C# Hashtable 內部實作深度剖析：雙重雜湊、衝突解決與擴容機制

Hashtable vs Dictionary

核心資料結構：bucket 結構體

struct bucket
{
    object key;      // 鍵
    object val;      // 值
    int hash_coll;   // 高位元=衝突旗標，低 31 位=雜湊碼
}

• hash_coll >= 0：無衝突，低 31 位存 key.GetHashCode() & 0x7FFFFFFF。
• hash_coll < 0：有衝突（最高位 1），低 31 位仍存雜湊碼。
• 刪除後：有衝突位置 → key = buckets（特殊標記）、hash_coll = 0x80000000；無衝突 → 全清 0。

雙重雜湊探測序列

h1 = key.GetHashCode() & 0x7FFFFFFF;
h2 = 1 + ((h1 >> 5) + 1) % (hashsize - 1);
探測位址 i: (h1 + i * h2) % hashsize   (i = 0, 1, 2...)

• hashsize 為質數（擴容時取近似 2x 的質數），確保 h2 與 hashsize 互質，探測序列覆蓋整個表。
• 裝載因子 α 上限 0.72，超過觸發擴容。

關鍵操作流程

新增

1. 計算 h1, h2，初始索引 bn = h1 % hashsize。
2. 線性探測：bn = (bn + h2) % hashsize。
3. 遇到 key == null（無衝突空位）或 key == buckets（已刪除有衝突空位） → 寫入，count++。
4. 遇到相同雜湊碼且 KeyEquals → 更新值或拋例外（Add 模式）。
5. 經過有衝突位置（hash_coll < 0） → 將該位置 hash_coll 最高位置 1。
6. 若 count >= loadsize → expand()（rehash 到新質數大小陣列）。

查詢

1. 同樣計算 h1, h2、初始索引。
2. 迴圈探測，直到：
   找到匹配鍵 → 回傳值；
   遇到 hash_coll >= 0（無衝突） → 結束回傳 null；
   探測次數達 hashsize → 結束回傳 null。

刪除

1. 找到目標位置。
2. 若原有衝突（hash_coll < 0）：hash_coll &= 0x80000000、key = buckets、val = null。
3. 若原無衝突：key = val = null、hash_coll = 0。
4. count--。

擴容

newSize = HashHelpers.GetPrime(buckets.Length * 2);
newBuckets = new bucket[newSize];
foreach (oldBucket in buckets)
    if (oldBucket.key != null && oldBucket.key != buckets)
        putEntry(newBuckets, oldBucket.key, oldBucket.val, oldBucket.hash_coll & 0x7FFFFFFF);
buckets = newBuckets;
loadsize = (int)(loadFactor * newSize);

簡易 Hashtable 實作教學碼

public class SimpleHashtable
{
    struct Entry { public object Key, Value; public int HashColl; }
    Entry[] buckets; int count, loadSize; float loadFactor = 0.72f;

    public SimpleHashtable(int capacity = 11)
    {
        int size = capacity > 11 ? GetPrime(capacity) : 11;
        buckets = new Entry[size];
        loadSize = (int)(loadFactor * size);
    }

    public void Add(object key, object value) => Insert(key, value, true);
    public object this[object key] { get => Find(key); set => Insert(key, value, false); }

    private void Insert(object key, object value, bool add)
    {
        if (count >= loadSize) Expand();
        uint h1 = (uint)(key.GetHashCode() & 0x7FFFFFFF);
        uint h2 = 1 + ((h1 >> 5) + 1) % (uint)(buckets.Length - 1);
        int bn = (int)(h1 % (uint)buckets.Length);
        int emptySlot = -1, ntry = 0;
        while (true)
        {
            ref Entry e = ref buckets[bn];
            if (e.Key == null)
            {
                if (emptySlot != -1) bn = emptySlot;
                e.Key = key; e.Value = value; e.HashColl = (int)h1; count++; return;
            }
            if (e.Key == buckets) { emptySlot = bn; } // 記錄已刪除衝突位
            if ((e.HashColl & 0x7FFFFFFF) == h1 && key.Equals(e.Key))
            {
                if (add) throw new ArgumentException("Key exists");
                e.Value = value; return;
            }
            if (emptySlot == -1 && e.HashColl >= 0) e.HashColl |= unchecked((int)0x80000000);
            bn = (int)((bn + h2) % (uint)buckets.Length);
            if (++ntry >= buckets.Length) throw new Exception("Full");
        }
    }
    // Find, Remove, Expand, GetPrime 略...
}

總結

Hashtable 以開放定址法 + 雙重雜湊實作，透過 hash_coll 高位元標記衝突、特殊標記處理刪除，設計精巧但受限於裝箱與探測機制，現代開發首選 Dictionary<TKey,TValue>。