如何在合理内存占用下判断指定hash是否存在于超长哈希列表中

这类需求属于典型的成员存在性校验场景，核心思路是通过接受可配置概率的假阳性，换取数十倍甚至上百倍的空间压缩，你可以根据业务可接受的误判上限灵活调整参数，完全控制内存占用。

可选数据结构与算法汇总 #

• 布隆过滤器（Bloom Filter）
  最经典的通用方案，原理是用k个独立哈希函数将输入映射到bit数组的k个位置并置为1；校验时只要有一个位置为0即可100%判定不存在，所有位置为1则判定存在。
  空间开销极低：10亿条数据、万分之一假阳性率的场景下，仅需要约1.7GB内存，仅为直接存储32位哈希开销的1/20。原生实现不支持删除，有删除需求可选用计数布隆过滤器变体。
• 布谷鸟过滤器（Cuckoo Filter）
  布隆过滤器的主流改进方案，支持元素删除，同空间下假阳性率比布隆过滤器低30%左右，查询性能更高，不存在假阴性，适合需要动态增删哈希的场景。
• 商过滤器（Quotient Filter）
  相对冷门的高性能实现，基于商余数编码原理，支持插入、查询、删除全操作，空间效率比布谷鸟过滤器更高，额外支持多集合合并操作，对SSD友好，内存不足时可直接落地到磁盘，查询性能不会出现大幅下跌，非常适合分布式多节点的大规模哈希校验场景。
• Xor过滤器（Xor Filter）
  近年提出的冷门静态结构，是目前所有成员校验结构中空间效率最高的实现，同误判率下比布隆过滤器省30%左右的内存，查询速度极快，唯一缺点是构建完成后不支持新增/删除元素，适合哈希集合不会更新的静态校验场景，比如历史黑哈希库、冻结的合规哈希名单校验。
• 哈希前缀分片方案
  如果业务完全不能接受任何假阳性，可以采用分层分片策略：将所有哈希按固定长度前缀分为N个分片，每个分片单独落地存储，校验时先取待查哈希的前缀匹配对应分片，仅将该分片加载到内存做精确校验即可，内存占用仅等于单个分片的大小，可通过调整分片数量灵活控制内存上限，缺点是查询会引入磁盘IO开销。

工程优化提示 #

如果你的待校验哈希本身是密码学哈希函数（SHA256、MD5等）的输出，本身已经满足均匀分布特性，可以直接取哈希的部分bit位作为过滤器的输入，不需要额外做哈希计算，可节省大量CPU开销。
所有概率型过滤器的假阳性率都可以通过公式提前计算，你可以根据业务允许的误判上限反向推导所需的内存大小，实现内存占用的完全可控。

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