軟體工程師職涯升級計畫啟動！立即預約職涯諮詢、履歷健檢或模擬面試👈，為您的加薪做好準備！
什麼是雜湊表？—— 鍵值對的抽象資料型態
想像一下，你有一本非常厚的通訊錄。如果這本通訊錄是按照每個人的姓名首字母排序的，當你想找「王小明」的電話時，你可以迅速翻到「W」的開頭，然後快速找到他。雜湊表就是這樣的概念，它是一種以「鍵值-資料對（Key-Value Pair）」來描述資料的抽象資料型態（Abstract Data Type, ADT）。
換句話說，雜湊表的核心概念就是：你提供一個獨特的鍵（Key），雜湊表就能夠迅速幫你找到與之相對應的值（Value）。這個過程就像給每個資料一個獨特的「標籤」，然後透過這個標籤直接找到資料本身。
雜湊表的魔力：極致的搜尋速度
雜湊表之所以被廣泛應用於各種系統中，是因為它擁有一個殺手級的特性：
- 極高的搜尋、新增、刪除速度： 在理想情況下，雜湊表的操作時間複雜度都趨近於 O(1)。
- 鍵（Key）的唯一性： 雜湊表中，每個鍵都必須是唯一的。這保證了你可以透過一個鍵準確地找到一個唯一的值。如果試圖用相同的鍵新增不同的值，通常會覆蓋舊的值或拋出錯誤，這取決於雜湊表的具體實現。
核心原理：雜湊函式
雜湊表之所以能實現 O(1) 的平均時間複雜度，關鍵在於雜湊函式（Hash Function）。雜湊函式是一個將任意大小的輸入資料（鍵）轉換成一個固定大小的數字（稱為雜湊值或雜湊碼）的演算法。這個雜湊值通常會被用作資料在內部陣列中的索引。
運作流程：
- 資料新增 (Insert)：
- 將要儲存的**鍵（Key）**傳入雜湊函式。
- 雜湊函式計算出一個雜湊值（Hash Value）。
- 將這個雜湊值作為內部陣列的索引（Index），把**值（Value）**儲存在該索引位置。
- 資料查詢 (Search)：
- 將要查詢的**鍵（Key）**傳入相同的雜湊函式。
- 雜湊函式計算出相同的雜湊值。
- 利用這個雜湊值作為索引，直接從內部陣列中取出對應的值（Value）。
- 資料刪除 (Delete)：
- 類似查詢操作，透過雜湊函式找到對應的索引，然後從該位置移除資料。
實作雜湊表：方法與 JavaScript 範例
讓我們用 JavaScript 來簡單模擬雜湊表的實現。在 JavaScript 中，原生的 Object 和 Map 類型其實就是雜湊表的實現。
使用 JavaScript Object (物件) 模擬
JavaScript 的物件本身就是一個鍵值對的集合，非常類似於雜湊表。鍵會被轉換為字串，用作物件的屬性名。
JavaScript
class SimpleHashTable {
constructor() {
this.data = {}; // 使用 JS 物件作為內部儲存
}
/**
* 新增資料到雜湊表
* @param {string} key - 唯一的鍵
* @param {*} value - 要儲存的值
*/
insert(key, value) {
if (this.data.hasOwnProperty(key)) {
console.warn(`Key "${key}" already exists. Overwriting value.`);
}
this.data[key] = value; // 直接用鍵作為屬性名
console.log(`Inserted: ${key} -> ${value}`);
}
/**
* 查詢雜湊表中的資料
* @param {string} key - 要查詢的鍵
* @returns {*} - 鍵對應的值，如果找不到則返回 undefined
*/
search(key) {
if (this.data.hasOwnProperty(key)) {
console.log(`Found: ${key} -> ${this.data[key]}`);
return this.data[key];
} else {
console.log(`Key "${key}" not found.`);
return undefined;
}
}
/**
* 從雜湊表中刪除資料
* @param {string} key - 要刪除的鍵
* @returns {boolean} - 如果成功刪除則返回 true，否則返回 false
*/
delete(key) {
if (this.data.hasOwnProperty(key)) {
const deletedValue = this.data[key];
delete this.data[key]; // 使用 delete 操作符移除屬性
console.log(`Deleted: ${key} -> ${deletedValue}`);
return true;
} else {
console.log(`Key "${key}" not found. Nothing to delete.`);
return false;
}
}
/**
* 檢查雜湊表是否包含某個鍵
* @param {string} key - 要檢查的鍵
* @returns {boolean} - 如果包含則返回 true，否則返回 false
*/
has(key) {
return this.data.hasOwnProperty(key);
}
/**
* 獲取所有鍵
* @returns {Array<string>} - 雜湊表中所有的鍵
*/
keys() {
return Object.keys(this.data);
}
/**
* 獲取所有值
* @returns {Array<*>} - 雜湊表中所有的值
*/
values() {
return Object.values(this.data);
}
}
// --- 使用範例 ---
console.log("--- 使用 SimpleHashTable ---");
const myHashTable = new SimpleHashTable();
myHashTable.insert("name", "Alice");
myHashTable.insert("age", 30);
myHashTable.insert("city", "New York");
myHashTable.insert("occupation", "Engineer");
myHashTable.search("name"); // Found: name -> Alice
myHashTable.search("age"); // Found: age -> 30
myHashTable.search("country"); // Key "country" not found.
console.log("Does it have 'city'?", myHashTable.has("city")); // true
console.log("All keys:", myHashTable.keys()); // ["name", "age", "city", "occupation"]
myHashTable.delete("age"); // Deleted: age -> 30
myHashTable.search("age"); // Key "age" not found.
myHashTable.insert("name", "Bob"); // Key "name" already exists. Overwriting value.
myHashTable.search("name"); // Found: name -> Bob
程式碼說明：
SimpleHashTable類別內部使用一個普通的 JavaScript 物件this.data來儲存鍵值對。insert()方法直接將鍵作為屬性名，值作為屬性值儲存。search()方法透過鍵直接存取物件屬性。delete()方法使用delete運算符移除屬性。hasOwnProperty()用於判斷物件自身是否包含指定屬性，避免查詢到原型鏈上的屬性。
更原生的方式：JavaScript Map (映射)
從 ES6 開始，JavaScript 引入了 Map 物件，它提供了更完善的鍵值對儲存功能，且允許任何型別的值作為鍵（而不僅僅是字串，這是 Object 的限制）。Map 在內部實現上，也更接近於一個高效的雜湊表。
JavaScript
console.log("\n--- 使用原生的 JavaScript Map ---");
const myMap = new Map();
// 新增資料 (set)
myMap.set("name", "Charlie");
myMap.set(123, "Number Key");
myMap.set(true, "Boolean Key");
console.log("Map size:", myMap.size); // 3
// 查詢資料 (get)
console.log("Name:", myMap.get("name")); // Charlie
console.log("Number Key:", myMap.get(123)); // Number Key
console.log("Non-existent key:", myMap.get("address")); // undefined
// 檢查鍵是否存在 (has)
console.log("Has 'true' key?", myMap.has(true)); // true
console.log("Has 'false' key?", myMap.has(false)); // false
// 刪除資料 (delete)
myMap.delete(123);
console.log("Map size after delete:", myMap.size); // 2
console.log("Number Key after delete:", myMap.get(123)); // undefined
// 再次新增相同鍵會覆蓋
myMap.set("name", "David");
console.log("Updated name:", myMap.get("name")); // David
// 遍歷 Map
console.log("Iterating over Map entries:");
for (const [key, value] of myMap) {
console.log(`${key} -> ${value}`);
}
// Output:
// name -> David
// true -> Boolean Key
// 清空 Map (clear)
myMap.clear();
console.log("Map size after clear:", myMap.size); // 0
程式碼說明：
Map提供了set()、get()、has()和delete()等直觀的方法，功能更強大、更符合雜湊表的抽象。Map允許使用非字串型別作為鍵，例如數字、布林值甚至其他物件。Map保證了鍵的插入順序，這在Object中是不保證的（儘管現代 JavaScript 引擎通常會保留數值和符號鍵的插入順序）。
雜湊衝突與解決方案
儘管雜湊表在理想情況下能達到 O(1) 的效率，但在實際應用中，不同的鍵經過雜湊函式計算後，可能會得到相同的雜湊值，這就是所謂的雜湊衝突（Hash Collision）。
想像一下，你的通訊錄裡有兩個人，一個叫「王力宏」，一個叫「王麗紅」，它們的首字母都是「W」，當你翻到「W」的頁面時，你會發現兩個人都在。這就是一個簡化的雜湊衝突。
有兩種主要的方法來解決雜湊衝突：
- 鏈式串接（Chaining）：
- 在每個雜湊值對應的儲存位置，不直接儲存值，而是儲存一個鏈結串列（Linked List）或陣列。當發生衝突時，新的鍵值對會被添加到該鏈結串列的末尾。
- 優點： 實現相對簡單，對雜湊函式的質量要求不高。
- 缺點： 當衝突過多時，鏈結串列會變長，導致搜尋時間退化到 O(n)（最壞情況）。
- 範例： 想像一個百貨公司的停車場，每個樓層（雜湊值）有許多停車位（鏈結串列）。即使同一樓層的停車位都滿了，你還是可以在同一樓層找到另一個空位，但可能要找很久。
- 開放定址法（Open Addressing）：
- 當發生衝突時，雜湊表會嘗試在其他位置尋找下一個可用的空位來儲存資料。常見的策略有：
- 線性探測（Linear Probing）： 依序檢查下一個位置，直到找到空位。
- 二次探測（Quadratic Probing）： 以平方增長的方式跳躍尋找空位。
- 雙重雜湊（Double Hashing）： 使用第二個雜湊函式來計算探測的步長。
- 優點： 不需要額外的儲存空間來儲存鏈結串列，快取效率較高。
- 缺點： 實現較複雜，容易出現**叢集（Clustering）**現象（已佔用的區塊聚集），影響性能；需要處理表格滿載時的擴容問題。
- 範例： 想像一個百貨公司的立體停車塔，當目標停車位被佔用時，系統會自動幫你找附近的其他空位。
良好雜湊函式的重要性
為了最大程度地減少雜湊衝突並維持雜湊表的高效率，一個好的雜湊函式至關重要。好的雜湊函式應該具備以下特點：
- 快速計算： 函式本身的計算應該非常快速。
- 均勻分布： 能夠將不同的輸入鍵均勻地映射到雜湊表的各個位置，減少衝突的發生。
- 一致性： 對於相同的輸入鍵，雜湊函式必須始終產生相同的雜湊值。
總結：雜湊表——高效數據管理的利器
雜湊表是一個強大且用途廣泛的資料結構，因其出色的平均時間複雜度而成為許多應用程式的核心組件。從資料庫索引、快取系統、程式語言的字典/物件實現，到網路路由和密碼學，雜湊表無處不在。
理解雜湊表的運作原理、特性以及如何處理雜湊衝突，對於任何想要深入學習資料結構和演算法的開發者來說都至關重要。透過 JavaScript 的物件和 Map 範例，我們可以看到這種高效資料結構在實際程式設計中的應用。
