我正在尝试为固定大小集创建一个数据结构，该结构应支持以下操作：
- 查询元素是否在集合中(误报正常，漏报无效(
- 将集合中的一个元素替换为另一个元素
就我而言，集合的大小可能非常小(4-16 个元素(，但查找必须尽可能快并读取尽可能少的位。此外，它需要节省空间。更换(即操作 2(可能很少。我研究了以下选项：
- 布隆过滤器：这是标准解决方案。但是，很难删除元素，因此难以实现操作2。
- 计数布隆过滤器：空间要求比标准布隆过滤器高得多(~3-4 倍(，而不会降低错误 +ve 速率。
- 简单地存储所有元素的哈希列表：对于类似的空间要求，提供比计数布隆过滤器更好的 false +ve 速率，但查找成本很高(在最坏的情况下，将查找所有位(。
- 以前对位置进行完美哈希的想法：我对一小组元素的快速完美哈希没有想法。
附加信息：
- 元素是 64 位数字。
关于如何解决这个问题的任何想法？
布谷鸟过滤器是一个应该考虑的选项。引用他们的摘要
布谷鸟过滤器：几乎比布卢姆更好
我们提出了一种新的数据结构，称为布谷鸟过滤器，可以取代布隆过滤器进行近似集合成员船测试。Cuckoo 滤镜支持动态添加和删除项目，同时实现比布隆滤镜更高的性能。 对于存储许多项目和 针对中等低的误报率，**布谷鸟过滤器比空间优化的布隆过滤器具有更低的空间开销。我们的实验结果还表明，布谷鸟过滤器的性能优于以前的数据结构，这些数据结构扩展了布隆过滤器，在时间和空间上都支持大量删除。
https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
好吧，请注意以下几点：
- 使用标准哈希
表，带有下降哈希函数(因为它是数字，所以有一堆标准哈希函数(和 4|S|条目平均需要少于 2 次查找(假设无偏数字作为输入(，尽管它可能会恶化到可怕的最坏情况 4|S|.当然可以按如下方式绑定：
- 如果搜索的单元格数超过k- 中止并返回 true(将导致 FP 在您可以校准的某种概率下，并将提供更快的最坏情况性能(。关于计算布隆过滤器 - 这是这样做的方法，IMO。请注意，布隆过滤器(标准(要求 154 位的 FP 概率为 1%，或 100 位的 FP 概率为 5%。(*)
因此，如果您需要此数字的 4 倍，您将获得 616 位/400 位，请注意，在大多数现代机器中，这足以填充一些 CPU 缓存块，这意味着(取决于机器( - 在某些机器上读取所有这些位实际上可能需要不到 10 个周期。
IMO 如果不获得更高的 FP 率，您将无法做任何事情来击败它。
(*( 计算依据：
m = n ln(p(/ln(2(2
附言如果您可以保证每个元素最多删除一次，则可以使用具有双倍空格的布隆过滤器变体，该变体具有稍好的FP，但也有一些FN，只需使用2个布隆过滤器：1个用于regular,1用于deleted。如果元素在 regular 中而不是在 deleted 中，则该元素在集合中。
这提高了FP率，但代价是还具有FN
签出succinct data structures，例如常量时间和最小空间的成员资格。
在处理从 有界宇宙，其中子集的大小相对较大 但不够大，无法使用位图。