Hashing/Hash Table

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

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

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

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

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

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

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

例：検索の仕方

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

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

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

（１）チェイン法

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

（２）オープンアドレス法

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