[C#] System.Collections.Specialized.ListDictionary — 小規模辞書に特化した連結リスト実装

System.Collections.Specialized.ListDictionary は、単方向連結リストで実装された小規模辞書 です。要素数が 10 件程度までなら、ハッシュ計算のオーバーヘッドが省ける分だけ Hashtable より速いという想定で設計されました。HybridDictionary の小規模時の中身としても使われています。

`ListDictionary` とは

名前空間：System.Collections.Specialized
内部構造：単方向連結リスト（各ノードがキー・値・次ノードへの参照を持つ）
検索は 線形探索：先頭から順にキーを比較
キーの比較は既定で Object.Equals、コンストラクタで IComparer を渡すこともできる

using System.Collections.Specialized;

var dict = new ListDictionary
{
    { "apple",  150 },
    { "orange", 120 },
    { "cherry", 300 },
};

int price = (int)dict["apple"]!; // 150

サポートするインターフェース

インターフェース	役割
`IDictionary`	キー・値の連想コレクション
`ICollection`	`Count` / `CopyTo` / 同期サポート
`IEnumerable`	`foreach` で `DictionaryEntry` を列挙

各インターフェースの詳細は次を参照してください。

IDictionary: Hashtable の記事
ICollection: ArrayList の記事
IEnumerable: IEnumerable と IEnumerator の記事

主な API と計算量

すべての検索系操作が 線形探索 なため、Hashtable や Dictionary<TKey, TValue> の O(1) と異なり O(n) になります。

操作	計算量
取得 `[key]`	O(n)
追加 `Add(k, v)`	O(n)（重複チェックのため）
削除 `Remove(k)`	O(n)
`Contains(k)`	O(n)
列挙	O(n)

要素が数件しかなければ実時間は誤差レベルですが、要素が増えるほど性能は線形に劣化 します。

なぜわざわざ連結リストか

ハッシュテーブルは O(1) ですが、

ハッシュ値の計算
内部配列の確保（最低 11 要素分など）
バケット衝突の処理

といった固定オーバーヘッドを持ちます。要素が 2〜3 件しかないキャッシュや属性バッグでは、線形探索のほうが実時間で速いケースがある——これが ListDictionary の存在理由です。

ボックス化と型安全

非ジェネリックなのでキー・値ともに object。値型はボックス化されます。新規コードでは Dictionary<TKey, TValue> または 要素数が極端に少ないなら (Key, Value)[] の配列 で十分なことがほとんどです。

使いどころ

数件しか要素が入らない属性バッグ：例えばパーサのトークン属性、設定の局所オーバーライドなど。
HybridDictionary 経由での利用：直接使うより、要素数で切り替わる HybridDictionary を経由する設計が想定されていました。
レガシー API 互換：既存コードが ListDictionary を返す場合。

実務では、要素数が分かっているなら 配列＋線形探索を自前で書くか、最初から Dictionary<TKey, TValue> を選ぶのが分かりやすく、わざわざ ListDictionary を選ぶ理由は薄いです。

注意点

線形探索なので大規模データには絶対に使わない：100 件、1000 件と入れ始めると Dictionary<TKey, TValue> との差は致命的になります。
スレッドセーフでない：並行アクセスは別途ロックが必要。
キーは null 不可。

まとめ

ListDictionary は 単方向連結リストで実装された辞書。すべての操作が O(n)。
IDictionary / ICollection / IEnumerable を実装。
要素数が極小（〜10 件程度）のときに Hashtable の固定オーバーヘッドを避ける目的で設計された。
新規コードでは Dictionary<TKey, TValue> を選ぶのが基本。ListDictionary を選ぶ積極的理由はほぼない。

ListDictionary とは