ハッシュテーブル#2

無限にメモリーが使えるなら一番速くなるわけだが、そういうわけにもいかないので、
今回のように、数百程度のキーワードと比較するのに適切なメモリーはまずいくらかと。
64ビットの数字でハッシュを出すと2の64乗種類の単語を扱えるわけだが、
メモリーも2の64乗にポインタのバイト幅をかけた分という量を使うことになり現実的ではない。
せいぜい数キロで抑えないと、実装のデメリットばかりになる。



たとえば100の単語を入れるのに100の部屋だと、手間は普通の検索より少なくできない。
100の単語を入れるのに、いくつ部屋を用意すれば、十分に速くなるのかを知りたい。
実は理想的な状態では200あれば最高の速度が出せる。
この検索方法では、ハッシュをもとに辿り着いた部屋に、単語が入っているかどうかまず調べる。
空室なら、該当する単語無しで検索終了だ。
単語が入っていれば比較し、バッチリあっていればヒットで検索終了。
しかしハッシュが同じで違う単語が入っていることもあり、
そのときは順番に次の部屋を確認していき、空室かヒットが出るまで続く。
つまり、200用意した部屋に、ちょうど100の単語が1部屋置きに入ってくれればいいわけだ。
100の単語のハッシュが全て異なり、しかも1部屋置きに並ぶことはあり得ないが。

で、実際にコードを書いてみて、数百の単語について何部屋用意すれば良いか試してみた。
このハッシュテーブルについて書いてあった某雑誌には、
部屋の数を素数にすることで、そうでない場合よりバラけるという風に書いてあり、
実際に素数にすることでバラけさせる例も書いてあった。
しかし、素数じゃないよりはマシだから素数が定番だと書いてあっただけで、
素数を使ってもやっぱり同じハッシュの違う単語は想像以上にたくさんあった。
使用したのは真魚内部のPHPのキーワード群で、
452個の単語を1009(素数)部屋に割り振ってもたくさん衝突がある。
2003、4001、8009、と部屋数を上げていくが、最初の数十で衝突が出て先に進まない。
それ以上大きい数字は実装上のデメリットを考えると不可能。
というわけで、ハッシュのダブリが全く発生しないようにするのはあきらめた。
ダブリが発生したら次の部屋へと言う方法でやっちゃうしかないわけだが、
それだと上記のように、空き部屋に辿り着くまで何度か思考する事になるわけだが、
それでも全部の部屋と比較するよりは速いって言う状態を作るために、
単語の最大数×2ぐらい用意しておけば、偏ってもそれほど遅くはならないはず。
最大数はそのPHPでの452なので、まずは1009を使おう。
もし、将来もっと必要になったら、その都度拡張しよう。
うまくいけば可変が一番良い。

たしかPHPはもっとたくさんの関数を色分けしたかったのに、
速度のことを考えて遠慮したと言う経緯があったので、
ハッシュテーブルを使って可変でも出来たら増量するかもな。

たぶん関連のある記事:

コメントは終了しています。