
ハッシュ表の衝突を空き場所までたどる
解き方
ハッシュ表は、キーから計算した格納位置を手掛かりにデータを探す構造です。異なるキーが同じ位置になることを衝突と呼びます。衝突は計算の失敗ではなく、対応方法を決めて扱うものです。ここでは、次の位置を順番に調べる線形探査法を使います。
手順を追う例
要素番号0~6の7個の枠を用意し、すべて空とします。キーは正の整数で、ハッシュ値h(k)はkを7で割った余りです。衝突したら次の枠へ進み、6の次は0へ戻ります。削除は行わず、同じキーは二度登録しません。
10:余り3なので枠3へ格納。
17:余り3ですが枠3は使用中。枠4へ格納。
24:枠3と4が使用中なので枠5へ格納。
検索も同じ順番をたどります。17を探すなら、枠3の10を確認した後、枠4で17を見付けます。ハッシュ値だけではキーが一致したとは判断できません。
確認問題【オリジナル】
上の表へ、さらに31、38をこの順に登録します。それぞれ何番の枠に入りますか。その後、45を検索した場合、どの枠を順番に確認し、どこで「存在しない」と判断できますか。
答えと解説
31も38も余りは3です。31は枠3、4、5を通過して枠6へ、38は枠3、4、5、6を通過し、先頭に戻って枠0へ入ります。
45の検索順は3→4→5→6→0→1です。枠1が空なので、この条件では存在しないと判断できます。登録も検索も同じ探査順を使い、途中の枠を飛ばさないためです。
ただし削除を行う表では、単純に空へ戻すと検索を途中で止めてしまうことがあります。その場合は削除済みの印など別の管理が必要です。また全枠が埋まる場合に備え、最大7枠を確認したら停止するなど、探査回数の上限も必要です。暗号用のハッシュと違い、ここでの目的は格納位置を決めて探しやすくすることです。
本記事の例と確認問題は独自に作成しています。