GolangでCuckoo Hashingを実装してみた

2017/5/27 修正
int64型であるkeyを[]byte型へconvertする際にhasher.Write([]byte(string(key)))ではうまくいかないため以下のように修正しました。

b := make([]byte, 8)
binary.LittleEndian.PutUint64(b, uint64(key))

hasher.Write(b)

背景

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

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