考え方
データそのものから格納位置を計算し、その番地を直接参照します。
ハッシュ法探索
ハッシュ法は、ハッシュ関数で求めた番地を使ってデータの位置を直接見つける探索法です。
ハッシュ法
配列やリストの中から目的のデータを探す方法の1つがハッシュ法です。格納時と探索時に同じハッシュ関数を使うことで、 目的のデータがありそうな位置をすばやく絞り込めます。
このページの例
ハッシュ関数として key mod 10 を使い、0〜9 の10個の番地に格納します。
ハッシュ法の探索例
たとえばデータ 12 を格納するとき、12 mod 10 = 2 なので、配列の位置 2 に置きます。
探索するときも同じ計算を行えば、最初に確認すべき位置をすぐに求められます。
-1 は、まだ何も格納されていない空の場所を表す初期値です。
h(12) = 12 mod 10 = 2
0-1
1-1
212
3-1
4-1
5-1
6-1
7-1
8-1
9-1
ハッシュ法の衝突
異なるデータから同じハッシュ値が出ると衝突（コリジョン）が起きます。たとえば 22 も 22 mod 10 = 2 となり、
12 と同じ位置にぶつかります。
オープンアドレス法
衝突したら次の番地へ進み、空いている場所を順番に探します。ここでは線形探索（+1）を使います。
チェイン法
同じ番地のデータを連結して保持します。探索時はそのバケットのリストを順にたどります。
ハッシュ法シミュレータ
ハッシュテーブル
探索計算量
ハッシュ法の探索計算量は、オープンアドレス法でもチェイン法でも、平均は O(1)、最悪は O(N) です。
オープンアドレス法
平均: O(1) / 最悪: O(N)
チェイン法
平均: O(1) / 最悪: O(N)
ハッシュ値がうまく分散していれば、調べる場所は少なくて済むため平均は O(1) です。
ただし衝突が多いと、オープンアドレス法では配列を長くたどり、チェイン法では1つのバケットのリストが長くなるため、
最悪は O(N) になります。