侧边栏壁纸
博主头像
996worker

祇園精舎の鐘の聲, 諸行無常の響き有り。

  • 累计撰写 159 篇文章
  • 累计创建 44 个标签
  • 累计收到 6 条评论

Bloom Filter -- 布隆过滤器

996worker
2022-05-04 / 0 评论 / 0 点赞 / 18 阅读 / 721 字
温馨提示:
本文最后更新于 2022-05-04,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

Intro

How do you implement the blacklist of the mail system?

布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难。

Bloom filter theory

当一个元素加入布隆过滤器中的时候,会进行如下操作:

  • 使用布隆过滤器中的哈希函数对元素值进行计算,得到哈希值(有几个哈希函数得到几个哈希值)。
  • 根据得到的哈希值,在位数组中把对应下标的值置为 1。

当我们需要判断一个元素是否存在于布隆过滤器的时候,会进行如下操作:

  • 对给定元素再次进行相同的哈希计算;
  • 得到值之后判断位数组中的每个元素是否都为 1,如果值都为 1,那么说明这个值在布隆过滤器中,如果存在一个值不为 1,说明该元素不在布隆过滤器中。

To sum up, 布隆过滤器说某个元素存在,小概率会误判(Hash碰撞)。布隆过滤器说某个元素不在,那么这个元素一定不在。布隆过滤器能够说明某个东西一定不存在!

Usage

  1. 判断给定数据是否存在:
    • 比如判断一个数字是否存在于包含大量数字的数字集中(数字集很大,5 亿以上!);
    • 防止缓存穿透(判断请求的数据是否有效避免直接绕过缓存请求数据库)等等;
    • 邮箱的垃圾邮件过滤、黑名单功能等等。
  2. 去重:比如爬给定网址的时候对已经爬取过的 URL 去重。

Implementation

如果你想要手动实现一个的话,你需要:

  1. 一个合适大小的位数组保存数据;
  2. 几个不同的哈希函数;
  3. 添加元素到位数组(布隆过滤器)的方法实现;
  4. 判断给定元素是否存在于位数组(布隆过滤器)的方法实现。
0

评论区