コレクション系インターフェース 早見表

コレクション系インターフェースの型パラメータの共変性、および、実装されるメソッド、プロパティの早見表。
※IReadOnly～ は .NET 4.5 から導入
※非ジェネリックはもう使わないと思うので省略

	共変 <out T>	メソッド									プロパティ
		GetEnumerator()	Add( T )	Clear()	Contains( T )	CopyTo( T[], int )	Remove( T )	IndexOf( T )	Insert( int, T )	RemoveAt( int )	Count { get; }	IsReadOnly { get; }	this[ int ] { get; }	this[ int ] { set; }
IEnumerable<T>
ICollection<T>
IList<T>
IReadOnlyCollection<T>
IReadOnlyList<T>

	メソッド				プロパティ
	Add( TKey, TValue )	ContainsKey( TKey )	Remove( TKey )	TryGetValue( TKey, out TValue )	this[ TKey ] { get; }	this[ TKey ] { set; }	Keys { get; }	Values { get; }
IDictionary <TKey, TValue>									他の項目は ICollection<T> 参照 Keys と Values は ICollection<T>
IReadOnlyDictionary <TKey, TValue>									他の項目は IReadOnlyCollection<T> 参照 Keys と Values は IEnumerable<T>

雑感

元々あまり使われなかっただろう IsReadOnly プロパティは、IReadOnly～ インターフェースが導入されたため、完全に要らない子に・・・

IReadOnlyDictionary の Keys／Values プロパティの戻り値が IReadOnlyCollection<T> ではなく IEnumerable<T> なのは、Count プロパティの使用頻度と実装のし易さあたりが理由？
確かに Keys や Values の Count プロパティなんてほぼ使わないだろうし、IEnumerable<T> だと yield で簡単実装できるから、いい判断だと思う。
逆に、IDictionary の Keys／Values プロパティの戻り値 ICollection<T> は機能が過剰だし、実装も面倒。

.NET 4.5 からは IReadOnly～ を積極的に使っていこう・・・かな

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 で正確な一致比較ができない場合は、これらを使用しない方がいい。

System.Collections.ObjectModel.Collection<T> について

System.Collections.ObjectModel にある Collection<T> について、ソース観点からの補足説明のようなもの。

主な用途は、継承用クラスになる。
実際、System.Collections.ObjectModel にある他クラスの継承元として使われている。
単品で使用できないこともないが、IList<T> ないし List<T> の単なるラッパになるので（Collection<T> の引数無しコンストラクタは内部で List<T> を生成）、ラップするメリットがあまりない。
List<T> の機能を制限したいなら、基本的にインターフェースへのキャストで十分。

状態変更時に挟める protected メソッドとして、ClearItems、InsertItem、RemoveItem、SetItem が用意されている。
これらと状態変更用の public メソッド・プロパティとの関係は下記

public	protected	protectedの実装	備考
Item （インデクサ）	SetItem	IList[index] = item	protected メソッド実装時、index 引数の境界値チェックは不要。（public 側で実施済）
Add	InsertItem	IList.Insert(index, item)
Insert
Remove	RemoveItem	IList.RemoveAt(index)
RemoveAt
Clear	ClearItems	IList.Clear()

注意すべきは、Add と Insert で同じ InsertItem メソッドが使われる点。
Add(item) は Insert(Length - 1, item) として処理される。

表でも自明なように IList.Add は使用されない。
自前の IList のラッパーとする場合、IList.Add のみの特殊処理を実装していても使われないので注意。
（普通は IList.Insert と差がある実装にしないだろうけど・・・）