次の操作をサポートする固定サイズ セットのデータ構造を作成しようとしています。
- 要素がセット内にあるかどうかを照会します (偽陽性は問題ありませんが、偽陰性は問題ありません)。
- セットの 1 つの要素を別の要素に置き換える
私の場合、セットのサイズは非常に小さい (4 ～ 16 要素) 可能性がありますが、ルックアップはできるだけ高速で、読み取りビット数をできるだけ少なくする必要があります。また、スペースを効率的に使用する必要があります。代替品 (すなわち操作 2) はほとんどない可能性があります。次のオプションを調べました。
- ブルーム フィルター: これは標準的なソリューションです。ただし、要素を削除するのは難しいため、操作 2 を実装するのは困難です。
- ブルーム フィルターのカウント: false +ve 率が減少しない場合、必要なスペースは標準のブルーム フィルターよりもはるかに高くなります (~ 3 ～ 4 倍)。
- すべての要素のハッシュのリストを単純に保存する: 同様のスペース要件のブルーム フィルターをカウントするよりも false +ve 率が高くなりますが、検索にコストがかかります (最悪の場合、すべてのビットが検索されます)。
- location の完全なハッシュに関する以前のアイデア: 要素の小さなセットに対する高速な完全なハッシュについてのアイデアはありません。
追加情報：
- 要素は 64 ビットの数値です。
これを解決する方法についてのアイデアはありますか?