淺談 Hash、Hashtable 與 HashMap

Hash 這玩意兒是程式世界的基礎，但一堆人搞不清楚 Hash、Hashtable、HashMap 的差別。常見情況：被問到為啥用 HashMap 不用 Hashtable，只能兩眼發直。今天就一次講清楚。

Hash 的概念

Hash 就是把任意長度的資料「打碎」再「拼湊」成固定長度的代碼。

Hash Function 做的事

1 2	String input = "This is a very long sentence with lots of words"; int hashCode = input.hashCode(); // 回傳一個整數，比如 -123456789

Hash Function 的特性：

決定性 - 同一個輸入永遠產生同一個輸出
單向性 - 不可逆，不能從 hash code 推回原始資料
雪崩效應 - 輸入改一點點，輸出就完全不同
均勻分佈 - 理想情況下，不同輸入的 hash 值均勻分佈在整個範圍

Hash 的應用

1. 數位簽章
確認資料沒有被竄改。簽署人計算文件的 hash 值，用私鑰加密。驗證人計算一遍 hash，再用公鑰解密比對。如果兩個 hash 相同，代表文件沒動過。

2. 資料完整性驗證
下載檔案時，官方會提供 SHA256 checksum。你下載完自己算一次，比對是否相同。如果相同，代表沒有傳輸損壞或被中間人修改。

3. 密碼儲存
千萬別存明文密碼。應該存 hash 值。使用者登入時，計算輸入密碼的 hash，和資料庫裡的比對。即使資料庫被盜，駭客也只能拿到 hash，推不回密碼。

編碼 vs 加密 vs Hash

很多人搞混這三個：

編碼（Encoding）：ASCII、UTF-8、Base64
  - 可逆
  - 沒有金鑰
  - 目的：轉換資料格式便於傳輸
  - 例：Base64.encode("hello") = "aGVsbG8="，decode 就回來了

加密（Encryption）：AES、RSA
  - 可逆（用密鑰）
  - 需要金鑰
  - 目的：保護資料機密性
  - 例：AES.encrypt("hello", key) = "xyz123"，用 key 才能 decrypt

Hash（雜湊）：MD5、SHA1、SHA256
  - 不可逆
  - 不需金鑰
  - 目的：驗證資料完整性
  - 例：SHA256("hello") = "2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824"

Hash Table 資料結構

Hash Table 是一種資料結構，用來解決「快速查找」問題。

基本概念

傳統陣列的問題：

有序查找（線性搜尋）：O(n)，要一個一個比
二元搜尋：O(log n)，但需要排序

Hash Table 用 hash code 當 index：

要存 key="Alice", value="Engineer"
1. 計算 hash("Alice") = 5
2. 放到 table[5] = "Engineer"
3. 查詢時，直接看 table[5]，O(1) 完成！

理想情況下，查詢、插入、刪除都是 O(1)。

雜湊碰撞問題

但現實有個問題：雜湊碰撞（hash collision）。

1
2
3

hash("Alice") = 5
hash("Bob") = 3
hash("Cathy") = 5  // 碰撞了！都是 5

不同的鍵產生相同的 hash code，怎麼辦？有兩個常見解法：

1. Closed Addressing（閉放定址法）

在 table[5] 這個位置放一個 linked list 或其他結構，把所有碰撞的元素都存進去：

1	table[5] -> "Alice" -> "Cathy" -> null

查詢時要遍歷 linked list，最壞情況 O(n)。但如果 hash function 夠好，碰撞很少，平均還是接近 O(1)。

2. Open Addressing（開放定址法）

碰撞時，找個 empty slot 放進去：

1 2	hash("Alice") = 5 -> table[5] hash("Cathy") = 5（碰撞）-> 找下一個 empty -> table[6]

線性探測、二次探測等方法。

Java 的 Hashtable 類

Hashtable 是 JDK 1.0 的遠古生物。

基本特性

Hashtable<String, Integer> ht = new Hashtable<>();
ht.put("Apple", 10);
ht.put("Banana", 20);

int price = ht.get("Apple");  // 10
ht.remove("Banana");

主要特性：

執行緒安全 - 幾乎所有方法都加了 synchronized
Key 和 Value 都不能是 null - put(null, value) 直接 NPE
效能一般 - synchronized 全都上，競爭激烈時效能堪憐
舊時代遺留 - 現在已經棄用

為啥不允許 null？因為 Hashtable 無法區分「鍵不存在」和「鍵對應的值是 null」。get() 回傳 null 時，你不知道是找不到，還是真的存了 null。

為啥要棄用

效能問題太嚴重。簡單的 get 操作：

public synchronized V get(Object key) {
    Entry tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return e.value;
        }
    }
    return null;
}

整個方法都 synchronized，其他執行緒都要排隊。如果你有 100 個執行緒都在讀，全部堵住。

HashMap 類

HashMap 是現代的選擇。

基本特性

Map<String, Integer> map = new HashMap<>();
map.put("Apple", 10);
map.put("Banana", 20);
map.put(null, 999);  // 允許 null key
map.put("Orange", null);  // 允許 null value

int price = map.get("Apple");  // 10
Integer missing = map.get("NotExist");  // null

主要特性：

不執行緒安全 - 沒有 synchronized，多執行緒要自己同步或用 ConcurrentHashMap
Key 和 Value 可以是 null - 但只能有一個 null key
效能好 - 沒有鎖的開銷
可預測的迭代順序 - 不保證（1.7 是 bucket order，1.8+ 是 insertion order for linked entries）

HashMap 內部結構（Java 1.8+）

// 簡化版結構
class HashMap<K, V> {
    static final int DEFAULT_CAPACITY = 16;  // 預設容量
    Entry<K, V>[] table;  // hash table
    
    public V put(K key, V value) {
        int hash = hash(key);
        int index = hash % table.length;
        
        // 放到 table[index] 這個 bucket 裡
        // 如果碰撞，使用 linked list 或 red-black tree（Java 1.8）
    }
}

Java 1.8 之後的改進：

碰撞少時用 linked list
碰撞多時（超過 8 個）自動轉成 red-black tree，查詢快速到 O(log n)

什麼時候會 resize

HashMap<String, Integer> map = new HashMap<>();  // 容量 16

// 插入資料後，當 size > capacity * loadFactor 時（預設 0.75）
// 16 * 0.75 = 12，所以第 13 個元素會觸發 resize
// 新容量 = 舊容量 * 2 = 32

Resize 很昂貴（要重新計算所有元素的 index），所以如果預先知道大小，最好初始化時指定：

1	Map<String, Integer> map = new HashMap<>(1000); // 指定容量 1000

ConcurrentHashMap 是更好的選擇

需要執行緒安全？別再用 Hashtable，用 ConcurrentHashMap：

1
2
3

Map<String, Integer> map = new ConcurrentHashMap<>();
map.put("Apple", 10);
map.get("Apple");

優勢：

分段鎖（Segment Lock） - 不是鎖整個表，而是分成多個段，每個段有自己的鎖
好效能 - 多執行緒讀寫競爭不大
Key 和 Value 不能是 null

簡單概念：

Hashtable:
  [lock] [bucket1] [bucket2] [bucket3] ... [bucket16]
  一個全域鎖，所有操作都要等

ConcurrentHashMap:
  [bucket1-4][bucket5-8][bucket9-12][bucket13-16]
    [lock1]    [lock2]      [lock3]        [lock4]
  4 個段，4 個鎖，最多 4 個執行緒並行操作

Java Collections Framework

Hashtable 和 HashMap 在 Java Collections 的位置不同。

Collection（介面）
├── Set
│   ├── HashSet
│   ├── LinkedHashSet
│   └── TreeSet
└── List
    ├── ArrayList
    ├── LinkedList
    └── Vector

Map（介面，不是 Collection 的子介面！）
├── HashMap
├── LinkedHashMap
├── TreeMap
├── ConcurrentHashMap
└── Hashtable

重點：Map 和 Collection 並列，不是包含關係。

這是因為 Map 是 key-value 結構，邏輯上和 Collection（單一元素）不同。

實務建議

新專案用 HashMap - 除非特殊需求，Hashtable 已死

需要執行緒安全用 ConcurrentHashMap

// 不好
Map<String, Data> map = Collections.synchronizedMap(new HashMap<>());

// 更好
Map<String, Data> map = new ConcurrentHashMap<>();

保持插入順序用 LinkedHashMap

1	Map<String, Integer> map = new LinkedHashMap<>(); // 保持插入順序

預先知道大小，初始化容量

1	Map<String, String> map = new HashMap<>(100); // 避免頻繁 resize

永遠別用 null 作為 key - 會造成混亂

// 不好做法
map.put(null, "value");
if (map.get(someKey) == null) {  // 不知道是 null key 還是 not found
}

就醬，Hash 的世界沒那麼複雜，關鍵是理解基本概念，選對工具。