ハッシュテーブルはなぜ一瞬で見つかるのか

辞書(連想配列)に map["りんご"] と書くと、何万件データが入っていてもほぼ一瞬で値が返ってきます。先頭から1件ずつ探しているわけではありません。ハッシュテーブルは、探す代わりにキーから「しまう場所の住所」を計算してしまうデータ構造です。

下の図1で実際に試せます。好きなキーを入力して「格納する」を押すと、住所が計算されて棚に収まる様子が見られます。

「探す」のではなく「計算する」

図1のポイントは、格納でも探索でもやることがまったく同じだということです。キーをハッシュ関数に通して棚番号を計算する — それだけ。探すときも先頭から見ていく必要はなく、計算した棚を1つ開けるだけで済みます。データが100件でも100万件でも計算の手間は変わらないので、平均してO(1)(ほぼ一定時間)で見つかります。

そしてもう1つ大事なのが、棚が空だったときです。「無い」と答えるのにも他の棚を見る必要がありません。あるならこの棚にしか無いと分かっているからです。

同じ棚にぶつかったら? — 衝突とチェイン法

棚の数は有限なので、違うキーが同じ棚番号になることがあります。これが衝突(コリジョン)です。図1では衝突したアイテムを同じ棚に鎖のようにつなげてぶら下げています。これがチェイン法で、探すときは棚の中の短い鎖だけを順に見ます。

もう1つの代表的なやり方がオープンアドレス法で、こちらは「先客がいたら隣の空き棚にずらして入れる」方式です。鎖を作らないぶんメモリ効率は良いのですが、棚が混んでくると空きを探す移動が長くなります。どちらの方式でも、棚に対してデータが増えすぎたら棚の数を増やして全部入れ直します(リハッシュ)。

まとめ

ハッシュテーブルが一瞬で見つかる理由は、「探す」作業を「計算する」作業に置き換えているからでした。キーから住所を直接計算するので、データ量が増えても手間が増えない。衝突という弱点はありますが、チェイン法などでうまくさばけば平均O(1)を保てます。次に map[key] と書くときは、裏側でこの計算機が回っている様子を思い出してみてください。