一種資料結構, 可以用非常快的時間存取資料
什麼是雜湊表？核心概念
雜湊表是一種資料結構, 使用一個 key (鍵) 快速找到 Value (值), 速度通常可以達到 O(1), 比如 Python 的 dict, Java 的 HashMap, JavaScript 的 Object/ Map 均是屬於雜湊表, 用圖表可以這樣呈現
由圖中可以看見過 key 是唯一數值, 對應一個 value。
核心原理 ：雜湊函式
雜湊函式 (Hash Function) 會將任意大小的輸入, 透過函式轉換成一個固定大小數字, 最為索引並且寫入進入 Table 當中。
Hash Table 的重要特性
- 資料查找 (Search) : 透過查詢 key 鍵, 作為索引找到 value 數值。
- 資料新增 (Insert) : 透過函式的轉換計算雜湊值, 並且把數值插入這個索引位置。
- 資料刪除 (Delete) : 找到索引, 移除資料。
程式範例
import java.util.HashMap;
public class HashMapExample {
public static void main(String[] args) {
// 建立 HashMap (Key:String, Value:Integer)
HashMap<String, Integer> scores = new HashMap<>();
// 放入資料 (put)
scores.put("Alice", 90);
scores.put("Bob", 75);
scores.put("Charlie", 80);
// 根據 Key 取出資料
System.out.println("Alice 的分數 : " + scores.get("Alice"));
// 判斷 Key 是否存在
if (scores.containsKey("Bob")) {
System.out.println("Bob 的分數是 : " + scores.get("Bob"));
}
// 移除資料
scores.remove("Charlie");
// 遍歷所有的 key-value
for(String key : scores.keySet()) {
System.out.println(key + "=" + scores.get(key));
}
}
}
程式碼說明
- HashMap : 用來創建物件 (Object)。
- put : 插入資料。
- remove : 移除資料。
- 使用 for 迴圈去抓取所有資料。
雜湊衝突與解決方法
儘管雜湊表能夠達到高效率, 但在實際應用中卻可能會得到相同的雜湊值, 這就是所謂的雜湊衝突 (Hash Collision)
這時候可以使用以下幾中方法解決
- 鏈氏串接 (Chaining) : 在 Value 的地方不直接存數值, 而是改成鏈結串列 (Linked List) 或陣列, 發生衝突則直接加入到末端
- 開放定址法 (Open Addressing) : 發生衝突時, 雜湊表會在其他位置找可用的空間來儲存
總結 : 雜湊表資料結構的好幫手 ！
雜湊表在任程式當中都非常常見, 就是因為有極好的時間複雜度, 故在資料庫或者快取系統當中都可以看見其影子, 本篇以 Java 來作為例子簡單實作一個類別, 使讀者更了解雜湊值。
