ハッシュテーブル

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

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

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

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

例:

以下のデータを格納したい.

実データ
6
12
18
10
2
14
15
17

ハッシュのルール(ハッシュ関数

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


配列番号
0
1
2
3
4
5
6
 データ
14
15
2
10
18
12
6

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


例:検索の仕方

ハッシュ関数により実データが下記のように格納されている.


番号
0
1
2
3
4
5
6
 データ
14
15
2
10
18
12
6

もし,12というデータを探したいとき,12÷7= 1...5 より,5番目の配列を探せばよい.

上述の例で は、データを単なる変数にしていますが、実際には検索キーを含んだ構造体等が格納されます。


ハッシュテーブルの利点

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

ハッシュテーブルの応用

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

注意事項

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

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

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

(1)チェイ ン法 

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

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

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



オープンアドレス法にお けるデータ探索の方法

 

オープンアドレス法では、以下のいずれかの条件になるまで、 再ハッシュを行って探索を続けます。(以下の条件のいずれかになると探索を終了します)

  • 該当するデータが見つ かった

  • 「空」のバケットに移動した

  • ハッシュテーブルを一巡した

オープンアドレス法では、ハッシュテーブルのサイズ分だけのデータを格納することができます。

オープンアドレス法の削除処理の注意事項
オープンアドレス法では、同じハッシュ値を持つデータを削除する場合に工夫が必要です。同じハッ シュ値を持つ複数のデータを格納している状態で、本来のハッシュ値の値を「削除」と扱ってしまうと、他のデータを見つけることができなくなるからです。 
そこで、オープンアドレス法では、データの状態を 
  • 空(カラ) 「ー」 ・・・ 初期状態。一度も使われたことのないバケッ ト。
  • 削除済み「☆」 ・・・ データを保持したことがあ るが、削除されている状態のバケット
  • データあり
の3つの状態で管理します。ここで重要なのは、「空」と「削除済み」とは意味が違うということで す。

Comments