Title Text:Sometimes, you can tell Bloom filters are the wrong tool for the job, but when they’re the right one you can never be sure.

Origin:https://xkcd.com/2934/

https://www.explainxkcd.com/wiki/index.php/2934:_Bloom_Filter

布隆过滤器

https://xkcd.in/comic?lg=cn&id=2934

这部漫画讲述了一种称为布隆过滤器的数据结构。软件工程师使用布隆过滤器来检查某些东西是否可能在一个集合中，或估算该集合中有多少东西，同时使用有限的内存。

一个例子：Chrome网络浏览器曾用来存储已知恶意的URL的布隆过滤器，基于一个太大而无法本地存储的数据库。Chrome使用这个布隆过滤器来确认是否需要警告用户他们正在访问一个恶意页面。只有在极少数情况下，布隆过滤器表示该URL可能是恶意的，Chrome才会将该URL发送到外部服务以确认它是否已知为恶意。开发者不希望浏览器将每个URL都发送到外部服务，因为那样会泄露用户的整个浏览历史到该服务中，并且在加载网页时会造成不必要的网络延迟。
布隆过滤器的工作原理如下：

添加项目：当添加一个项目时，它会被多个哈希函数哈希（将其转化为数字的一种方式）。这些哈希函数将在一个大的位数组中标记某些位置（可以把它想象成一排可以开或关的灯）。
检查项目：要检查一个项目是否可能在集合中，您需要使用相同的函数对其进行哈希，并查看所有相应的位置是否点亮。如果亮了，该项目可能在集合中，但有可能出现假阳性（布隆过滤器可能错误地表示该项目存在于集合中）。如果任何位置没有点亮，则该项目不在集合中。
假阳性：数组的大小与项目数量相比越大，假阳性的机会就越低。例如，每个项目10个位使得每个被测试项目匹配到集合中实际存在的每个项目的机会为0.1%。
计数项目：通过分析被激活的位，结合适当的计算，可以推导出在数组中“存储”的个别项目的估算数量。这个估算的准确性将取决于多个因素，但更多的数组位（可能能够“记住”每个项目）在缩小可能性时是最重要的因素之一。
在漫画中，Cueball手里拿着一张纸或平板电脑，上面有一个大的“1”数字。这被标记为1位布隆过滤器，几乎没有用。当为空时，它对任何测试的项目正确返回负值，但一旦添加一个项目，该位就被设置为1，现在它无用地表示任何测试的项目可能在集合中。它的大小估算也变成了“在1和无限之间”，这也没有帮助。
对于一个1位过滤器来说，拥有多个哈希函数是毫无意义的，因为它们最终都会指向同一个位，这将返回完全相同的结果。
标题文本将布隆过滤器的特征引入选择布隆过滤器而非其他候选数据结构的决策过程。类比地（根据文本），您可以确定它们不是最佳方法，但只能在有限程度的概率下得出它们是的结论。