Hashing/Hash Table

教科書では「ハッシュ法」として、探索アルゴリズムの一つとし て取り上げていますが、本講義ではデータ構造の1種である「ハッシュテーブル」として取り上げます。

ハッシュ法とハッシュ テーブルとは?

ハッシュ法:データを格納する位置をきめるルール(ハッシュ関数)を用意し,それ関数により得られた値をそのデータを格納するアドレスとする。

ハッシュ テーブル:ハッシュ法に従ってデータを保存するデータ構造。連想配列とも呼ばれる。

ハッシュテーブルの利点

データの追加や検索(探 索)に対して、検索キーに基づいてデータ数にかかわらず一定時間で行えるという利点があります。つまり、検索キーワードについてのデータ検索が高速に行え るということです。

ハッシュテーブルの応用

現在、C++やJavaなどの言語において、ハッシュテーブルを実装したクラスが用意されていま す。

ハッシュ関数

ここでは計算しやすい(わかりやすい)ように,実データを7で割ったときの余りを格納位置とする.

各データを7で割った余りを格納する配列番号とする。

例:検索の仕方

ハッシュ関数によりデータが下記のように格納されている.もし,12というデータを探したいとき,12÷7= 1...5 より,5番目の配列を探せばよい.

注意事項

ハッシュ関数において は,一般的には, 素数で割った余りをハッシュ値 にしておくとデータのばらつきが良くなり、衝突が少なくなるといわれています.


衝突の問題とチェイン法/オープンアドレス法

教科書のハッシュ関数(13で割った余りをハッシュ値とする)の場合,ハッシュ値が同じになることがある(衝突).その場 合の解決策として,チェイン法とオープンアドレス法がある.

(1)チェイ ン法

ハッシュ値が衝突した場合は,それらを線形リストとして管理する方法。

(2)オープンアドレス法

ハッシュ値が衝突した場合は,もう一度ハッシュ値を求めなおす方法です.教科書の例では、線形探査法として値に+1を足して再計算し、 ハッシュ値を求めています。(厳密に言うと、単純にハッ シュ値に1を足しているのではないということです。)