今回のテーマ

• ハッシュテーブル

C# の HashTable クラス

ハッシュテーブルはデータ構造の分野に分類されるものであり、C# に限らない話であるが、C# には System.Collections.Hashtable クラスがあって紛らわしいのでこれについて触れておく。

まず、Hashtable クラスは Dictionary クラスによって置き換えられたので、現在は使われない。Hashtable クラスではキー/値に object 型をとって Dictionary と同等の機能を提供している。Hashtable クラスは Dictionary クラスより前からあり、当時は C# にジェネリックが導入されていなかった。そのため、毎回キャストが必要になり面倒だが、現在はジェネリックとそれを使ったより高度な Dictionary クラスがあるので、使う必要はなく使用は非推奨である。

C# で「ハッシュテーブル」を使ったクラスは Dictionary と HashSet である（他にもあるかもしれない）。これらの特徴は「重複を許さない」ことである。Dictionary のキー項目は重複できないし、HashSet は要素の重複を許可しない。

「ハッシュテーブル」の意味

データベースのキー項目など、コンピュータにおいては「重複を許さない」ことは大きな意味がある。管理上、データの整合性においても重要だが、「重複を許さない」ことで検索性能が飛躍的に向上する。

ハッシュテーブルはデータの格納方法に特徴がある。このデータ格納方法では「検索対象のデータ数がいくら増えても、検索したい値がデータに含まれているかを探すための計算量が一定になる」つまり、O(1) となる優れた方法です。ただし、以下の留保事項があります。

1. ハッシュテーブル（の配列）は隙間（何もデータが含まれない要素）ができるので、メモリを余計に使う
   • つまり、メモリに余裕がある状況で有効である
2. ハッシュ値を求めるハッシュ関数が返す値に偏りがないこと
   • C# では ComputeHash() メソッドが用意されている

参照:

• ハッシュメニュー

備考

ちなみに線形探索の計算量は O(n) です。つまり、検索対象のデータ数が増えると、検索に必要な計算量は一次関数的に増えます。