STAGE 3
ハッシュ表
名前から棚の番号を計算する
🎯 ミッション
ハッシュ表のしくみ(ハッシュ関数・衝突)と、得意なこと・苦手なことを説明できるようになろう。5人以上を棚に入れて1人を探し、確認クイズに全問正解すれば合格。
未達成

ねこ博士
二分探索で O(log N) まで速くなった。もっと速くできるだろうか。究極は、人数によらず一発で行けることだね。

うさ美
名前から、その人がいる場所が直接分かればいいんですけど……。名簿の何番目にいるかは、調べないと分からないですよね。

ねこ博士
そこで発想を変える。「どこにいるかを調べる」のではなく、「名前から置き場所を計算で決めて、そこに置いておく」。探すときも、同じ計算をすれば置き場所が分かる。

ねこ博士
たとえば、棚を10個用意して、「名前の文字を1つずつ番号(文字コード)に直して足し、10で割った余りを棚の番号にする」と決めておく。

うさ美
計算は毎回同じだから、「たろう」は置くときも探すときも同じ棚に行き着く。探すときに、ほかの棚を見る必要がないんですね。

ねこ博士
そう。名前などから番号を計算する関数をハッシュ関数、その番号で決まった棚にデータを置く仕組みをハッシュ表と呼ぶ(hash は「細かく刻んで混ぜる」という意味)。
ハッシュ関数の例:名前の各文字の番号(文字コード)を足し、棚の数で割った余り
置く:番号を計算して、その棚に入れる / 探す:同じ計算をして、その棚だけを見る

うさ美
でも、違う名前が同じ棚の番号になることもありますよね。棚が10個しかないなら、11人目は必ずどこかの棚で2人目になります。

ねこ博士
それを衝突と呼ぶ。衝突は避けられないので、対策を決めておく。一番簡単なのは、同じ棚の中に小さな列を作って、そこに並べておくやり方だ。探すときは、その棚の列だけを順に見ればいい。

うさ美
棚の中の列が長くなったら、結局その列を線形探索することになりますね。

ねこ博士
そう。だから、データの数に対して棚を十分に用意する。データの数 ÷ 棚の数を負荷率と呼び、これが1くらいを超えたら、棚の数を2倍に増やして全部を置き直す、というように管理する。ハッシュ関数が名前をうまくばらけさせ、負荷率が小さく保たれていれば、1つの棚の列は平均して数人だけ。だから、探す手間は人数によらず、平均で O(1) になる。

うさ美
置き直すときは、全員分の計算が要るので大変そうです。

ねこ博士
その1回は O(N) かかる。でも、棚を2倍ずつ増やせば、置き直しはたまにしか起きないので、ならすと1人あたりの手間は小さい。これは、いろいろなプログラミング言語の「辞書」や「連想配列」と呼ばれる道具の中身として、広く使われている。

うさ美
ハッシュ表に苦手なことはありますか?

ねこ博士
ある。棚の番号はばらけるように計算しているから、並び順はめちゃくちゃになる。だから「五十音順に全員を表示する」「『か』で始まる人を全員探す」のような、順番や範囲を使う仕事には向かない。それなら、並んだ配列の二分探索のほうがいい。それから、ハッシュ関数がうまくばらけないと、1つの棚に集中して、最悪 O(N) になってしまう。
得意:ぴったり一致する1つを探す・入れる・消す(平均 O(1))
苦手:順番に並べる、範囲で探す。ばらけ方が悪いと最悪 O(N)
確認クイズ
Q1. ハッシュ表で、名前から探す手順は?
正解! 置くときと同じ計算で棚が決まるので、ほかの棚を見る必要がない。
Q2. ハッシュ表の「衝突」とは?
正解! 棚の数には限りがあるので、違う名前が同じ番号になるのは避けられない。同じ棚の中に列を作るなどして対処する。
Q3. ハッシュ表が苦手な仕事は?
正解! 棚の番号はばらけるように計算するので、並び順は保たれない。順番や範囲を使う仕事は、並んだ配列や木などのほうが向いている。