【算法一】布隆过滤器算法维基百科详细说明

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【算法一】布隆过滤器算法维基百科详细说明，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2930字，纯文字阅读大概需要5分钟。

内容图文

甲布隆过滤器是空间高效的概率 数据结构，通过设想伯顿霍华德布卢姆于1970年，是用于测试一个是否元件是一个的成员组。可能会出现假阳性匹配，但否定否定匹配-换句话说，查询返回“可能在集合中”或“绝对不在集合中”。元素可以添加到集合中，但不能删除（尽管可以通过计数Bloom过滤器变体来解决）；添加的项目越多，误报的可能性越大。

Bloom提出了一种应用技术，如果应用了“常规”的无错误哈希技术，则源数据量将需要不切实际的大量内存。他举了一个针对500,000个单词的字典的断字算法的示例，其中90％遵循简单的断字规则，但是其余的10％需要昂贵的磁盘访问来检索特定的断字模式。有了足够的核心内存，可以使用无错误的哈希来消除所有不必要的磁盘访问；另一方面，由于核心内??存有限，Bloom的技术使用较小的哈希区域，但仍消除了大多数不必要的访问。例如，仅理想无错误哈希所需大小的15％的哈希区域仍可消除85％的磁盘访问。^[1]

更一般地，对于1％的误报概率，每个元素需要少于10位，而与集合中元素的大小或数量无关。

 

算法描述

? 布隆过滤器的一个示例，代表集合{?x，y，z?}。彩色箭头显示每个设置元素映射到的位数组中的位置。元素w不在集合{?x，y，z?}中，因为它散列到一个包含0的位数组位置。在此图中，m??= 18，k = 3。

一个空的布隆过滤器是一个位阵列的米位，全部设置为0。还必须有?不同的散列函数所定义，其中的每一个映射或散列一些组元件向之一米阵列位置，产生一个均匀随机分布。通常，k是一个小常数，取决于所需的误错误率 ε，而m与k和要添加的元素数成正比。

要添加元素，请将其提供给k个哈希函数中的每一个以获取k个数组位置。将所有这些位置的位设置为1。

要查询元素（测试元素是否在集合中），请将其馈送到k个哈希函数中的每一个以获取k个数组位置。如果这些位置的任何位为0，则该元素肯定不在集合中；如果是的话，那么插入时所有位都将设置为1。如果全部为1，则该元素在集合中，或者在插入其他元素期间偶然将这些位设置为1，从而导致假肯定。在简单的Bloom过滤器中，无法区分这两种情况，但是更高级的技术可以解决此问题。

设计k个不同的独立哈希函数的要求可能对大k来说是禁止的。对于具有宽输出的良好哈希函数，此类哈希的不同位字段之间应该几乎没有关联，因此可以通过将其输出切成多个位来使用这种类型的哈希来生成多个“不同”哈希函数领域。或者，可以将k个不同的初始值（例如0、1，...，k  -1）传递给采用初始值的哈希函数；或将这些值添加（或追加）到密钥中。对于较大的m和/或k，散列函数之间的独立性可以放宽，而误报率的增加可以忽略不计。^[3]?（具体地，迪林格＆Manolios（2004年b）显示导出的有效性 ?使用指数增强双散列或三重散列，变体双散列是有效地与两个或三个散列值接种简单随机数生成器）。

从这个简单的布隆过滤器中删除一个元素是不可能的，因为无法知道应该清除映射到的k位中的哪一个。尽管将这k个位中的任何一个设置为零就足以删除该元素，但它也将删除碰巧映射到该位的任何其他元素。由于简单算法无法确定是否添加了其他任何会影响要删除元素的位的元素，因此清除任何位都可能会带来假阴性的可能性。

可以通过使第二个Bloom过滤器包含已删除的项目来模拟从Bloom过滤器中一次删除元素。然而，第二滤波器中的误报变成复合滤波器中的误报，这可能是不希望的。在这种方法中，不可能重新添加以前删除的项目，因为必须将其从“已删除”的过滤器中删除。

通常情况下，所有键都是可用的，但枚举起来很昂贵（例如，需要读取许多磁盘）。当误报率过高时，可以重新生成过滤器。这应该是一个相对罕见的事件。

 

内容总结

以上是互联网集市为您收集整理的【算法一】布隆过滤器算法维基百科详细说明全部内容，希望文章能够帮你解决【算法一】布隆过滤器算法维基百科详细说明所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---