なふだで すぐ さがす、ハッシュ

なふだが ばしょの ばんごうを きめる

まえに あたいが
ばしょの ばんごうで ならんでいるのを まなびました。
さがすには ばしょを ひとつずつ みる ひつようが ありました。
でも あたい じたいを みて
ばしょの ばんごうを きめられたら どうでしょう?
なまえの もじで ばしょを きめるように。
あたいを いれると ばんごうが でてくる
ちいさな けいさんを ひとつ おくのです。
その けいさんを ハッシュかんすうと いいます。

あたいを おしてみて。けいさんが ばしょの ばんごうを きめ、その ばしょに すっと はいります。

あたいごとに ばしょが さっと きまりましたね。
どこに おくか なやむ ひつようが ない。
けいさんが ばしょを おしえるからです。
おなじ あたいを また いれても
けいさんの けっかは いつも おなじ ばしょ。
だから ばしょが ばらつきません。
なら さがすときも
おなじ けいさんを つかえば いいのでは?

けいさんして すぐ その ばしょへ

さがすときも ひみつは おなじ。
さがす あたいを おなじ けいさんに いれて
ばしょの ばんごうを だせば
すぐ その ばしょへ いけば いい。
ばしょを ひとつずつ みる ひつようが ない。
いれるときの けいさんと
さがすときの けいさんが おなじだから
いれた ばしょと さがす ばしょが ぴったり。
だから いっぱつで とどきます。

さがす あたいを おしてみて。おなじ けいさんで ばんごうが でて、みていかず その ばしょへ すぐ ジャンプ。

みていかず すぐ つきましたね。
ばしょが ひゃくこ でも まんこ でも
かかる てまは にたような もの。
けいさん いっかい、ジャンプ いっかいで おわり。
これが ハッシュの はやい わけです。
でも ひとつ きになることが あります。
たがいに ちがう あたい ふたつが
けいさんの けっかが おなじだと どうなる?

ふたつが おなじ ばしょへ いく

けいさんは いつも おなじ ばしょを おしえますが
あたいが ちがっても ばしょまで ちがうとは かぎりません。
たがいに ちがう あたい ふたつが
たまたま けいさんの けっかが おなじに なることが ある。
すると どちらも おなじ ばしょへ いく。
ひとつの ばしょに ふたつが はいろうとする。
こうして おなじ ばしょを めぐって ぶつかるのを
しょうとつと いいます。
しょうとつは まれですが たしかに おきます。

ふたつの あたいを じゅんに おしてみて。けいさんの けっかが おなじで、ふたつが おなじ ばしょへ いって ぶつかります。

おなじ ばしょを めぐって ふたつが ぶつかりましたね。
ひとつの ばしょには ふつう ひとつしか はいらないので
ふたつ いちどに くると もんだいです。
だからといって ハッシュを あきらめられません。
しょうとつは たまに いっかいで、
のこりは あいかわらず いっぱつで はやい。
だから しょうとつが おきたときだけ
ちょっと べつに しょりすれば いい。
どう しょりするか みてみましょうか?

しょうとつは べつに しょりする

しょうとつを とく みちは おおきく ふたつ。
ひとつは ひとつの ばしょに ふたつを まとめて いれること。
ばしょに ちいさな たばを おいて
ぶつかった あたいたちを そこに ならべて いれます。
もうひとつは となりの ばしょへ ずらすこと。
もとの ばしょが ふさがっていたら
あいている となりの ばしょを さがして そこに いれる。
どちらでも あたいを なくさず
あとで また さがせます。

しょりの やりかたを えらんで おしてみて。ひとつの ばしょに まとめるか、となりの ばしょへ ずらして しょうとつを とく。

しょうとつが きれいに とけましたね。
まとめても となりへ ずらしても
あたいは あんぜんに ばしょに おさまりました。
さがすときも おなじ きまりに したがえば
しょうとつした あたいも うまく さがせます。
しょうとつは たまにで しょりも かんたんなので
ハッシュは あいかわらず はやくて たよれます。
では ぜんたいを いちど まとめましょう。

まとめて みましょう

ひとことに まとめると こうです。
あたいを みて けいさんで ばしょの ばんごうを きめる。
いれるときは その ばしょに いれ、
さがすときは おなじ けいさんで その ばしょへ いく。
だから みていかず いっぱつで とどく。
ときどき ちがう あたいが おなじ ばしょへ いく
しょうとつが おきたら べつに しょりする。
まとめて いれるか となりの ばしょへ ずらせば いい。
けいさんで すぐ さがす、それが ハッシュです。

かなめを じゅんに おして ふりかえって。(けいさんで ばしょを きめる → おなじ けいさんで すぐ さがす → おなじ ばしょの しょうとつ → しょうとつは べつに しょり)

これで あたいを けいさんで すぐ さがす
かしこい やりかたが わかりました。
ばしょを みていく もどかしさが
けいさん いっかいで すっきり とけましたね。
いれると さがすを はやくする
こういう うでが データを あつかう ちからです。
つぎは どんな やりかたで
あたいを もっと よく ためて さがせるか
いっしょに つづけて みていきましょう。