【C#】Dictionary, HashSet, Hashtable, SortedDictionary, SortedSetの違いをそれぞれ解説(ハッシュテーブル or 2分探索木)

はじめに

今回はDictionary, HashSet, Hashtable, SortedDictionary, SortedSetという似たようなコレクションについて取り上げたいと思います。

はじめに
データ構造
使用例
HashSetとDictionaryの違い
Hashtable
SortedDictionaryとSortedSetの違い
参考

データ構造

型	データ構造
`Dictionary`	ハッシュテーブル
`HashSet`	ハッシュテーブル
`Hashtable`	ハッシュテーブル
`SortedDictionary`	2分探索木
`SortedSet`	2分探索木

ハッシュテーブルを利用していると以下の特徴があります。

順序が保証されない
追加・削除・検索がO(1)と高速
メモリ使用が大きい

2分探索木を利用していると以下の特徴があります。

順序が保証される
追加・削除・検索がO(log n)かかる
メモリ使用が少ない

使用例

// Dictionary<TKey, TValue>
// データ構造：ハッシュテーブル
// 非順序付き辞書
var dictionary = new Dictionary<int, int>();
            
// O(1)
dictionary[0] = 1;
var value = dictionary[0];
            
            
// HashSet<T>
// データ構造：ハッシュテーブル
// 非順序付き辞書
var hashset = new HashSet<int>();

// O(1)
hashset.Add(10);
var isContain = hashset.Contains(10);
            


// Hashtable
// 補足：objectを使って何でも入るやべー奴, Microsoftが非推奨してる, Dictionaryを使おう
// データ構造：ハッシュテーブル
// 非順序付き辞書
var hashtable = new Hashtable();
            
// O(1)
hashtable.Add(1, 1);
hashtable.Add("key", "value");
hashtable.Add("key2", 10);
object x = hashtable[1];
            


// SortedDictionary
// データ構造：2分探索木
// 順序付き辞書
var sortedDictionary = new SortedDictionary<int, int>();
            
// O(log n)
sortedDictionary[0] = 1;
var z = sortedDictionary[0];
            


// SortedSet<T>
// データ構造：2分探索木
// 順序付き辞書
var sortedSet = new SortedSet<int>();
            
// O(log n)
sortedSet.Add(10);
isContain = sortedSet.Contains(10);

HashSetとDictionaryの違い

HashSet クラスは数学の集合モデルに基づいており、Dictionary や Hashtable コレクションのキーにアクセスするのと同じような高パフォーマンスの set 操作を行えます。簡単に言えば、 HashSet クラスは値のないコレクションと Dictionary 考えることができます。

https://learn.microsoft.com/ja-jp/dotnet/api/system.collections.generic.hashset-1?redirectedfrom=MSDN&view=net-7.0

原理的に言うとValueのないハッシュテーブルを用いているというわけですね。
ですので以下のように重複できない&非順序になっています。