ハッシュ わかりやすく

名札がますの番号を決める

前のレッスンでは、並んだ値を探すには一つずつ見ていくか、並べかえた索引を使う必要がありました。では、値そのものを見てますの番号を決められたらどうでしょうか。名前の文字でますを決めるようにです。
値を入れるとますの番号が出てくる小さな計算を、一つ決めておくのです。この計算をハッシュ関数と呼びます。最初のレッスンで見た辞書も、中をのぞくとこの方法で動いています。

値を押してみましょう。計算がますの番号を決め、そのますにすっと入ります。

値ごとに、ますがすいすい決まりました。どこに置くかを悩む必要はありません。計算が場所を教えてくれるからです。
同じ値をもう一度入れても、計算の結果はいつも同じますです。だから、場所がばらばらになりません。では、探すときにも同じ計算を使えばよいのではないでしょうか。

計算して、すぐそのますへ

探すときも、秘密は同じです。探す値を同じ計算に入れてますの番号を求め、そのますへまっすぐ行けばよいのです。ますを一つずつ見ていく必要はありません。
入れるときに使った計算と探すときに使う計算が同じなので、入れておいたますと探すますがぴったり合います。だから一回でたどり着きます。

探す値を押してみましょう。同じ計算でますの番号が出て、見ていかなくてもそのますへすぐに飛びます。

見ていかなくても、すぐに着きました。ますが百個でも一万個でも、かかる手間はほとんど同じです。計算一回、ジャンプ一回で終わるからです。
これがハッシュの速い理由です。並べかえた索引が二十回ほどのぞく必要があったのに対して、ハッシュはたいてい一回で終わります。ところが、気になる点が一つあります。違う二つの値の計算結果が同じだったら、どうなるでしょうか。

二つが同じますへ向かう

計算は、同じ値にはいつも同じますを教えてくれますが、値が違えばますも必ず違うとはかぎりません。ますの数は決まっているのに、値はずっと多いことがあるからです。
そのため、違う二つの値がたまたま同じますを受け取ることが起きます。一つのますに二つが入ろうとするのです。このように同じますをめぐってぶつかることを、衝突といいます。

二つの値を順に押してみましょう。計算結果が同じなので、二つが同じますへ行ってぶつかります。

同じますをめぐって、二つがぶつかりました。一つのますにはふつう一つしか入らないのに、二つが同時に来たので問題です。
だからといって、ハッシュをあきらめることはありません。計算をうまく選べば衝突はまれで、ほかはやはり一回で速くすみます。だから、衝突が起きたときだけ別に処理すればよいのです。どう処理するのかを見てみましょう。

衝突は別に処理する

衝突を解く道は、大きく二つあります。一つは、一つのますにいくつかの値をまとめて入れる方法です。ますごとに小さな一覧を置き、ぶつかった値をそこに並べて入れます。
もう一つは、隣のますへずらす方法です。元のますがふさがっていたら、空いている次のますを探してそこに入れます。どちらの方法でも値をなくさず、あとでまた探し出せます。

処理の方法を選んで押してみましょう。一つのますにまとめるか、隣のますへずらして衝突を解きます。

衝突がきれいに解けました。まとめても隣へずらしても、値は安全に場所を得ました。
探すときも同じ規則にしたがえば、衝突した値もちゃんと探し出せます。ただ、ますがほとんど埋まると衝突が増えるので、埋まりきる前にますを増やして並べ直します。衝突はたまにしか起きず、処理もかんたんなので、ハッシュはやはり速くて頼もしいのです。

まとめ

一言でまとめるとこうです。ハッシュは、値を見て計算でますの番号を決めます。入れるときはそのますに入れ、探すときは同じ計算でそのますへ行きます。だから、見ていかなくても一回でたどり着きます。
たまに違う値が同じますへ向かう衝突が起きたら、別に処理します。一つのますにまとめるか、隣のますへずらせばよいのです。計算ですぐに探すこと、それがハッシュです。

要点を順に押して振り返りましょう。（計算でますを決める → 同じ計算ですぐ探す → 同じますでの衝突 → 衝突は別に処理）

これで、値を計算ですぐに探す方法がわかりました。場所を一つずつ見ていくもどかしさが、計算一回で解けたのです。
でも、ハッシュにもできないことがあります。ますが値の大きさに関係なく散らばっているので、「あ」から「う」までのように範囲で探したり、順番に並べたりすることには使えません。次のレッスンでは、順番を守りながらすばやく探せる入れ物、ツリーに出会います。