0%

Redis布隆过滤器

见龙在田,利见大人。 —— 《易经》之乾卦的第二爻(九二爻) 译为一个胸怀大志的人,已经崭露头角。今指一个人仕途顺利,初露锋芒,得到领导的赏识,前途光明。

一、基础

  1. 概念
          布隆过滤器(Bloom Filter)是1970年由布隆提出的,是一个很长的二进制向量和一系列随机映射函数。实质上,它是一种概率型数据结构(probabilistic data structure),其特点是高效地插入和查询,可以用来快速判断某个元素存在或不存在,空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。它被广泛用于网页黑名单系统、垃圾邮件过滤系统、爬虫的网址判重系统以及解决缓存穿透问题。

  2. 原理

    • 布隆过滤器是一个bit向量或者说bit数组

结构

  • 布隆过滤器离不开哈希函数,它有如下特点

    • 经典的哈希函数都有无限大的输入值域(无穷大)。
    • 经典的哈希函数的输出域都是固定的范围(有穷大,假设输出域为S)
    • 当给哈希函数传入相同的值时,返回值必一样
    • 当给哈希函数传入不同的输入值时,返回值可能一样,也可能不一样。
    • 输入值会尽可能均匀的分布在S上
  • 如果我们要映射一个值到布隆过滤器中,需要使用多个不同的哈希函数生成多个哈希值,并对每个生成的哈希值指向的bit位设为1,例如针对值“baidu”和三个不同的哈希函数分别生成了哈希值1、4、7,则上图转变为:

百度

  • 再存一个值“tencent”,假设三个不同的哈希函数得到的哈希值分别为3、4、8,图继续变为:

腾讯

  • 如图,4这个bit位由于两个值的哈希函数都返回了这个bit位,因此它被覆盖了。
  • 当需要查询“dianping”这个值是否存在,假设三个哈希函数分别得到哈希值1、5、8。结果发现5这个bit位上的值为0,说明没有任何一个值映射到这个bit位上,因此可以很确定地说“dianping”这个值不存在。
  • 当需要查询“baidu”这个值是否存在,那么三个哈希函数肯定会拿到1、4、7三个值。然后发现这三个bit位上的值均为1,那么可以说“baidu”这个值可能存在,即哈希冲突的问题。
  1. 适用场景
    • 爬虫URL去重
    • 缓存穿透问题

二、使用

  1. 使用原生bitmap
  2. 使用bloom-filter模块

全置为1的问题

三、参考

  1. 参考一
  2. 参考二