Hash Tableはデータをハッシュ関数で変換したキーの示すテーブル(表)に埋め込むデーター構造です。
5個のハッシュテーブルの場合
________
|________| ← キー0のデータ
|________| ← キー1のデータ
|________| ← キー2のデータ
|________| ← キー3のデータ
|________| ← キー4のデータ
ハッシュ関数
ハッシュ関数とキーの決め方について説明します。
このハッシュ関数は自分で決めれますが、自分の好きな方法は管理したい情報の一部を数値化して、それをテーブルの数で割るという方法です。
僕の場合は...
例えば、"Astrostory"という人の情報を管理したいときは、ord("A") + ord("s") ... ord("y")と足し合わせたものをテーブルの数で割ります。
そもそもの情報にint型があるときはそれをテーブルの数で割ります。
まとめると
データ → |ハッシュ関数| → キー
*キーは(後で説明するケースをのぞいて)ハッシュ関数の代入結果
となります。
テーブルに追加
テーブルにデータを追加する方法を説明します。
基本的にはハッシュ関数で得たキーの値のテーブルにデータを突っ込みます。
ですが、上記のハッシュ関数を用いてサイズ5で[24,9]のキーを得ると同じキーになってしまいます。これを衝突といいます。
衝突した時の対策は主にこの3つです。
1、テーブルの数を増やす
2、次のキーに変える
3、同じキーのなかにリストや連結リストなどで無理やりつないでいれる
連結リストについて知りたい方はこちらをどうぞ。
検索方法
検索の方法について説明します。
検索時には自分がどの方法でテーブルに入れたかが大切になります。
具体例として[10,9,7,1,14]を上記のハッシュ関数でサイズが5のハッシュテーブルに入れたと仮定します。
さて、4が衝突していますので、上の3つの方法のいずれかで対策したものとしてそれぞれみていきましょう。
1
この場合はテーブルの数を増やしているので、新しいテーブルの数で割って変更後の新しいキーが必要になります。今回だと[0,9,7,1,4]となって検索完了です。
2
衝突が起こらなかった時のハッシュキーはそれぞれ5で割って、[0,4,2,1,4]となります。そのハッシュキーの場所を探して、もし他のデータが入っていた場合は次のキー(+1)を探します。これを見つかるまでループで行えば検索完了です。
3
この場合のハッシュキーはそれぞれ5で割って、[0,4,2,1,4]となります。このキーの中でループ構文を使って目的のデータにたどりつけば検索完了です。
なぜ便利
衝突が起こってめんどくさそうですが、これとても検索がスマートなんです。
例で考えてみてください。
仮に500個のデータを50個のテーブルに入っている場合、運が良ければ一回のハッシュ関数の計算で、運が悪くても50回の線形探索(2)か10回の線形探索(3)で見つかるんです。
500個のデータを線形探索するより効率的です。