ハッシュテーブルは平均 O(1) で検索できる強力なデータ構造。Pythonの dict や Java の HashMap の内部実装です。
日野 こむぎ
ハッシュって、Pythonのdictみたいなやつ?
藤森 さやか 先生
その通り!
ハッシュテーブルはキーから直接保存場所を計算するから、平均 O(1) で検索できる超高速なデータ構造なの。
青木 澪
鍵となるのがハッシュ関数。
キーを入力すると、配列のインデックスを返してくれるの。
例えばキー「apple」→ インデックス 3 のように。
桃井 すみれ
もし違うキーで同じ場所になったらどうするんですかぁ?
青木 澪
鋭いところに気づいたわね!
それを衝突(collision) と呼ぶの。
対策は主に2つあって、チェイン法(連結リストでつなぐ方法) と、オープンアドレス法(別の空きスロットを探す方法) ね。
藤森 さやか 先生
ハッシュ関数は値を均等に分散させることが大事なのよ。
偏ると衝突が増えて、性能が落ちちゃうの。
日野 こむぎ
じゃあ最悪どのくらいになるの?
青木 澪
全部の要素が同じインデックスに集中する最悪のケースだと O(n) になってしまうけど、実用上はほぼ O(1) と考えて良いわ。
藤森 さやか 先生
応用範囲は広くて、暗号化のSHA-256、データベースのインデックス、ブロックチェーンなど至るところで使われているの。
桃井 すみれ
いろんなところで使われてるんですねぇ♪えへへ、すごいですぅ!
確認クイズ
ハッシュテーブルで異なるキーが同じハッシュ値となる現象を何と呼ぶか。
- 衝突 (collision)
- オーバーフロー
- ボトルネック
- デッドロック
こたえを見る
正解: 1. 衝突 (collision)
異なるキーが同じハッシュ値 (インデックス) になる現象を 衝突 (collision) と呼びます。対策にはチェイン法やオープンアドレス法があります。