Cuckoo Hashing とは、ハッシュテーブルの構造の一種である。
カッコウ(Cuckoo)には他の種類の鳥の巣に卵を置き、元々あったその鳥の卵は破棄するという習性があるが、
命名はそこから来ている。
まず、一般的なハッシュテーブルの作り方を考える。
8個の要素まで格納できるハッシュテーブルの作り方として、任意の整数 x を格納する場合を考える。
0から7までの整数を返すハッシュ関数H(x)を用意し、その値のインデックスの位置に x の値を格納すればよい。
すでに埋まっている場合は、ハッシュテーブルのサイズを倍にして、テーブルデータを作り直した後、ロジックを繰り返せばよい。
Cuckoo Hashing
Cuckoo Hashing では、２つの独立した8個までの要素を格納できるハッシュテーブルを用意する。
このハッシュテーブルには16個までの要素を格納できる。
一つ目のテーブルには0から7までの整数を返すハッシュ関数H1(x)を使い、二つ目のテーブルには0から7までの整数を返すハッシュ関数H2(x)を使う。
まず、H1(x)、H2(x)は異なるものを使い、同じxを与えたときに衝突がないようにしておく。
追加時のロジック
まずH1(x)を計算し、一つ目のテーブルが埋まっているか調べる。埋まっていなければ、その位置に格納する。
埋まっている場合はH2(x)を計算し、二つ目のテーブルが埋まっているか調べる。埋まっていなければ、その位置に格納する。
二つ目のテーブルが埋まっている場合は、すでに入っている値を取り出し、空いた位置に格納する。
取り出した値yでH1(y)を計算し、一つ目のテーブルが埋まっているか調べる。埋まっていなければ、その位置に格納する。 埋まっている場合
は入っている値を取り出しその位置に格納する。取り出した値zでH2(z)を計算して二つ目のテーブルが埋まっているか調べる。以下繰り返し。
検索、削除時のロジック
まずH1(x)を計算し、一つ目のテーブルに値があるか調べる。空の場合は、H2(x)を計算し、二つ目のテーブルにあるか調べる。
どちらにもなければ、なしとみなせる。
Cuckoo Graph
上記の追加ロジックによると、要素を玉突きのように、追い出して追加するようなケースが発生することが分かる。
この玉突きの様子に線を引きグラフのように見立てる。一つの要素からのグラフがその要素に戻るケースが発生する。これをループと呼ぶ。
だが、ループが２つ以上存在するケースは存在しないことが分かる。
Cuckoo Cycle
Cuckoo Cycle とは、２つのテーブルのグラフにおいて、任意の長さのループを作る操作のことである。
Cuckoo Hashing での要素を追加していくときに、一つの要素を追加する際にループができることがある。
この操作が任意の長さのループを求めるアルゴリズムとして使える。
この任意の長さのループを求めるという計算が grin の Proof Of Work として、利用されている。
ループを求めるには、そのサイズの要素の全てを保持するメモリが必要となることが分かる。
またループになっているかどうかは少ない計算量で確かめることができる。
https://web.stanford.edu/class/cs166/lectures/13/Small13.pdf
https://github.com/mimblewimble/grin/blob/master/doc/pow/pow.md
