如何快速检测指定长度的GUID是否已出现过？

你要的这种“快速排除绝大多数非重复请求，仅对高概率重复的情况做全量校验”的算法不仅存在，而且已经广泛应用在分布式系统的去重场景中，最典型的就是布隆过滤器（Bloom Filter），另外还有衍生的计数布隆过滤器、Cuckoo Filter等变种，完全适配你的需求。

核心思路：用布隆过滤器做前置快速判断 #

布隆过滤器的工作逻辑刚好匹配你的诉求：

• 它用一个紧凑的位数组+多个独立哈希函数，把已接收的GUID映射到位数组的对应位置（置为1）。
• 新请求过来时，用同样的哈希函数计算GUID对应的位：
  • 如果有任意一位是0：这个GUID绝对没出现过，直接放行，不需要碰后面的HashSet。
  • 如果所有位都是1：这个GUID大概率已经出现过，这时候再去查你维护的最近1000个GUID的HashSet做最终确认（因为布隆过滤器存在极低的误判概率，即非重复GUID被误判为已存在）。

这种方式完美解决了HashSet的“大小-延迟”权衡问题：布隆过滤器内存占用极小（比如存储1000个GUID，误判率0.1%的话，只需要约1.7KB内存），而且位运算的检查速度极快，绝大多数请求都能直接通过，只有极少数误判的情况才会触发HashSet的查询，整体延迟被压到最低。

适配“最近1000个GUID”的优化 #

因为你只需要维护最近的1000个GUID，避免内存无限增长，可以结合滑动窗口思路：

• 如果不需要支持删除（比如窗口满了直接丢弃最早的一批GUID），可以用分段布隆过滤器：把过滤器分成几个小的实例，比如每次存200个GUID，满5个就淘汰最早的那个分段，新的GUID写入最新的分段。检查时遍历所有未被淘汰的分段即可。
• 如果需要精确滑动（比如每新增一个GUID就移除最老的那个），可以用计数布隆过滤器（每个位存储计数而非0/1）或者Cuckoo Filter，这两个变种支持删除操作，当窗口滑动时，把最老的GUID对应的计数减1或者直接从过滤器中删除。

额外补充 #

如果你的message-id是标准UUIDv4（随机生成的128位GUID），本身自然重复的概率极低，但业务场景下可能因为重试等原因出现重复，布隆过滤器的误判率完全可以控制在可接受的范围内（比如0.1%甚至更低）。如果要求零误判，那“布隆过滤器前置+HashSet最终校验”的组合就是最优解。

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