Hopscotch Hashingなるものを見つけた

必要に迫られているわけでもなく、ものすごく興味があるわけでもないけれど、ふと最強のハッシュアルゴリズムってなんだろう?という小さな疑問から色々探してみたら、ハッシュの世界はなかなか奥が深いものでした。

 

あなたの知らないハッシュテーブルの世界

 

とにかくこれが最高にわかりやすかった。そしてこの中で紹介されていたのが『Hopscotch Hashing 』です。世の中には『Cuckoo Hashing』なるものが存在していて(個人的にはCuckoo Hasingはそんなに有用性が高くないと思う ※これは素人考えで実際は全然そんな事ないそうです)、古典的アルゴリズムもいまだに改良されてるのかぁとかしみじみ思ったこともありましたが、『Hopscotch Hashing 』は知らなかったっす。こちらに論文があります。

 

Hopscotch Hasing

 

英語キター!!

ということでいつか暇な日曜日の昼下がりに紅茶でも飲みながら読むことにしましょう。概要は上のリンクのスライドでかなりつかめるし、実際に実装している方もいるし(hopscotch hasingでググると上の方にくるブログ)、slideshareにほぼ同じスライドあるしなので、いつか実装したいなぁと思いました。

 

Hopscotch Hashingを実装してみた | Story of Your Life

 

よくわかるHopscotch hashing