算法与计算机科学somethingsimilar.com
布隆过滤器的反面
The Opposite of a Bloom Filter
2012 — 2017，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这篇文章介绍了一种“布隆过滤器的反面”数据结构：它能确定某个元素一定出现过，但可能遗忘（有假阴性但无假阳性）。实现方式是一个数组，用哈希值索引，插入时替换旧元素并比较是否为新元素，用于流处理中避免重复写入。
为什么经久不衰：它简洁地展示了布隆过滤器的互补思路，在去重和缓存场景中有实用价值，评论中的改进和质疑也让它常读常新。
HN 评论精选
用简单的哈希替换数组实现了“见过但会遗忘”的结构，并指出哈希和数组长度的重要性。
我读了几遍才明白，但其实很简单。你需要一个结构能告诉你某物已被见过，但有时会忘记，且绝不会错误地告诉你它见过。解决方案：一个数组。哈希找到索引，换出那里的值，看是否是你的项。如果是，你确定它之前被放入过；如果不是，它可能没被放入过（可能已被遗忘）。哈希算法很关键，加长数组就能减少遗忘，压缩键能减少存储。
MichaelGG查看英文原文
Took me a few reads, but it's actually quite simple. You want a structure that can tell you something has been seen, but sometimes forgets, but will never incorrectly tell you something has been seen. Solution: an array. Hash the item to find its index, swap out what's there, and see if it is your item. If so, you know for sure it was previously placed. If not, then it might not have (it may have been forgotten). let arr = Array of key let contains_key key = let index = hash key % arr.length let prev_key = arr.swap[index, key] return prev_key = key The hash algorithm is crucial. Reducing forgetfulness is as simple as making the array longer. And he points out that if you can compress the keys, you can reduce storage size.
提出可通过探测、布谷鸟哈希或年龄位来改进结构，减少碰撞损失并利用时间局部性。
这就像一个使用开放寻址但没有探测的缓存，任何初始碰撞都立即驱逐。所以可以考虑加入探测（在还有空槽时，以常数平均时间）来减少破坏性碰撞，或者用布谷鸟哈希等槽位选择方法。是否值得取决于饱和速度：如果通常是一对一驱逐，可以加个年龄位，偏向驱逐更旧/更少访问的值，利用时间局部性。有了年龄位，甚至不需要定期全量重置，只需让一部分旧条目在每个周期可被驱逐即可。
gojomo查看英文原文
Seems like a cache using open addressing but no probing, just instant eviction on any initial collision. So, could also consider adding probing to lessen destructive collisions (up to some chosen probing depth) while there are other unused slots, in still-constant average time. Or, any other choice-of-slots approach such as 'cuckoo hashing': http://en.wikipedia.org/wiki/Hash_table#Cuckoo_hashing Whether you'd want to pay that cost could depend on how soon you reach saturation within each reset period, after which 'every' insert results in an eviction. But if you were usually in one-for-one eviction mode, you might add a bit or more that hints 'age' or 'recent access' to probed items. Then each eviction could be biased towards an older/less-accessed value... taking more advantage of the clustering-in-time that was reported. And once you add that aging bit you might not need discrete full-restart periods ("hourly") at all: just make a useful proportion of older entries eligible for eviction each interval, maintaining a steady-state of full-array, evictions-biased-towards-older-entries.
指出这种结构比布隆过滤器占空间大，并询问这种不对称是否不可避免。
这很有用。但它比布隆过滤器大，因为布隆过滤器只需要一位，而这里要存一个值。我怀疑这种不对称不可避免，但无法证明。有人知道吗？
ajb查看英文原文
This is useful. However, it is larger than a bloom filter, because a bloom filter needs one bit where this stores a value. I suspect that this asymmetry is unavoidable, but I can't prove it. Anyone?
认为LRU/LFU可能性能更好，且“反面”的名称不贴切，因为空间复杂度和顺序无关性等特性不同。
这方案还行，但我觉得LRU或LFU缓存会更好（它们没有两个冲突事件频繁交替的病态情况），而且你可能不用自己实现。我也觉得叫它“布隆过滤器的反面”有点过了。布隆过滤器有很多特性这里没有体现。比如空间是O(MN)（元素大小×过滤器大小）而不是O(N)；而且布隆过滤器的结果与之前元素的添加顺序无关。如果你想要“反面”，你很可能希望保留这些特性。
mistercow查看英文原文
This seems like an alright solution, but I think an LRU or LFU cache would perform better (they wouldn't have pathological cases like two colliding events that frequently alternate), and you probably wouldn't have to implement it yourself. I also think it's a bit much to call this "the opposite of a bloom filter". A bloom filter has a lot of properties that don't come through in the algorithm proposed. For one thing, the space required is O(MN) (size of an element * size of the filter) instead of a bloom filter's O(N). For another, bloom filters give the same results regardless of what order previous elements were added in. It seems to me that if you're looking for "the opposite of a bloom filter", you're probably wanting those properties.
历次讨论
同类还值得读
位运算技巧集
Bit Twiddling Hacks
斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。
算法与计算机科学上首页 8 次 · 2011–2024graphics.stanford.edu编辑精选如何不按平均评分排序
How Not To Sort By Average Rating
经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。
算法与计算机科学上首页 7 次 · 2009–2024evanmiller.org编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选