算法与计算机科学llimllib.github.io编辑精选
通过示例理解布隆过滤器
Bloom Filters by Example
2017 — 2025，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这是一个通过实例讲解布隆过滤器（Bloom Filter）的交互式教程，介绍这种空间高效的概率型数据结构如何判断元素是否属于集合，以及其允许假阳性、不会假阴性的特性。教程以循序渐进的代码示例帮助读者理解其原理与实现。
为什么经久不衰：布隆过滤器是工程中常用的经典数据结构，这篇教程以直观示例讲透原理，多年来反复登上 HN 首页，至今仍是入门首选。
HN 评论精选
用加盐的单一哈希函数即可替代多个哈希函数
我不认同布隆过滤器需要多个哈希函数的标准教条。只需用一个递增的盐值修改输入，就能用同一个哈希函数按需哈希任意多次。比如要把 "abc" 哈希 8 次，不用 8 个哈希函数，而是哈希 "abc-0"、"abc-1"……"abc-7"。只要哈希函数质量好、输出处理得当，这些结果之间不会有显著关联。实践中这对我一直很有效。
natch查看英文原文
I disagree with the standard dogma around bloom filters that you need multiple hash functions. Just use a simple incrementing salt value to modify the input so you can hash the resulting salted input as many times as you need to, using a different salt value each time. Say you want to hash the string "abc" 8 times. Instead of having 8 hash functions, just take the hash of, say, "abc-0", "abc-1", ... "abc-7". As long as your hash function is of good quality and you're treating the output properly, you don't have to worry about the results from these different inputs having some significant relationship. For cryptographic types maybe I'm using the term "salt" loosely. Whatever, think of another term if you like. Anyway in practice this has worked fine for me.
给出直接计算布隆过滤器最优参数 m 和 k 的公式
这似乎是确定布隆过滤器大小的绕弯办法。我当年为 Newzbin 实现时总结出了直接的计算公式：m = ceil((n * log(p)) / log(1.0 / (pow(2.0, log(2.0)))))，k = round(log(2.0) * m / n)。
Freaky查看英文原文
That seems a roundabout way of sizing a bloom filter. Here's what I came up with when I first implemented them for Newzbin: https://hur.st/bloomfilter m = ceil((n * log(p)) / log(1.0 / (pow(2.0, log(2.0))))); k = round(log(2.0) * m / n);
提问：为何不能把可靠的“非成员”判断取反当作成员判断
不相关，但我一直有个关于布隆过滤器的疑问：如果判断元素在集合中不可靠，但判断不在集合中每次都准确，那为什么不能简单地把非成员判断的布尔值取反，就当作成员判断？比如：如果它不是“不在组里”，那它就在组里……
tomc1985查看英文原文
Unrelated, but I've always had this question about bloom filters... If testing for membership in the set is unreliable, but testing for non-membership in the set works every time, then why can't you simply invert the boolean for the non-membership test and call that a membership test? E.g., if it's not not in the group, then it's in the group...
提问：单次加密哈希的输出能否切分代替多次哈希
对于使用加密哈希函数的实现，真的需要对每个元素多次调用哈希函数吗？比如实现一个 2^20 位的布隆过滤器，每个元素占 10 位，能否不用哈希 10 次，而是用 256 位加密哈希只哈希一次，取低 200 位，切成 10 个 20 位的字符串来用？
tzs查看英文原文
For implementations that use cryptographic hash functions, do you actually need more than one hash function invocation per item? For instance, suppose you were implementing a Bloom filter with 2^20 bits, and you want to use 10 bits per item. Instead of hashing the item 10 times, could you hash once with a 256 bit cryptographic hash, and then take the lower 200 bits, divide that into 10 bit strings of 20 bits each, and use those?
历次讨论
同类还值得读
位运算技巧集
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编辑精选