先来看几个比较常见的例子

字处理软件中，需要检查一个英语单词是否拼写正确

在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上

在网络爬虫里，一个网址是否被访问过

yahoo, gmail等邮箱垃圾邮件过滤功能

这几个例子有一个共同的特点： 如何判断一个元素是否存在一个集合中？

常规思路
数组
链表
树、平衡二叉树、Trie
Map (红黑树)
哈希表

虽然上面描述的这几种数据结构配合常见的排序、二分搜索可以快速高效的处理绝大部分判断元素是否存在集合中的需求。但是当集合里面的元素数量足够大，如果有500万条记录甚至1亿条记录呢？这个时候常规的数据结构的问题就凸显出来了。数组、链表、树等数据结构会存储元素的内容，一旦数据量过大，消耗的内存也会呈现线性增长，最终达到瓶颈。有的同学可能会问，哈希表不是效率很高吗？查询效率可以达到O(1)。但是哈希表需要消耗的内存依然很高。使用哈希表存储一亿 个垃圾 email 地址的消耗？哈希表的做法：首先，哈希函数将一个email地址映射成8字节信息指纹；考虑到哈希表存储效率通常小于50%（哈希冲突）；因此消耗的内存：8 * 2 * 1亿 字节 = 1.6G 内存，普通计算机是无法提供如此大的内存。这个时候，布隆过滤器（Bloom Filter）就应运而生。在继续介绍布隆过滤器的原理时，先讲解下关于哈希函数的预备知识。

巴顿.布隆于一九七零年提出

一个很长的二进制向量 （位数组）

一系列随机函数 (哈希)

空间效率和查询效率高

有一定的误判率（哈希表是精确匹配）

存在：在集合内（可能错误）”和“不在集合内（绝对不在集合内）”两种情况，可见 Bloom filter 是牺牲了正确率换取时间和空间。

3.1布隆过滤器原理

布隆过滤器（Bloom Filter）的核心实现是一个超大的位数组和几个哈希函数。假设位数组的长度为m，哈希函数的个数为k。

布隆过滤器添加元素

将要添加的元素给k个哈希函数

将这k个位置设为1

布隆过滤器查询元素

将要查询的元素给k个哈希函数

如果k个位置有一个为0，则肯定不在集合中

如果k个位置全部为1，则可能在集合中

3.2布隆过滤器实现

下面给出python的实现，使用murmurhash算法

至于Java版的实现，可以参考:

    以上就是本篇文章【Bloom Filter实现大数据集查询】的全部内容了，欢迎阅览 ！ 文章地址：http://sicmodule.glev.cn/news/8955.html 
     资讯      企业新闻      行情      企业黄页      同类资讯      首页      网站地图      返回首页 歌乐夫资讯移动站 http://sicmodule.glev.cn/mobile/ , 查看更多