読者です 読者をやめる 読者になる 読者になる

GolangでCuckoo Hashingを実装してみた

BloomFilterを実装した後に、やろうやろうと思っていたCuckoo Hashingを実装してみました。
Cuckoo Hashing自体の説明は @_krzさんの記事がわかりやすいです。絵を交えられているのでイメージもつきやすいです。
メリットとしてはlookupが定数時間(2回比較するだけ)で完了することが挙げられます。
またアルゴリズム自体がわかりやすいです。2つのテーブルを用意しておき、挿入したいkeyハッシュ値を計算し、ハッシュ値をindexとみて、テーブルが空いていれば挿入。すでに埋まっていれば、keyと既に入っていた値を交換して、もう一つのテーブルで同様の操作を繰り返すという流れになっています。カッコーの托卵のようですね。

デメリットは、ハッシュの衝突が起こった場合やループが無限ループに入る恐れがあります。今回の実装でもMAXLOOPを設定することで無限ループを防いでいます。 また、こちらによるとテーブルの半分が埋まった段階で性能が落ちてしまうそうです。

実装

gistaaf77c63f3668efdd44e2f4ae9642f76

今回は0を空とする実装にしましたが、実際には0を挿入したい場合も多いと思うので、その場合はうまくゼロ値を使うなどするのがよいと思います。

References