Java 集合框架深度解析：Hashtable 核心原理、遍歷方式與 HashMap 關鍵差異對比

Java 集合框架深度解析：Hashtable 核心原理、遍歷方式與 HashMap 關鍵差異對比

Hashtable 是 Java 1.0 時代引入的經典哈希表實現，雖然被 HashMap 和 ConcurrentHashMap 取代主流地位，但理解其內部結構、同步機制與局限性，有助於深入掌握集合框架演進脈絡。本文系統剖析 Hashtable 源碼（JDK 8 視角），覆蓋數據結構、核心方法、遍歷方式、與 HashMap 的關鍵差異。

一、類定義與繼承體系

public class Hashtable<K,V> 
    extends Dictionary<K,V> 
    implements Map<K,V>, Cloneable, java.io.Serializable

• 繼承 Dictionary<K,V>：古老抽象類，已被 Map 取代
• 實現 Map、Cloneable、Serializable
• 所有公共方法均加 synchronized：方法級粗粒度同步

二、核心數據結構：拉鏈法哈希表

// 核心字段
private transient Entry<K,V>[] table;  // 哈希桶數組
private transient int count;            // 元素數量
private int threshold;                  // 擴容閾值 = capacity * loadFactor
private float loadFactor;               // 加載因子 (默認 0.75)
private transient int modCount = 0;     // 結構修改次數，支撐 fail-fast

Entry 節點（單向鏈表）

private static class Entry<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Entry<K,V> next;  // 指向下一個節點

    Entry(int hash, K key, V value, Entry<K,V> next) {
        this.hash = hash; this.key = key; this.value = value; this.next = next;
    }
    // getKey/getValue/setValue 實現...
}

三、構造方法族系

四、核心方法源碼剖析

1. put(K key, V value) —— 同步插入/更新

public synchronized V put(K key, V value) {
    // 1. 值不能為 null（關鍵差異）
    if (value == null) throw new NullPointerException();

    // 2. 計算索引
    Entry<K,V>[] tab = table;
    int hash = hash(key);
    int index = (hash & 0x7FFFFFFF) % tab.length;

    // 3. 遍歷鏈表：key 存在則更新，返回舊值
    for (Entry<K,V> e = tab[index]; e != null; e = e.next) {
        if (e.hash == hash && e.key.equals(key)) {
            V old = e.value;
            e.value = value;
            return old;
        }
    }

    // 4. 擴容檢查
    modCount++;
    if (count >= threshold) {
        rehash();  // 容量翻倍+1，重新哈希
        tab = table;
        hash = hash(key);
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    // 5. 頭插法插入新節點
    Entry<K,V> e = tab[index];
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
    return null;
}

2. get(Object key) —— 同步查找

public synchronized V get(Object key) {
    Entry<K,V>[] tab = table;
    int hash = hash(key);
    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;
}

3. rehash() 擴容機制

protected void rehash() {
    int oldCapacity = table.length;
    Entry<K,V>[] oldTable = table;

    // 新容量 = 老容量 * 2 + 1 (保持質數特性)
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE) return;
        newCapacity = MAX_ARRAY_SIZE;
    }

    Entry<K,V>[] newTable = new Entry<K,V>[newCapacity];
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newTable;

    // 重新哈希所有節點到新表
    for (int i = oldCapacity; i-- > 0;) {
        for (Entry<K,V> old = oldTable[i]; old != null; ) {
            Entry<K,V> e = old;
            old = old.next;
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = newTable[index];
            newTable[index] = e;
        }
    }
}

五、四種遍歷方式（均為同步安全）

Hashtable<String, String> table = new Hashtable<>();
// ... 放入數據

// 1. keys() - Enumeration (舊 API)
Enumeration<String> en1 = table.keys();
while (en1.hasMoreElements()) { String k = en1.nextElement(); }

// 2. elements() - Enumeration (舊 API)
Enumeration<String> en2 = table.elements();
while (en2.hasMoreElements()) { String v = en2.nextElement(); }

// 3. keySet() - Iterator (現代 API)
Iterator<String> it1 = table.keySet().iterator();
while (it1.hasNext()) { String k = it1.next(); }

// 4. entrySet() - Iterator (現代 API，推薦)
Iterator<Map.Entry<String, String>> it2 = table.entrySet().iterator();
while (it2.hasNext()) { 
    Map.Entry<String, String> entry = it2.next(); 
    String k = entry.getKey(); String v = entry.getValue();
}

六、Hashtable vs HashMap 關鍵差異對比

七、為什麼不推薦在新項目中使用 Hashtable？

1. 同步粒度太粗：全表鎖，併發吞吐極低
2. 功能受限：不支持 null，無法滿足現代業務需求
3. 替代方案更優：
   • 單線程/非併發 → HashMap
   • 併發讀寫 → ConcurrentHashMap (JDK 8 CAS + synchronized 細粒度，JDK 17 更強)
   • 需要同步 Map 視圖 → Collections.synchronizedMap(new HashMap<>())
4. 僅存於遺留代碼：早期 API、部分第三方庫、舊配置類

八、總結

1. Hashtable 採用數組 + 單向鏈表（拉鏈法），質數容量、頭插法、全方法同步
2. 核心限制：Key/Value 不可為 null，這是與 HashMap 最大行為差異
3. 擴容策略 2n+1 保持質數，但位運算不如 2 的冪次高效
4. 現代開發全場景替換為 HashMap / ConcurrentHashMap
5. 理解 Hashtable 有助於掌握哈希表演進：從粗粒度鎖 → 細粒度鎖 → 無鎖 CAS → 紅黑樹優化