Cuckooフィルター：なぜ正確に7カウントですか？ （エンティティ挿入の「限られた数」のように）

Question

私は過去数日の間、鳩のようなフィルターで私の頭を包み込んでいます。私は、多くの点でブルームフィルタに比べて利点があることを理解しています。一般的には、使用することをお勧めします。

私が探しているアプリケーションの数は必要です。私はどこにでも情報を見つけることができません。なぜなら、鳩のようなフィルターでは「カウントが限られている」という理由があります。 （私は限界が7であると聞いたが）

これは理論上の制限ですか？

Answer 1

Cuckooフィルタは、単一のキーの複数のコピーを保持できます。すべてのアイテムは同じハッシュ値を持つため、2つの可能なバケットのいずれかの1つのスロットにすべて挿入されます。バケットのサイズが4の場合、合計8スロットになります。

一般的に、可能なスロットがいっぱいになったときにキーを追加しようとすると、問題はありません。スロット内のキーの1つが単純に追い出されます。ただし、すべてのキーが同じである場合、移動できるオーバーフローまたはバックアップの場所はありません。