J2ME Hashtable 內部實現原理深度剖析：從源碼看雜湊表核心機制

前言：為何要讀 Hashtable 源碼？

Hashtable 是 J2ME 核心集合，理解其內部機制能指導容量規劃、避免效能陷阱、排查記憶體異常。本文基於 CLDC 實現源碼，剖析結構佈局、關鍵方法與設計細節。

核心結構佈局

關鍵欄位

private transient HashtableEntry[] table;  // 雜湊桶數組
private transient int count;               // 實際元素數

transient 關鍵字：標記不參與序列化。CLDC Hashtable 不支援序列化，因核心容器欄位皆為 transient。

內部類：HashtableEntry（雜湊桶節點）

class HashtableEntry {
    int hash;           // 鍵的 hashCode
    Object key;         // 鍵
    Object value;       // 值
    HashtableEntry next; // 下一個節點（鏈表解決衝突）
}

採用數組 + 鏈表（Separate Chaining）經典結構。

內部類：HashtableEnumerator（疊代器）

class HashtableEnumerator implements Enumeration {
    boolean keys;              // true=疊代鍵, false=疊代值
    int index;                 // 當前掃描桶索引
    HashtableEntry[] table;    // 桶數組引用
    HashtableEntry entry;      // 當前鏈表節點
    
    // 構造時 index 設為 table.length，從末尾向前掃描
    // hasMoreElements() / nextElement() 協同推進
}

精妙寫法：while (index-- > 0 && (entry = table[index]) == null); 單行完成「向前找下一非空桶並定位鏈表頭」。

雜湊索引計算

int index = (hash & 0x7FFFFFFF) % tab.length;

• & 0x7FFFFFFF：確保非負（去除符號位）
• 取模桶數組長度 → 桶索引
• 桶數組長度通常為質數（默認 11），減少衝突

核心方法邏輯

put(K, V)

1. 計算 hash = key.hashCode()
2. 定位桶索引 index
3. 遍歷該桶鏈表：
   　　• 找到相同鍵（equals） → 替換值，返回舊值
   　　• 未找到 → 建立新 Entry 插入鏈表頭
4. count++，檢查 count > threshold (capacity * 0.75) → rehash()

get(K)

1. 計算 hash、定位桶
2. 遍歷鏈表 equals 比對，命中返回 value，否則 null

remove(K)

1. 定位桶，遍歷鏈表尋找目標節點
2. 修正前驅節點 next 指針跳過目標節點
3. count--，返回被刪除值

rehash() 擴容

1. 新容量 newCapacity = oldCapacity * 2 + 1（保持質數特性）
2. 分配新桶數組 newTable
3. 遍歷舊桶所有節點，重新計算索引插入新桶
4. 替換 table = newTable

CLDC 實現的特殊限制

• 負載因子固定 0.75，無構造函數可調
• 無泛型，編譯期無型別檢查
• 非同步安全，多執行緒需外部同步
• 不可序列化（transient 欄位）

效能調優啟示

1. 預設容量：new Hashtable(預估元素數 / 0.75 + 1) 避免 rehash
2. 鍵的 hashCode()：高品質雜湊碼決定分佈均勻度，自定義鍵類必須覆寫 hashCode() 與 equals()
3. 避免頻繁 remove/put 交替：導致鏈表碎片化，必要時重建 Hashtable

結語

Hashtable 以「數組 + 鏈表」、質數桶長度、固定負載因子、transient 非序列化等設計選擇，在極度受限的 CLDC 環境中平衡了效能、記憶體與代碼體積。讀懂源碼，才能真正駕馭這個看似簡單實則精妙的核心集合。