メインコンテンツへスキップ
見出し画像

ハッシュ表の衝突を空き場所までたどる

    解き方

    ハッシュ表は、キーから計算した格納位置を手掛かりにデータを探す構造です。異なるキーが同じ位置になることを衝突と呼びます。衝突は計算の失敗ではなく、対応方法を決めて扱うものです。ここでは、次の位置を順番に調べる線形探査法を使います。

    手順を追う例

    要素番号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枠を確認したら停止するなど、探査回数の上限も必要です。暗号用のハッシュと違い、ここでの目的は格納位置を決めて探しやすくすることです。

    IPA 科目Bサンプル問題(出題範囲・形式の参考)

    本記事の例と確認問題は独自に作成しています。

    科目Bの目次

    この記事が参加している募集

     
     
    ITの知識ゼロから、基本情報技術者試験の勉強を始めました📚 わからなかった言葉や問題を、自分の言葉でまとめる備忘録です。 基礎からコツコツ学んで、いつかは応用情報にも挑戦したいです! 一緒に学んでいただけたらうれしいです🌱

    あなたへのおすすめ