【C#】コレクションの内部実装

コレクションの内部実装csharptan.wordpress.com

配列リスト

個数不定のデータを持つための一番手っ取り早い方法は、事前に配列を確保しておいて、状況に応じて確保しなおす方法です。

List<T> や Stack<T> で内部的にやってることはほぼこれだけ

循環バッファー

循環バッファー（circular buffer）は、 Queue<T> の内部的な仕組み

連結リスト (Linked List)

連結リスト（linked list）は、 LinkedList<T> の内部的な仕組みです。

ハッシュ テーブル

Dictionary<TKey, TValue> と HashSet<T> の内部ではハッシュ テーブル（hash table）を使っています。

キーに対応する何らかの整数値を作れれば、普通の配列を使って辞書を実現できます。その「何らかの整数値」というのがハッシュ値（hash value: 直訳だと「ごちゃまぜにした値」）です。

二分探索ツリー

SortedDictionary<TKey, TValue> や SortedSet<T> の内部では、二分探索ツリー（binary search tree）というものを使っています。

検索にかかる時間はおおむねツリーの高さに比例しますが、平均的には、要素数nに対して、ツリーの高さはlog2 nになります。つまり、 O(log n) での検索ができます。

整列済み配列（二分探索）

配列を整列済みに保っておけば、二分探索という高速な検索アルゴリズムが使えます。これを応用したのが SortedList<TKey, TValue> です。

この方法を使えば、最悪でも log2 n 回の繰り返しで検索できます。