Hollis的个人博客
Hollis的个人博客

布隆过滤器

Hollis Hollis 收录于 Redis 和 Redis
  约 3800 字 预计阅读 8 分钟  - 次阅读   - 条评论  

面试题

现有50亿个电话号码，给你10万个电话号码，如何要快速准确的判断这些电话号码是否已经存在？

判断是否存在，布隆过滤器了解过吗？

安全连接网址，全球数10亿的网址判断

黑名单校验，识别垃圾邮件

白名单校验，识别出合法用户进行后续处理

是什么

由一个初值都为零的bit数组和多个哈希函数构成，用来快速判断集合中是否存在某个元素

1.布隆过滤器初始状态.png

设计思想

目的：减少内存占用；

方式：不保存数据信息，只是在内存中做一个是否存在的标记flag

本质就是判断具体数据是否存在于一个大的集合中。

备注：

布隆过滤器是一种类似set的数据结构，只是统计结果在巨量数据下有点小瑕疵，不够完美。

布隆过滤器(英语： Bloom Filter) 是 1970 年由布隆提出的。

它实际上是一个很长的二进制数组(00000000)+一系列随机hash算法映射函数，主要用于判断一个元素是否在集合中。

通常我们会遇到很多要判断一个元素是否在某个集合中的业条场景，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、哈希表等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间也会呈现线性增长，最终达到瓶颈。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为O(n),0(logn),0(1)，这个时候隆过滤器 (Bloom Filter)就应运而生。

2.布隆过滤器.png

能干嘛

高效地插入和查询，占用空间少，返回的结果是不确定性+不够完美

重点：一个元素如果判断结果：存在时，元素不一定存在，但是判断结果为不存在时，则一定不存在。

布隆过滤器可以添加元素，但是不能删除元素，由于涉及hashcode判断依据，删除元素会导致误判率增加。

小总结：有，是可能有；无，是肯定无；（可以保证的是，如果布隆过滤器判断一个元素不在一个集合中，那这个元素一定不会在集合中）

布隆过滤器原理

布隆过滤器实现原理和数据结构

  • 原理

    布隆过滤器(Bloom Filter) 是一种专门用来解决去重问题的高级数据结构。

    实质就是一个大型位数组和几个不同的无偏hash函数(无偏表示分布均匀)。由一个初值都为零的bit数组和多个哈希函数构成，用来快速判断某个数据是否存在。但是跟 HyperLogLog 一样，它也一样有那么一点点不精确，也存在一定的误判概率

    3.布隆过滤器初始状态.png

  • 添加key、查询key

    添加key时 使用多个hash函数对key进行hash运算得到一个整数索引值，对位数组长度进行取模运算得到一个位置，每个hash函数都会得到一个不同的位置，将这几个位置都置1就完成了add操作。

    查询key时 只要有其中一位是零就表示这个key不存在，但如果都是1，则不一定存在对应的key.结论：有，是可能有无，是肯定无

  • hash冲突导致数据不精准

    当有变量被加入集合时，通过N个映射函数将这个变量映射成位图中的N个点,把它们置为 1(假定有两个变量都通过 3 个映射函数)。

    4.hash映射.png

    查询某个变量的时候我们只要看看这些点是不是都是 1，就可以大概率知道集合中有没有它了

    如果这些点，有任何一个为零则被查询变量一定不在， 如果都是 1，则被查询变量很可能存在， 为什么说是可能存在，而不是一定存在呢?那是因为映射函数本身就是散列函数，散列函数是会有碰撞的。 (见上图3号坑两个对象都1)

    正是基于布隆过滤器的快速检测特性，我们可以在把数据写入数据库时，使用布隆过滤器做个标记。当缓布缺失后，应用查询数据库时，可以通过查询布隆过滤器快速判断数据是否存在。如果不存在，就不用再去据库中查询了。这样一来，即使发生缓存穿透了，大量请求只会查询Redis和布隆过滤器，而不会积压到数据库，也就不会影响数据库的正常运行。布隆过滤器可以使用Redis实现，本身就能承担较大的并发访问压力

  • hash冲突导致数据不精准2

    哈希函数

    哈希函数的概念是：将任意大小的输入数据转换成特定大小的输出数据的函数，转换后的数据称为哈希值或哈希编码，也叫散列值

    5.哈希函数.jpg

    如果两个散列值是不相同的(根据同一函数)那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果，具有这种性质的散列函数称为单向散列函数。

    散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的，但也可能不同，这种情况称为“散列碰撞 (collision)”。

    用 hash表存储大数据量时，空间效率还是很低，当只有一个 hash 函数时，还很容易发生哈希碰撞。

    Java中hash冲突Java案例
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

    public static void main(String[] args) {
    system.out.println("Aa".hashCode()); 
    system.out.println("BB".hashCode());

    system.out.println("柳柴".hashCode());
    system.out.println("柴柕".hashCode());

    Set<Integer> sets = new HashSet<>();
    int hashCode;
    for(int i = 0; i < 200000; i++) {
        hashCode = new Object().hashCode();
        if(sets.contains(hashCode)) {
            System.out.println("运行到第："+i+"次出现hash冲突,hashcode：" + hashCode);
            continue;
        } 
        sets.add(hashCode);
    }
}

/**
* 2112
* 2112
* 851553
* 851553
* 运行到第：103993 次出现hash冲突,hashcode：213440190
* 运行到第：109440 次出现hash冲突,nashcode：651156501
* 运行到第：143624 次出现hash冲突,hashcode：2038112324
* 运行到第：144557 次出现hash冲突,hashcode：1164664992
* 运行到第：150537 次出现hash冲突,hashcode：273791087
* 运行到第：179149 次出现hash冲突,hashcode：996371445
* 运行到第：182462 次出现hash冲突,hashcode：254720071
* 运行到第：185099 次出现hash冲突,hashcode：1872358815
*/

使用3步骤

  • 初始化bitmap

    布隆过滤器 本质上是由长度为 m 的位向量或位列表(仅包含 0或 1 位值的列表)组成，最初所有的值均设置为0

    6.布隆过滤器初始化.png

  • 添加数据

    当我们向布降过滤器中添加数据时，为了尽量地址不冲突，会使用多个 hash 函数对 key 进行运算，算得一个下标索引值，然后对位数组长度进行取模运算得到一个位置，每个 hash 函数都会算得一个不同的位置。再把位数组的这几个位置都置为 1 就完成了 add 操作。

    例如，我们添加一个字符串wmyskxz，对字符串进行多次hash(key) -> 取模运行 -> 得到坑位

    7.布隆过滤器add操作.png

  • 判断是否存在

    向布隆过滤器查询某个key是否存在时，先把这个 key 通过相同的多个 hash 函数进行运算，查看对应的位置是否都为 1，只要有一个位为零，那么说明布隆过滤器中这个 key 不存在；

    如果这几个位置全都是 1，那么说明极有可能存在；

    因为这些位置的 1 可能是因为其他的 key 存在导致的，也就是前面说过的hash冲突。。。。。

    就比如我们在 add了字符串wmyskxz数据之后，很明显下面1/3/5 这几个位置的 1 是因为第一次添加的 wmyskxz 而导致的；

    此时我们查询一个没添加过的不存在的字符串inexistent-key，它有可能计算后坑位也是1/3/5，这就是误判了

    8.查询不同key时存在误判.png

布隆过滤器误判率，为什么不要删除

布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置变成1了，这样就无法判断究竟是哪个输入产生的，因此误判的根源在于相同的 bit 位被多次映射且置 1。

这种情况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。如果我们直接删除这一位的话，会影响其他的元素

特性：布隆过滤器可以添加元素，但是不能删除元素。因为删掉元素会导致误判率增加。

小总结：

  • 是否存在：有，很很可能有；无是肯定无，100%无
  • 使用时最好不要让实际元素数量远大于初始化数量，一次给够避免扩容
  • 当实际元素数量超过初始化数量时，应该对布隆过滤器进行重建，重新分配一个size 更大的过滤器，再将所有的历史元素批量add进行

布隆过滤器的使用场景

  1. 解决缓存穿透的问题，和redis结合bitmap使用

    缓存穿透是什么

    一般情况下，先查询缓存redis是否有该条数据，缓存中没有时，再查询数据库。当数据库也不存在该条数据时，每次查询都要访问数据库，这就是缓存穿透。

    缓存穿透带来的问题是，当有大量请求查询数据库不存在的数据时，就会给数据库带来压力，甚至会拖垮数据库。

    可以使用布隆过滤器解决缓存穿透的问题

    把已存在数据的key存在布隆过滤器中，相当于redis前面挡着一个布隆过滤器。

    当有新的请求时，先到布隆过滤器中查询是否存在：

    如果布隆过滤器中不存在该条数据则直接返回;

    如果布隆过滤器中已存在，才去查询缓存redis，如果redis里没查询到则再查询Mysql数据库

  2. 黑名单校验，识别垃圾邮件

    发现存在黑名单中的，就执行特定操作。比如：识别垃圾邮件，只要是邮箱在黑名单中的邮件，就识别为垃圾邮件。

    假设黑名单的数量是数以亿计的，存放起来就是非常耗费存储空间的，布隆过滤器则是一个较好的解决方案。

    把所有黑名单都放在布隆过滤器中，在收到邮件时，判断邮件地址是否在布隆过滤器中即可。

优缺点

优点：高效地插入和查询，内存中占用bit空间小

缺点：

  • 不能删除元素。因为删除元素会导致误判率增加，因为hash冲突同一个位置可能存的东西是多个共有的，你删除一个的同时可能也把其他的删除了

  • 存在误判，不能精准过滤；有，是很有可能有；无，是肯定无

收录于 合集・Redis 13
更新于 2025-04-08 
CC BY-NC-SA 4.0
Redis
返回 | 主页
0%