Dictionary<TKey, TValue> の実装について

Dictionary<TKey, TValue> の実装について、ソースからの説明。
知ってるといいことあるかもしれない・・・

Dictionary の本体

// Dictionary の要素の構造体
// KeyValuePair をそのまま保持しているわけではない
private struct Entry {
    public int hashCode;  // 正の数にしたハッシュコード(0～7FFFFFFF)、-1 は未使用
    public int next;      // buckets 位置が同じ要素の次インデックス、-1 は次の要素無し
    public TKey key;      // キー
    public TValue value;  // 値
}

// ハッシュコード -> entries インデックスのマップ
// 実際は、正のハッシュコード % buckets.Length で buckets のサイズに合わせる
private int[] buckets;

// 要素の配列
private Entry[] entries;

ソースだけだとピンとこないかもしれないので、追加処理を図で。

IEqualityComparer<TKey>.GetHashCode() でキーからハッシュコードを求める
0x7FFFFFFF との論理積で、ハッシュコードを正の数にする

ハッシュコードを buckets 位置 B に変換（剰余を求める）

buckets[B] に entries の次の未使用インデックス E を設定

entries[E] に hashCode, key, value を設定

ちなみに、ハッシュコードの衝突（buckets 位置が使用済）が起こった場合。

buckets 位置 B を求める

buckets[B] に entries の次の未使用インデックス E を設定

entries[E] に hashCode, key, value を設定、next に buckets[B] の元の値を設定

Dictionary の容量

ハッシュテーブルの容量については素数派と 2^n 派が存在するが、Dictionary では素数を採用している。
※素数のメリットはハッシュ関数が多少ダメでも衝突が起こりにくいこと、2^n のメリットは剰余の計算が速いことらしい。

Dictionary で採用される素数については、HashTable ソースの HashHelpers.primes 参照。
HashHelpers.primes 以降の素数は、その場で計算される。（HashHelpers.GetPrime 参照）

Dictionary コンストラクタの capacity 引数で素数以外を指定しても、それ以上の素数に切り上げられる。
容量拡張が発生するタイミングは、entries を使い切った場合で、現在の容量×2 以上の素数に切り上げられる。
（buckets も同時に拡張される）

Dictionary の列挙

entries の順序どおり列挙される。
entries は先頭から埋められていくので、Add とインデクサによる追加・変更のみならば、Dictionary への追加順で列挙される。

Remove による削除が発生した場合、次の追加処理では、削除された領域を先に使うため、追加順による列挙ではなくなる。
※複数削除の場合は、Entry.next を利用して空き領域リストが構築される

[Remove → Add 後の列挙]

static class TestDic
{
    static void Main()
    {
        var dic = new Dictionary<string, int>();
        var val = 0;
        foreach( var c in "abc" ) dic.Add(c.ToString(), val++);
        Console.WriteLine("ADD a b c");
        Console.WriteLine(string.Join(" ", dic));

        dic.Remove("b");
        Console.WriteLine("REMOVE b");
        Console.WriteLine(string.Join(" ", dic));

        dic.Add("d", val++);
        Console.WriteLine("ADD d");
        Console.WriteLine(string.Join(" ", dic));
    }
}

[結果]

ADD a b c
[a, 0] [b, 1] [c, 2]
REMOVE b
[a, 0] [c, 2]
ADD d
[a, 0] [d, 3] [c, 2]

また、列挙時に追加・変更・削除が検知できるよう、version メンバ変数がある。
追加・変更・削除が発生した場合は version をインクリメントして、IEnumerator の MoveNext 時に version が変わっていたら、InvalidOperationException を発生させる。

IEqualityComparer<TKey>

キーのハッシュコードの計算や一致比較を担当する IEqualityComparer<TKey> は、コンストラクタの comparer 引数で指定することができる。
未指定や null を渡した場合は EqualityComparer<TKey>.Default が使用される。
MSDN にある「既定の等値比較子」がこれに該当する。

int や string など基本的な型は EqualityComparer<TKey>.Default で問題ないが、配列や自前のクラスなどは IEqualityComparer<TKey> を自分で用意する必要がある。
※EqualityComparer<T>.Default については、いつか説明予定・・・

ちなみに、値を担当する IEqualityComparer<TValue> はコンストラクタで指定できないため、問答無用で EqualityComparer<TValue>.Default が使用される。
実際に使用されているメソッドは下記。

• ContainsValue
• ICollection<KeyValuePair<TKey, TValue>>.Contains
• ICollection<KeyValuePair<TKey, TValue>>.Remove

EqualityComparer<TValue>.Default で正確な一致比較ができない場合は、これらを使用しない方がいい。