北京
凌晨两点，后端工程师李鸣盯着监控面板上一条直线往上升的CPU利用率曲线。他所负责的广告点击去重服务，每小时要处理上亿条事件，用std::unordered_set去重已经顶不住了。同事丢来一句话：“去重最快的方法，根本不一定是哈希集合。”点开一看，是一份名为《The Shape of Duplicate Detection》的研究。里面塞了4050个实测数据、480种负载，很多结论直接挑战了团队过去几年的默认选择——有些场景用哈希表慢了不止一星半点，而是差出94倍甚至9万倍。李鸣从第一页开始，被拉进了一条完全不同的去重设计路径。
研究团队首先瞄准了一个最直白的场景：**稠密有界整数的去重**。当键值是一批范围固定、分布均匀的32位整数时，直接拿哈希集合往里扔，等于强迫数据走一条多余的流程。std::unordered_set每插入一个值就得先算哈希，再在桶链表里探测、找位置，最后还要在内存中跟着指针跳来跳去。可如果替换成一块预分配好大小的位集（bitset），一切变得极其简单：整数值本身就是数组下标，对应比特位置1就代表“见过”，一次内存写入便完成去重判断。在一次100万个均匀32位整数的测试中，位集和哈希集合产出的去重结果完全一致，但前者跑出的速度整整快了94倍。研究者给出的建议没有丝毫摇摆：如果你的键天生就能当数组索引，那就别再把它硬塞进哈希的逻辑里。三十倍到一百一十倍的提升，并不是靠优化哈希函数得来的，而是把问题换了一种数据结构去解决。
接下来画风陡变。当去重对象从整数变成**长文本字符串**时，哈希集合和位集的竞争格局被彻底打乱。长字符串的比较和哈希计算开销极大，光是对一长串字符进行一遍散列，成本就超过了好几次整数操作。这时候，研究给出了一条看似绕路的策略：先为每条字符串计算一个轻量程度的数字指纹，然后对这些指纹排序，排序后马上就能发现重复的指纹；当指纹出现冲突时，再拿出完整的原始字符串做一次严格比对，确保不误判。这套“指纹排序加验证”的流程，在实际测试中跑赢了哈希集合，幅度在1.8倍到2.7倍之间。不过故事并没有一边倒。在某些负载下，重复的字符串会扎堆出现，此时哈希集合反而重新夺回优势——原因在于，多次命中同一个散列桶会让对应的缓存行持续处于热状态，后续访问几乎全从CPU缓存中直接读取，避开了内存延迟。一条简短的结论背后，埋着对现代处理器缓存结构的深刻理解。
另一种更具冲击力的反差，出现在**流式无界数据的去重**上。当你面对每秒涌入数万条的事件流，并且要求不让重复事件流入下游时，问题悄然变了一个方向：能记住的东西始终是有限的。研究对比了两条完全不同的技术路线。第一条，在内存里维护一个滑动窗口，只保留最近一小段时间内的事件键，每来一个事件就在窗口内做一次快速检查——单次操作平均开销约68纳秒，几乎等于几次指针运算的时间。第二条，选择所有事件都落库，采用PostgreSQL，每个进入的事件都立刻开启一个独立事务，写入、提交，然后才对外返回“已去重”的判断。同样的逻辑，同样的正确性保证，但单次检查的成本却暴涨到大约6.1毫秒。从68纳秒到6.1毫秒，同一份去重检查，竟然相差了约9万倍。这9万倍的鸿沟，其实并非由数据库本身慢得离谱造成，而是每一次“即写即提交”的事务化操作，都吞掉了大量磁盘I/O和同步等待。研究紧接着补了一刀：只要稍微改变写入策略，改成攒一批事件后做一次批量提交，就能把数据库方案的延迟拉回到接近内存窗口的数量级。同样用PostgreSQL，差别不过是一个事务边界怎么划的问题。
上述几次实验一起，最终被汇成了一张可供团队直接对准的决策表。每一条都是基于不同键值形态和不同可靠性要求给出的具体选型：
- 稠密有界整数：毫不犹豫用预分配大小的位集，实测通常快30倍到110倍。</
特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
