什么情况下需要布隆过滤器

发布日期：2025-01-03 19:07    点击次数：64

什么情况下需要布隆过滤器？先来看几个比较常见的例子字处理软件中，需要检查一个英语单词是否拼写正确在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上在网络爬虫里，一个网址是否被访问过yahoo, gmail等邮箱垃圾邮件过滤功能这几个例子有一个共同的特点：如何判断一个元素是否存在一个集合中？常规思路数组链表树、平衡二叉树、TrieMap (红黑树)哈希表虽然上面描述的这几种数据结构配合常见的排序、二分搜索可以快速高效的处理绝大部分判断元素是否存在集合中的需求。但是当集合里面的元素数量足够大，如果有500万条记录甚至1亿条记录呢？这个时候常规的数据结构的问题就凸显出来了。数组、链表、树等数据结构会存储元素的内容，一旦数据量过大，消耗的内存也会呈现线性增长，最终达到瓶颈。有的同学可能会问，哈希表不是效率很高吗？查询效率可以达到O(1)。但是哈希表需要消耗的内存依然很高。使用哈希表存储一亿 个垃圾 email 地址的消耗？哈希表的做法：首先，哈希函数将一个email地址映射成8字节信息指纹；考虑到哈希表存储效率通常小于50%（哈希冲突）；因此消耗的内存：8 * 2 * 1亿 字节 = 1.6G 内存，普通计算机是无法提供如此大的内存。这个时候，布隆过滤器（Bloom Filter）就应运而生。在继续介绍布隆过滤器的原理时，先讲解下关于哈希函数的预备知识。哈希函数哈希函数的概念是：将任意大小的数据转换成特定大小的数据的函数，转换后的数据称为哈希值或哈希编码。下面是一幅示意图：什么是布隆过滤器？本质上布隆过滤器( BloomFilter )是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。相比于传统的 Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。布隆过滤器原理布隆过滤器内部维护一个bitArray(位数组)， 开始所有数据全部置 0 。当一个元素过来时，能过多个哈希函数（hash1,hash2,hash3…）计算不同的在哈希值，并通过哈希值找到对应的bitArray下标处，将里面的值 0 置为 1 。需要说明的是，布隆过滤器有一个误判率的概念，误判率越低，则数组越长，所占空间越大。误判率越高则数组越小，所占的空间越小。以上图为例，具体的操作流程：假设集合里面有3个元素{x, y, z}，哈希函数的个数为3。首先将位数组进行初始化，将里面每个位都设置位0。对于集合里面的每一个元素，将元素依次通过3个哈希函数进行映射，每次映射都会产生一个哈希值，这个值对应位数组上面的一个点，然后将位数组对应的位置标记为1。查询W元素是否存在集合中的时候，同样的方法将W通过哈希映射到位数组上的3个点。如果3个点的其中有一个点不为1，则可以判断该元素一定不存在集合中。反之，如果3个点都为1，则该元素可能存在集合中。注意：此处不能判断该元素是否一定存在集合中，可能存在一定的误判率。可以从图中可以看到：假设某个元素通过映射对应下标为4，5，6这3个点。虽然这3个点都为1，但是很明显这3个点是不同元素经过哈希得到的位置，因此这种情况说明元素虽然不在集合中，也可能对应的都是1，这是误判率存在的原因。## 为什么不直接使用hashtableHash table的存储效率一般只有50%,为了避免碰撞的问题，一般哈希存储到一半的时候都采取内存翻倍或者其他措施，所以很耗费内存。Hash面临的问题就是冲突。假设 Hash 函数是良好的，如果我们的位阵列长度为 m个点，那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳 m/100 个元素。解决方法较简单， 使用k>1的布隆过滤器，即k个函数将每个元素改为对应于k个bits，因为误判度会降低很多，并且如果参数k和m选取得好，一半的m可被置为1。布隆过滤器的设计一般会由用户决定增加元素的个数n和误差率p，后面的所有参数都由系统来设计。1.首先根据传入的n和p计算需要的内存大小m bits:2.再由m,n得到hash function个数k:布隆过滤器添加元素将要添加的元素给k个哈希函数得到对应于位数组上的k个位置将这k个位置设为1布隆过滤器查询元素将要查询的元素给k个哈希函数得到对应于位数组上的k个位置如果k个位置有一个为0，则肯定不在集合中如果k个位置全部为1，则可能在集合中下图是Bloomfilter误判率表:为每个URL分配两个字节就可以达到千分之几的冲突。比较保守的实现是，为每个URL分配4个字节，项目和位数比是1∶32，误判率是0.00000021167340。对于5000万数量级的URL，布隆过滤器只占用200MB的空间。c++代码:定义布隆滤波器的结构体定义写入文件的结构体根据传入的元素个数n和误差率p， 计算布隆滤波器的内存大小m bits和hash function个数k:初始化bloomfilter, 根据size分配内存:释放内存:ResetBloom filter:计算hash函数，这里使用的是MurmurHash2：计算多少个hash函数:向Bloomfilter新增元素:查询元素:把bloomfilter保存在文件里:读取文件的bloomfilter:完整的代码: