皆さんは、大量のデータの中から目的のデータを探す時、どのように探しますか？
例えば、図書館で特定の本を探したい時、本のタイトルを一冊ずつ確認していくのは大変ですよね？ そんな時に役立つのがハッシュ探索法です！
ハッシュ探索法とは？
ハッシュ探索法は、データをハッシュテーブルと呼ばれる特別な表に格納し、高速に検索するアルゴリズムです。
イメージとしては、図書館の本を著者名順ではなく、特別なルールに基づいて配置する感じです。
このルールをハッシュ関数と呼びます。ハッシュ関数は、データ（例えば本のタイトル）を受け取り、ハッシュテーブルの**特定の位置（インデックス）**を計算します。
ハッシュ探索法の仕組み
- ハッシュ関数でインデックスを計算: 探したいデータ（例えば「ハッシュ探索法入門」という本）をハッシュ関数に入力します。すると、ハッシュ関数は「15」というインデックスを返します。
- 計算されたインデックスの場所にアクセス: ハッシュテーブルの15番目の場所にアクセスします。
- データが存在するか確認: 15番目の場所に「ハッシュ探索法入門」の本があれば、探索成功です！
ハッシュ探索法のメリット
- 探索が高速: データ量が増えても、探索にかかる時間はほぼ変わりません！ これは、ハッシュ関数によって直接目的のデータに近い場所にアクセスできるからです。
ハッシュ探索法のデメリット
- 衝突の発生: 異なるデータがハッシュ関数によって同じインデックスに割り当てられることがあります。これを衝突と言います。
- 衝突の解決: 衝突が発生した場合は、別の方法でデータを格納する必要があります。例えば、同じインデックスにリストを作ってデータを繋げたり、空いている別の場所にデータを格納したりします。
ハッシュ探索法の例
例えば、学生のIDと名前を管理するシステムを考えてみましょう。
| ID | 名前 |
| 123 | 田中太郎 |
| 456 | 佐藤花子 |
| 789 | 鈴木一郎 |
ハッシュ関数として「IDを3で割った余り」を使うと、
- 田中太郎(ID:123)は、123 ÷ 3 の余りが 0 なので、インデックス 0 に格納されます。
- 佐藤花子(ID:456)は、456 ÷ 3 の余りが 0 なので、インデックス 0 に格納されます。 衝突発生！
- 鈴木一郎(ID:789)は、789 ÷ 3 の余りが 0 なので、インデックス 0 に格納されます。 衝突発生！
この場合、インデックス 0 にリストを作成し、[田中太郎, 佐藤花子, 鈴木一郎]のようにデータを格納することで衝突を解決できます。
まとめ
ハッシュ探索法は、大量のデータから目的のデータを高速に検索できる便利なアルゴリズムです。
ただし、衝突が発生する可能性があるため、衝突の解決策も合わせて理解しておくことが重要です
