| |
|
ハッシュテーブルはキーと値のペア(エントリ)を複数格納し、キーに対応する値をすばやく参照するためのデータ構造である。
ある1個のハッシュテーブルに格納されている各エントリは、互いに異なるキーを持つ必要がある。
リストを1つ用意する。これを便宜上ルートリストと呼ぶ。
ルートリストには予めn個のリスト(便宜上エントリリストと呼ぶ)を格納する。
エントリリストには、エントリを複数格納する。
エントリを格納する場合、エントリのキーをもとにハッシュ関数を用いてハッシュ値を生成する。このハッシュ関数は0からn-1までの整数値を生成するものである。ハッシュ値をiとしたとき、ルートリスト上のi番目のエントリリストにこのエントリを格納する。
あるキーと値が等しいエントリを検索する場合、そのキーからハッシュ値を生成し、その値をjとしたときに、ルートリスト上のj番目のエントリリストに入っているエントリを1つづつ検索し、キーが一致しているものを取り出す。方法