Bloom Filter与HashSet对比：寻求更省空间的概率数据结构

针对你提到的场景——20bit键、集合大小1024，HashSet占10Kbit无错，误报率1e-7的布隆过滤器占33Kbit，以下是几种空间效率更高、支持可控误报的概率数据结构：

• 完美哈希+轻量布隆过滤器混合结构
  利用你的集合大小刚好是2^10的特点，先对20bit键做最小完美哈希，将其映射到10bit的唯一索引（无需存储索引表，只需要几个简单的哈希函数参数，空间开销仅几十bit）。之后用布隆过滤器存储这些10bit索引：要达到1e-7的误报率，所需空间约10Kbit（和HashSet相当），若可接受稍高误报，空间还能进一步压缩。

• 布谷鸟过滤器（Cuckoo Filter）
  这类过滤器在小基数、低误报场景下比布隆过滤器空间效率更高，还支持删除操作：
  针对你的需求，只需为每个元素存储约17bit的指纹，总空间为1024*17bit≈17Kbit，仅为你之前布隆过滤器的一半左右，误报率可稳定控制在1e-7级别。

• 简化版计数-Min Sketch（用于存在性判断）
  若仅需键存在性校验，可采用简化的CMS结构：用2-3个哈希函数将键映射到3个大小为1024的小型计数数组，每个数组位置用4bit计数（足够避免碰撞溢出），总空间为310244bit≈12Kbit，误报率可控制在1e-6级别，完全满足你对误报的容忍度。

关于你提到的「对键进行哈希处理」的思路，这是完全可行的核心优化方向：通过哈希将长键压缩为短指纹/索引，再用概率结构存储压缩后的值，能大幅降低空间开销。关键是要选择高扩散、低碰撞概率的哈希函数（如MurmurHash、xxHash），避免哈希碰撞显著抬升整体误报率。

内容的提问来源于stack exchange，提问作者Heiner Litz