原创

布隆过滤器(Bloom Filter)

1.

  1. 今天正在搬砖。。突然想到之前在某爆火全国的短视频公司的一次首页列表算法优化
  2. 随着用户量越来越大,之前reids所占的内存也越来越多,响应速度也越来越慢
  3. 开发和产品们终于忍不了决定优化,当时用的就是布隆算法
  4. 今天的我差一点就忘记了算法是咋回事了,甚至大概都忘了
  5. 搜索一圈仅发现一个清晰易懂的文章,决定复制粘贴一下,对于概念理论啥的文字实在不想自己写了太假

直观的说,bloom算法类似一个hash set,用来判断某个元素(key)是否在某个集合中。
和一般的hash set不同的是,这个算法无需存储key的值,对于每个key,只需要k个比特位,每个存储一个标志,用来判断key是否在集合中。

算法:

  1. 首先需要k个hash函数,每个函数可以把key散列成为1个整数
  2. 初始化时,需要一个长度为n比特的数组,每个比特位初始化为0
  3. 某个key加入集合时,用k个hash函数计算出k个散列值,并把数组中对应的比特位置为1
  4. 判断某个key是否在集合时,用k个hash函数计算出k个散列值,并查询数组中对应的比特位,如果所有的比特位都是1,认为在集合中。

优点:不需要存储key,节省空间

缺点:

  1. 算法判断key在集合中时,有一定的概率key其实不在集合中
  2. 无法删除

上面一段话复制于 https://www.cnblogs.com/liyulong1982/p/6013002.html

正文到此结束
本文目录