ハッシュについて

はじめに

P2Pの世界ではDHT(分散ハッシュテーブル)と呼ばれる技術に注目が集まっています。 DHTについては「分散ハッシュテーブル入門」を読んでいただくとして、その基礎になっているハッシュ (ハッシングという手法やハッシュテーブルというデータ構造を指す) について解説をしてみようと思います。

登場人物 - 電話帳とロボット

登場人物は電話帳とロボットの2人？です。電話帳はコンピュータのメモリやハードディスク、ロボットはCUPの喩えなんですが、あまり気にする必要はありません。

ロボットは電話帳を調べるのが仕事です。「10ページの3人目は誰？」と訊くと 1秒で「タナカさん。電話番号は…。住所は…」と答えてくれます。なかなか賢いですね。

線形探索 - 力技でがんばれ

今度は逆に「タナカさんの電話番号と住所は？」と訊いてみましょう。「1ページの1人目はヤマガタさん。タナカさんじゃない」「1ページの2人目はイトウさん。タナカさんじゃない」と9ページ分調べてからやっと「10ページの3人目はタナカさん。電話番号は…。住所は…」と答えます。実はあまり賢くなかったようです。

もし電話帳に10人しか載っていなかったとしたらどうでしょう (それは電話帳というより個人のアドレス帳ですけど)。 1人目で当たりかもしれないし、10人目でやっと当たりかもしれません。 1人を調べるのに1秒かかるとすると、平均で5秒です。このくらいなら我慢してもいいかな、という気がします。

電話帳に100人載っていたとすると平均で50秒、1000人だと500秒かかります。 500秒というと4分20秒です。これはちょっとなんとかしたいものです。

二分探索 - 電話帳ならではの作戦

個人のアドレス帳だから最初のページから順に調べなければいけないのですが、幸い電話帳はある規則に従って人名が並んでいます。ここでは単純に読みの50音順ということにしましょう。

ロボットに「イケダさんの電話番号と住所は？」と訊いてみます。ロボットは50音順に並んだ1000人の名前をどう調べるのでしょうか。

ロボットはまず500人目の名前を見ます。「500人目。ハラさん。イケダさんはもっと前」「250人目。サトウさん。イケダさんはもっと前」「125人目。カトウさん。イケダさんはもっと前」「63人目。クロダさん。イケダさんはもっと前」「32人目。オカダさん。イケダさんはもっと前」「16人目。ウチダさん。イケダさんはもっと前」「8人目。イトウさん。イケダさんはもっと前」「4人目。イシバシさん。イケダさんはもっと前」「2人目。アベさん。イケダさんはもっと後」「3人目。イケダさん。電話番号は…。住所は…」。それぞれに1秒かかるとしたら、全部で10秒です。運がよければもっと早くみつかるかもしれません。例えばオカダさんだと5秒ですね。最悪の場合で10秒ということです。全部調べていたら最悪で1000秒、つまり16分40秒かかるわけですから、相当賢くなったといえるでしょう。

二分探索の弱点 - 友達が増えたとき

ロボットは電話帳の特性を生かして賢く仕事をしましたが、これは個人のアドレス帳にも応用できるのでしょうか (1000人もアドレス帳に書いている人がいるとは思えませんが)。

アドレス帳はいつでも50音順に並んでいなければなりませんので、新しい人を追加するときが大変です。例えば500人目にハヤシさんを追加してみましょう。ロボットは「1000人目を1001人目に移動」「999人目を1000人目に移動」「998人目を999人目に移動」と延々と作業を続け、「500人目のハラさんを501人目に移動」とやって「500人目にハヤシさんを追加」と作業を終えます。それぞれに1秒かかるとしたら501秒、つまり4分21秒かかるわけです。ちょっと困りますね。

コンピュータの上では簡単に追加できるテクニック(二分探索木など) があるのですが、それはもう電話帳とはまた違った形になってしまいますので、ここでは触れないことにします。

ハッシュの原理 - 電話の横に置いてあるアドレス帳

同じアドレス帳でも持ち歩くタイプではなく、電話の横に置いてあるようなものを考えます。あれには「あ」から「ろ」までの目印がついています。ロボットにも「『い』のページの3人目は？」と訊くと「イケダさん。電話番号は…。住所は…」と 1秒で答えられる機能をつけてみました。

簡単に50音が本当に50文字あるとして、名前が平均的に分散していると仮定します。するとそれぞれのページには20人ずつ名前があることになります (「ん」で始まる人が20人いるの？とか細かいことは忘れてください)。 20人の名前の順序は適当で構いません。ロボットに「イケダさんの電話番号と住所は？」と訊いてみましょう。

ロボットは電話帳を調べ始めます。「『い』のページの1人目はイトウさん。イケダさんじゃない」「『い』のページの2人目はイシバシさん。イケダさんじゃない」「『い』のページの3人目はイケダさん。電話番号は…。住所は…」。今回は3秒でした。最悪の場合で20秒、平均で10秒です。なかなか早いですが、50音順のときに比べるとちょっと遅いですね。

ハッシュの強化 - 索引を長くしてみる

50ページしかないから遅いのです。名前の頭3文字までを使うとしたらどうでしょう。「イトウヒロフミさんの電話番号と住所は？」と訊いてみます。

「『いとう』のページの1人目はイトウマサヨシさん。違う」「『いとう』のページの2人目はイトウヒロフミさん。電話番号は…。住所は…」。今度は2秒でした。前回の50ページが125000ページに増えましたから、人名が平均的に分散しているとすれば1ページあたり0.008人。 1秒あれば電話帳に載っているかいないかがわかる計算になります。

でもちょっと待ってください。イトウさんのときは2秒かかりました。というのも「イトウ」という人は何人もいるでしょうが「イイイ」という人がいるでしょうか。「いいい」のページは空白なのではないでしょうか。他にも「ううう」や「えええ」のように、無駄になっているページがたくさんあるはずです。

ハッシュ関数 - ページを無駄なく使うために

ロボットは「い」のページや「いとう」のページを1秒で開いていました。もともとロボットは「7ページの2人目はイトウさん」のようにしか電話帳を読めませんから、実は「い」のページとは2ページ目のことだ、とか「いとう」のページは3503ページ目のことだとか頭の中で計算していたわけです。これをハッシュ関数と呼びます。

もうちょっと厳密にいうと、「イトウさんが電話帳に載っているとしたら3503ページ目を見ればいいはずだ」という計算がハッシュ関数なんですね。そのページは「い」のページなのか「いとう」のページなのかはあまり重要なことではありません。だから例えば「イトウヒロフミさんには800ページ目」「イトウマサヨシさんには5002ページ目」「イケダハヤトさんには101ページ目」などと適当に割り振ってしまえばいいのです。

うまいことページを分散させるために、いろいろ研究が進められています。一般にはうまく分散させられる関数のことをハッシュ関数と呼ぶことも多いです。

まとめ

大量のデータを検索するのには時間がかかります。
データが何かの規則で並んでいれば早く検索できます。
ハッシュを使うと追加や削除のあるデータでも早く検索できます。
ハッシュ関数を工夫するとデータ領域を無駄なく利用できます。
ハッシュでは時間を節約できる反面、データ領域が多めに要ります。

blog.fuktommy.com