博客主页:🏆看看是李XX还是李歘歘 🏆

🌺每天不定期分享一些包括但不限于计算机基础、算法、后端开发相关的知识点,以及职场小菜鸡的生活。🌺

💗点关注不迷路,总有一些📖知识点📖是你想要的💗

⛽️今天的内容是    布隆过滤器(BloomFilter)原理和实现      ⛽️💻💻💻

定义

布隆过滤器是一种比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”。实际上是一个很长的二进制向量和一系列随机映射函数,二进制存储的数据是0或1,默认是0。0代表不存在某个数据,1代表存在某个数据。

用途

主要用于处理数据的过滤,减少磁盘 IO 或者网络请求。例如:网页URL 去重(网址进行过滤,已经存在布隆中的网址,不在读取;)、垃圾邮件识别(垃圾邮件过滤,发送方地址命中布隆过滤器的黑名单,则认定为垃圾邮件。)、黑名单、查询加速【比如基于KV结构的数据】、集合元素重复的判断、解决Redis缓存穿透问题;等场景。

原理

背景:通常判断某个元素是否存在,会用HashMap,将值映射到 HashMap 的 Key,然后可以在 O(1) 的时间复杂度内返回结果,效率高。但是 HashMap 的实现也有缺点,例如存储容量占比高,考虑到负载因子的存在,通常空间是不能被用满的,但是值很多,例如上亿的时候,那 HashMap 占据的内存大小就会非常大了。或者数据集存储在远程服务器上,本地服务接受输入,而数据集非常大不可能一次性读进内存构建 HashMap 的时候,也会存在问题。

布隆过滤器的实现原理:通过K个散列函数将一个元素映射成位数组中的K个点,把它们置为1。检索时,我们只要看看K个点是不是都是1,就知道集合中有没有它了:如果这些点有任何一个0,则被检元素一定不在;如果都是1,则被检元素很可能存在。

因为每个点并不是只有一个元素会占用,这个点的值可能会被其他元素覆盖,如果K个点中有一个点为0,说明这个元素一定没有映射,如果都是1,可能是其他元素刚刚好将这个元素的K个点都置为1了。

实现

存入

布隆过滤器是一个二进制数据的集合。存入过程如下:

  1. 通过K个哈希函数计算该数据,返回K个计算出的hash值
  2. 这些K个hash值映射到对应的K个二进制的数组下标
  3. 将K个下标对应的二进制数据改成1。

查询

布隆过滤器主要作用就是查询一个数据是否在这个二进制的集合中。查询过程如下:

  1. 通过K个哈希函数计算该数据,对应计算出的K个hash值
  2. 通过hash值找到对应的二进制的数组下标
  3. 判断:如果存在一处位置的二进制数据是0,那么该数据不存在。如果都是1,该数据可能存在集合中。

优点

  1. 由于存储的是二进制数据,所以占用的空间很小;
  2. 它的插入和查询速度是非常快的,时间复杂度是O(K);
  3. 保密性很好,因为本身不存储任何原始数据,只有二进制数据。

缺点

  1. 概率型数据结构,可能不准确,只能确定某元素一定不存在或者可能存在,不能确定某元素真的存在
  2. 删除困难,由于映射的K个点中可能出现多个元素共用的情况,删除的过程中,这几个点的变化可能会涉及其他值的变化,所以不易删除(不是不能)

Counting Bloom Filter 的原理:

Counting Bloom Filter 的出现,解决了BloomFilter删除困难的问题,它将标准 Bloom Filter 位数组的每一位扩展为一个小的计数器(Counter),在插入元素时给对应的 k (k 为哈希函数个数)个 Counter 的值分别加 1,删除元素时给对应的 k 个 Counter 的值分别减 1。Counting Bloom Filter 通过多占用几倍的存储空间的代价, 给 Bloom Filter 增加了删除操作。基本原理是不是很简单?看下图就能明白它和 Bloom Filter 的区别在哪。

补充

如何选择哈希函数个数和布隆过滤器长度?

  1. 布隆过滤器长度小,所有的 bit 位很快会被置为 1,那么查询任何值都会返回“可能存在”,起不到过滤的目的了。布隆过滤器的长度会直接影响误报率,布隆过滤器越长其误报率越小。
  2. 哈希函数的个数需要权衡,个数越多则布隆过滤器 bit 位置位 1 的速度越快,且布隆过滤器的效率越低;但是如果太少的话,那我们的误报率会变高。

哈希函数个数和布隆过滤器长度有个公式可以计算,包括Counting Bloom Filter中计数器大小的选择也有公式

Logo

华为云1024程序员节送福利,参与活动赢单人4000元礼包,更有热门技术干货免费学习

更多推荐