Kirsch-Mitzenmacher Optimization
#データ構造
2つのハッシュ関数から n 個のハッシュ関数を生成する。Bloom Filter などで用いる。
$ h_1, h_2
を値域
$ \{0, \ldots, p - 1\}
の異なるハッシュ関数とする。新しいハッシュ関数
$ g_1, \ldots, g_k
を以下のように定める：
$ g_i(x) = h_1(x) + ih_2(x)\mod p
Building a better Bloom Filter
Kirsch, Mitzenmacher らによる論文
Which hash functions to use in a Bloom filter - Stack Overflow
http://cgi.di.uoa.gr/~ad/k22/Bloom_Filters.pdf