使用bloom滤镜有什么好处？
我正在阅读bloom filters，他们看起来很傻。 任何你可以使用布隆filter来完成的事情，你可以用更less的空间，更高效地完成，使用单个散列函数而不是多个，或者看起来就是这样。 为什么要使用布隆filter，它如何有用？
维基百科 ：
布隆filter比其他表示集合的数据结构具有强大的空间优势，例如自平衡二叉search树，尝试，哈希表或简单数组或条目的链接列表。 其中大多数需要存储至less数据项本身，这可能需要从less量的位，小的整数，到任意数量的位，例如string（尝试是一个例外，因为它们可以共享存储具有相同前缀的元素）。 链接结构会为指针产生额外的线性空间开销。 布隆filter错误率为1％，最佳值为k，而每个元素只需要大约9.6位，而不pipe元素的大小如何。 这个优点部分来自其紧凑性，从数组inheritance而来，部分来自其概率性质。 如果1％的误报率太高，每次我们添加大约4.8个比特，我们就减less10倍。
对我很清楚。
布卢姆filter不存储元素本身，这是至关重要的一点。 您不使用布隆filter来testing元素是否存在，您可以使用它来testing它是否存在，因为它保证没有错误的否定。 这样可以避免为一个集合中不存在的元素（如磁盘IO查找它们）做额外的工作。
而且所有这些空间都比散列表（这对于大型数据集可能部分在磁盘上）要小得多。 虽然你可以使用布隆filter和哈希表这样的结构，但是一旦你确定这个元素有可能存在。
所以一个示例使用模式可能是：
你在磁盘上有很多的数据 – 你决定你想要的错误界限（例如1％），它规定了m的值。 然后确定最优k （从文章中给出的公式）。 您从这个磁盘绑定数据填充您的筛选器一次。
现在你有RAM中的filter。 当你需要处理一些元素时，你可以查询你的filter，看看它是否存在于你的数据集中。 如果没有，则不需要额外的工作。 没有磁盘读取等（如果它是散列或树等，你将不得不这样做）。
否则，如果filter显示“是，它在里面”，那么有1％的可能性是错误的，所以你做了必要的工作来找出答案。 99％的时间，它真的会在那里，所以工作是没有任何失败的。
亚历克斯已经解释得很好。 对于那些还没有掌握的人来说，希望这个例子能帮助你理解：
比方说，我在谷歌Chrome团队工作，我想添加一个function，浏览器通知用户，如果他input的url是一个恶意的URL。 所以我有一个约100万个恶意URL的数据集，这个文件的大小大约是25MB。 由于尺寸相当大（与浏览器本身的尺寸相比较大），因此我将这些数据存储在远程服务器上。
情况1：我使用散列表的散列函数。 我决定一个有效的散列函数，并通过散列函数运行所有的100万个URL来获得散列键。 然后我做一个哈希表（一个数组），在那里的哈希键会给我的索引来放置该url。 所以现在一旦散列并填充哈希表，我检查它的大小。 我已经将所有的100万个URL和他们的密钥一起存储在散列表中。 所以大小至less是25 MB。 这个哈希表由于其大小将被存储在远程服务器上。 当用户出现并在地址栏中inputURL时，我需要检查它是否是恶意的。 因此，我通过哈希函数（浏览器本身可以做到这一点）运行URL，我得到了该URL的哈希键。 我现在必须使用该散列键向远程服务器发出请求，以检查散列表中具有该特定键的特定URL是否与用户input的内容相同。 如果是，那么它是恶意的，如果没有，那么它不是恶意的。 因此，每当用户inputURL时，都必须向远程服务器发送请求，以检查是否为恶意URL。 这将花费很多时间，从而使浏览器变慢。
案例2：我使用布隆filter。 整个列表中有100万个URL通过使用多个散列函数的bloomfilter运行，并且相应的位置被标记为1，在一个巨大的0arrays中。 假设我们想要1％的误报率，使用布隆filter计算器（ http://hur.st/bloomfilter?n=1000000&p=0.01 ），我们得到所需布隆filter的大小仅为1.13 MB。 尽pipe数组的大小很大，我们只需要存储1或0，而不是像散列表那样的URL。这个数组可以被当作位数组来处理。 也就是说，由于我们只有两个值1和0，我们可以设置个别位而不是字节。 这将减less8倍的空间。 这个1.13 MB的布鲁姆filter，由于其体积小，可以存储在networking浏览器本身！ 因此，当用户出现并inputURL时，我们只需应用所需的散列函数（在浏览器本身中），并检查bloom筛选器（存储在浏览器中）中的所有位置。 任何位置的值为0告诉我们，这个URL在恶意URL列表中是DEFINITELY NOT，用户可以自由进行。 因此，我们没有打电话给服务器，因此节省了时间。 值为1告诉我们URL可能在恶意URL列表中。 在这些情况下，我们调用远程服务器，在那里我们可以像第一种情况一样使用一些哈希函数来检索和检查URL是否实际存在。 由于大多数情况下，URL不可能是恶意URL，因此浏览器中的小布隆筛选器会计算出来，从而避免调用远程服务器，从而节省时间。 只有在某些情况下，如果布隆filter告诉我们url可能是恶意的，那么只有在这种情况下，我们才会打电话给服务器。 这“可能”是99％的权利。
因此，通过在浏览器中使用小布隆filter，我们节省了大量时间，因为我们不需要为input的每个URL进行服务器调用。
我们可以看到，具有单个散列函数的散列表与散列filter完全不同的用途。 希望这清除你的怀疑:)
编辑 ：
我已经为Python中的恶意URLtesting任务实施了一个bloomfilter。 代码可以在这里find – https://github.com/tarunsharma1/Bloom-Filter代码非常简单易懂，在自述文件中提供了详细的描述。;
我将首先解释什么是布隆filter，它可以做什么，不可以做什么，为什么我们需要它，直观地描述它是如何工作的，然后给出一些可用的例子。
所以一个标准布隆filter是一个概率数据结构 ， 可以 * ：
- 添加元素到一个集合
- 通过
definitely not in the set或possibly in the set检查元素是否在possibly in the set
这possibly in the set中正是为什么它被称为概率。 使用聪明的词，这意味着假阳性是可能的（可能有错误地认为该元素是正面的），但是假阴性是不可能的。
但它不能 * ：
- 从集合中删除一个项目
- 给你一个当前在你的设置中的所有元素的列表
* 这套can / can不适用于基本布隆filter。 因为它是很早以前创build的有用的数据结构，所以人们发现如何用其他有用的特性来增强它。
但等一下：我们已经知道一个数据结构，可以回答所有这些，没有模糊的“可能”，也没有所有的限制（不能删除，不能显示全部）。 它被称为一个集合 。 这里有一个布隆filter的主要优点：它是空间有效和空间不变的 。
这意味着我们在那里存储了多less元素并不重要，空间也是一样的。 是的， 10^6元素的布隆filter（无用的布隆filter）将占用与10^20元素的布隆filter相同的空间量，并且具有与0元素的布隆filter相同的空间量。 那么需要多less空间？ 这取决于你自己决定（但有一个交易： possible in the set答案中，你有更多的不确定因素与你possible in the set 。
另一个很酷的事情是，它是空间不变。 当您将数据保存到一个集合中时，您必须实际保存这些数据。 所以如果你将this long string in the set存储this long string in the set你至less需要使用27个字节的空间。 但是，对于1％的错误和k **的最佳值，每个元素（无论是简短的int还是巨大的文本）都需要9.6位（<2字节）。
另一个属性是，所有的操作都是不变的，这与set的情况下的分期恒定时间是绝对不一样的（记住，如果集合有冲突，在O(n)时间内会恶化）。
** k是在布隆filter中使用的哈希函数的值
我不会描述bloomfilter是如何工作的 （维基百科文章在解释所有事情方面做得非常好）。 在这里，我将简要介绍基本知识。
- 您启动一个长度为
m的空位数组 - 你select
k不同的哈希函数（越独立越好） - 如果要添加元素，则计算此值的所有
k哈希，并将相应的位设置为1 - 如果你想检查元素是否存在，你也计算所有
k哈希，如果至less有一个没有设置，肯定是不在集合中。 否则它可以在集合中。
即使这个描述足以理解为什么我们不能确定（你可以从各种其他值中设置所有位）。 它是如何工作的一个非常好的可视化 。
那么何时可以开放filter有用呢？ 简短的答案是在任何地方都可以接受误报，并且你可能想要检查是否有某些东西在这个集合中 ，但即使它们不是这样，也可以作为排除昂贵的调用validation者的第一道防线。
这里是一个更具体的描述清单：
- 恶意网站和浏览器的标准示例几乎在任何人们谈论布隆filter的地方都有描述
- 是一个密码弱：而不是有一个庞大的一套可能的弱密码，你可以检查密码是否肯定不弱，方式较小布隆filter
- 如果您有文章列表和用户列表，则可以使用布隆filter来显示用户没有阅读的文章。 有趣的是，你可以只有一个filter（你检查是否有user_id + article_id的组合）
- 比特币使用布隆filter进行钱包同步
- Akamai的Web服务器使用Bloomfilter来防止“一命中奇迹”被存储在磁盘caching中。 一次奇迹就是一次用户请求的网页对象，这是Akamai发现的应用于其caching基础架构近四分之三的事情。 使用布隆filter检测Web对象的第二个请求并仅在第二个请求中caching该对象时，可以防止一命中的奇迹进入磁盘caching，从而显着减less磁盘工作负载并提高磁盘caching命中率（从Bloom的筛选器中获取示例文章在wiki）
布隆filter在生物信息学中非常有用。 与使用常规散列相比，它们可以更节省空间，特别是当您使用的string的大小可以是数以亿计的字母，并且字母非常小时（{A，G，T，C}）。 它们通常用于评估基因组中是否存在某种k聚体。 这里有一个相关的例子。
编辑：
多重散列函数用于最小化误报。 希望是在所有k-hash函数之间，每个值在比特数组中将具有唯一的签名，而不是每个其他可能的值。 但是，误报确实存在，但可以将其尽量减less到可pipe理的水平。 使用这种技术，您可以散列与其大小无关的元素。 当你search它们时，你使用每个散列函数并检查它们的位值是否都是1。
将其与人类基因组进行比较，其中元素大小的增加显着增加了散列表的大小（表格大小为4 * 4k ）。 这是假设您使用2位/字母对元素进行编码。
如果布隆filter返回一个项目是该集合的成员，则有一定的概率出现误报。 如果只使用单个散列函数来指示集合中的成员资格，则假阳性的概率将高于使用多个散列函数。
