從零手寫 Dictionary 與 IEnumerable：深入理解雜湊表與迭代器模式

一、手寫 MyDictionary：揭開 O(1) 查詢的秘密

.NET 內建 Dictionary<TKey,TValue> 以雜湊表實作。核心邏輯：
1. 計算 Key 的 GetHashCode() → 雜湊碼。
2. 雜湊碼對桶陣列長度取模 → 索引位置。
3. 該位置以鏈結串列 (或開放定址) 處理碰撞。
4. 查詢時同樣計算索引，僅遍歷該桶內極少數元素，故平均 O(1)。

簡易版 MyDictionary<string,string> 實作

using System;
using System.Collections.Generic;

public class MyDictionary
{
    private class Entry
    {
        public string Key;
        public string Value;
        public Entry Next; // 鏈結串列處理碰撞
        public Entry(string k, string v) { Key=k; Value=v; }
    }

    private Entry[] _buckets;
    private int _count;
    private const int InitialSize = 16;

    public MyDictionary()
    {
        _buckets = new Entry[InitialSize];
    }

    private int GetBucketIndex(string key)
    {
        int hash = key.GetHashCode();
        return (hash & 0x7FFFFFFF) % _buckets.Length; // 正數索引
    }

    public void Add(string key, string value)
    {
        int idx = GetBucketIndex(key);
        Entry head = _buckets[idx];
        // 檢查鍵是否已存在
        for (Entry e = head; e != null; e = e.Next)
            if (e.Key == key) throw new ArgumentException("Key already exists");

        // 頭插法
        Entry newEntry = new Entry(key, value) { Next = head };
        _buckets[idx] = newEntry;
        _count++;

        // 擴容檢查 (負載因子 > 0.75)
        if (_count > _buckets.Length * 0.75) Resize();
    }

    public bool ContainsKey(string key)
    {
        int idx = GetBucketIndex(key);
        for (Entry e = _buckets[idx]; e != null; e = e.Next)
            if (e.Key == key) return true;
        return false;
    }

    public string this[string key]
    {
        get
        {
            int idx = GetBucketIndex(key);
            for (Entry e = _buckets[idx]; e != null; e = e.Next)
                if (e.Key == key) return e.Value;
            throw new KeyNotFoundException();
        }
        set
        {
            int idx = GetBucketIndex(key);
            for (Entry e = _buckets[idx]; e != null; e = e.Next)
                if (e.Key == key) { e.Value = value; return; }
            Add(key, value); // 不存在則新增
        }
    }

    private void Resize()
    {
        var old = _buckets;
        _buckets = new Entry[old.Length * 2];
        _count = 0;
        foreach (var bucket in old)
            for (Entry e = bucket; e != null; e = e.Next)
                Add(e.Key, e.Value); // 重新雜湊分佈
    }
}

二、效能對比：為什麼內建 Dictionary 快 20 倍？

// 測試程式碼
var sw = Stopwatch.StartNew();
var dict = new Dictionary();
// ... 載入 10 萬筆資料 ...
dict.ContainsKey("china");
sw.Stop();
Console.WriteLine($"Dictionary: {sw.ElapsedTicks} ticks");

var myDict = new MyDictionary();
// ... 載入相同資料 ...
sw.Restart();
myDict.ContainsKey("china");
sw.Stop();
Console.WriteLine($"MyDictionary: {sw.ElapsedTicks} ticks");
// 典型結果：Dictionary ~50 ticks, MyDictionary ~1200 ticks

差距主因：
1. 內建類別使用優化的雜湊演算法、快速模運算、CPU 快取友善記憶體佈局。
2. 內建採用開放定址法 (Open Addressing) 而非鏈結串列，減少指標追蹤與記憶體碎片。
3. JIT 編譯器對核心庫類別有特殊優化 (內聯、去虛擬化)。

三、手寫 IEnumerable：實現 foreach 的關鍵

foreach 編譯器會轉換為：

IEnumerator enumerator = collection.GetEnumerator();
try {
    while (enumerator.MoveNext()) {
        var item = enumerator.Current;
        // 迴圈主體
    }
} finally {
    IDisposable d = enumerator as IDisposable;
    d?.Dispose();
}

因此類別只需實作 IEnumerable (回傳 IEnumerator) 即可支援 foreach。

自訂集合 MyList 實作 IEnumerable

using System;
using System.Collections;

public class MyList : IEnumerable
{
    private ArrayList _inner = new ArrayList();

    public void Add(string name) => _inner.Add(name);

    // 索引器 (額外福利)
    public string this[int index] => _inner[index]?.ToString();
    public int this[string name]
    {
        get {
            for (int i=0; i<_inner.Count; i++)
                if (_inner[i]?.ToString() == name) return i;
            return -1;
        }
    }

    // 核心：實作 GetEnumerator
    public IEnumerator GetEnumerator()
    {
        for (int i = 0; i < _inner.Count; i++)
            yield return _inner[i]?.ToString(); // yield 自動生成 IEnumerator
    }
}

使用方式

var list = new MyList();
list.Add("A"); list.Add("B"); list.Add("C");

Console.WriteLine(list[1]);        // B (索引器)
Console.WriteLine(list["B"]);      // 1 (反向查索引)

foreach (string s in list)         // foreach 自動呼叫 GetEnumerator
    Console.WriteLine(s);

// 編譯錯誤：foreach 唯讀
// foreach (var s in list) s = "X"; 

四、yield return 背後的狀態機

編譯器將包含 yield return 的方法轉換為實作 IEnumerator 的狀態機類別：

• Current 屬性回傳當前值。
• MoveNext() 推進到下一個 yield return 點。
• Reset() 重置狀態 (通常不實作)。

這也是為什麼 foreach 迴圈變數不可寫入：Current 只有 getter。

五、總結與現代替代方案

理解底層原理有助於效能調優與面試，實務開發請直接使用 BCL (Base Class Library) 經過嚴格測試、高度優化的集合類別。