先来看几个比较常见的例子
这几个例子有一个共同的特点： 如何判断一个元素是否存在一个集合中？
常规思路
数组
链表
树、平衡二叉树、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。
布隆过滤器添加元素
布隆过滤器查询元素
3.2布隆过滤器实现
下面给出python的实现，使用murmurhash算法
至于Java版的实现，可以参考:
以上就是本篇文章【Bloom Filter实现大数据集查询】的全部内容了，欢迎阅览 ！ 文章地址：http://sicmodule.glev.cn/news/8955.html 资讯 企业新闻 行情 企业黄页 同类资讯 首页 网站地图 返回首页 歌乐夫资讯移动站 http://sicmodule.glev.cn/mobile/ , 查看更多