偽陽性を許容して空間効率良くキーの存在を確認するBloom filterとCuckoo filter - sambaiz-net例えばデータストアへのアクセス抑制のためにキーの存在を確認する際、 全てのキーを保持して探索すれば100%正しく判定できるが、キーが長く数が膨大になるとメモリの使用量が問題になることがある。 もし偽陽性が許容できるなら、次のフィルタを使うことで空間効率良くキーの存在を確認できる。 Bloom filter 1970年に考案されたフィルタで、 LevelDBやCassandraで使われている。 GoogleのkvsライブラリLevelDBを使う - sambaiz-net 初期値0のビット配列と、そのいずれかのビットにデータをマッピングするk個のハッシュ関数を定義し、 含めるデータを各ハッシュ関数に通して、マッピングされたビットを1に更新していく。 これにより、いずれかのハッシュ関数によって0のビットにマッピングされるデータは、必ずフィルタに含まれないことが分かる。 また、ビット配列のAND
