ハッシュ法 オープンアドレス ダブルハッシング法
ハッシュ法は検索アルゴリズムの一つ。 各データ(keyと呼ぶ)の挿入するべき位置をハッシュ関数を用いて求める。 ハッシュ関数で求めた値、ハッシュ値が配列の挿入するべき位置(インデックス)を示す。
ハッシュ関数 Hash(key)=key mod m ここでmをテーブルサイズとする。
弱点は、ハッシュ関数を用いて求めた値が以前に求めた値と重複する場合がある。 この時に、ダブルハッシュ法を用いる。 ダブルハッシュ法は、ハッシュ関数に一回目のハッシュ値とは別のテーブルサイズmのハッシュ関数を含めた関数 関数は、 H(key) = (h1(k) + j*h2(k))%m ここで、 h1(k) = key mod m h2(k) = 1 + key mod n n: mとは異なる値 j: 1(今回の場合) とする。
また、重複した場合にh1(k)からh2(k)分だけ位置を移動させることになることから、mとh2(k)が互いに素でないと挿入出来ない位置が生じます。これはmを素数としてh2(k)をmより小さい値にすることで回避することができる。
参考資料
