ハッシュテーブル
出典: フリー百科事典『ウィキペディア（Wikipedia）』
ハッシュテーブル (hash table) は、キーと値の組（エントリと呼ぶ）を複数個格納し、キーに対応する値をすばやく参照するためのデータ構造。ハッシュ表ともいう。あるハッシュテーブルに格納されている各エントリは、互いに異なるキーをもつ必要がある。通常、エントリの検索や追加は要素数によらず定数時間O(1)で行える。しかしハッシュ関数の選び方によっては、最悪の場合O(n)かかってしまう。
[編集] 実装方法
一つの実装例を示す。まず、ルート配列と呼ばれる要素数 N の配列を一つ用意する。ルート配列の各要素は、リスト（便宜上エントリリストと呼ぶ）とする。エントリリストには、少数のエントリを格納する。
エントリを格納する場合、エントリのキーをもとにハッシュ関数を用いてハッシュ値を生成する。ハッシュ関数は 0 から N - 1 までの整数値を生成するものであって、一様な分布と高速な計算が要求される。ハッシュ値を i とするとき、ルート配列上の i 番目のエントリリストにこのエントリを格納する。異なるキーが同じハッシュ値になることを衝突 (collision) と呼び、それらのエントリは同一のエントリリストに格納される。
あるキーをもつエントリを検索する場合、そのキーからハッシュ値を生成する。ハッシュ値を j とするとき、ルート配列上の j 番目のエントリリストに入っているエントリを一つずつ検索し、キーが一致しているものを取り出す。ルート配列上のエントリリストが高速でアクセスできる必要がある。
[編集] 主要プログラミング言語におけるハッシュテーブルの実装
- Javaにおける
HashMapLinkedHashMapHashtable - AWK、Perlにおける連想配列
- Pythonにおける辞書
- C++のSTLの
hash_map（非標準）、unordered_map（次期標準） - RubyのHashクラス
- CLI (Common Language Infrastructure) の
System.Collections.Hashtable、System.Collections.Specialized.ListDictionary、System.Collections.Specialized.HybridDictionary、System.Collections.Generic.Dictionary<TKey, TValue>
