Hashing/Hash Table
教科書では「ハッシュ法」として、探索アルゴリズムの一つとし て取り上げていますが、本講義ではデータ構造の1種である「ハッシュテーブル」として取り上げます。
ハッシュ法とハッシュ テーブルとは?
ハッシュ法:データを格納する位置をきめるルール(ハッシュ関数)を用意し,それ関数により得られた値をそのデータを格納するアドレスとする。
ハッシュ テーブル:ハッシュ法に従ってデータを保存するデータ構造。連想配列とも呼ばれる。
ハッシュテーブルの利点
データの追加や検索(探 索)に対して、検索キーに基づいてデータ数にかかわらず一定時間で行えるという利点があります。つまり、検索キーワードについてのデータ検索が高速に行え るということです。
ハッシュテーブルの応用
現在、C++やJavaなどの言語において、ハッシュテーブルを実装したクラスが用意されていま す。
ハッシュ関数
ここでは計算しやすい(わかりやすい)ように,実データを7で割ったときの余りを格納位置とする.
各データを7で割った余りを格納する配列番号とする。
例:検索の仕方
ハッシュ関数によりデータが下記のように格納されている.もし,12というデータを探したいとき,12÷7= 1...5 より,5番目の配列を探せばよい.
注意事項
ハッシュ関数において は,一般的には, 素数で割った余りをハッシュ値 にしておくとデータのばらつきが良くなり、衝突が少なくなるといわれています.
衝突の問題とチェイン法/オープンアドレス法
教科書のハッシュ関数(13で割った余りをハッシュ値とする)の場合,ハッシュ値が同じになることがある(衝突).その場 合の解決策として,チェイン法とオープンアドレス法がある.
(1)チェイ ン法
ハッシュ値が衝突した場合は,それらを線形リストとして管理する方法。
(2)オープンアドレス法
ハッシュ値が衝突した場合は,もう一度ハッシュ値を求めなおす方法です.教科書の例では、線形探査法として値に+1を足して再計算し、 ハッシュ値を求めています。(厳密に言うと、単純にハッ シュ値に1を足しているのではないということです。)