数据库浅谈之 Bloom Filter

HELLO，各位博友好，我是阿呆 🙈🙈🙈

这里是数据库浅谈系列，收录在专栏 DATABASE 中 😜😜😜

本系列阿呆将记录一些数据库领域相关的知识 🏃🏃🏃

OK，兄弟们，废话不多直接开冲 🌞🌞🌞

一 🏠 概述

什么是布隆过滤器

1970 年，Burton Howard Bloom 在论文 Space/Time Trade-offs in Hash Coding with Allowable Errors 提出了 bloom filter

布隆过滤器是一种空间效率很高的随机数据结构，专门用来检测集合中是否存在特定的元素。布隆过滤器由一个长度为m比特的位数组与 k 个独立的哈希函数组成的数据结构

当要向布隆过滤器中插入一个元素时，该元素经过 k 个哈希函数计算产生 k 个哈希值，以哈希值作为位数组中的下标，将所有 k 个对应的比特值由 0 置为 1

当要查询一个元素时，同样将其经过哈希函数计算产生哈希值，然后检查对应的 k 个比特值 ：如果有任意一个比特为 0 ，表明该元素一定不在集合中；如果所有比特均为 1，表明该元素有可能性在集合中

由于可能出现哈希碰撞，不同元素计算的哈希值有可能一样，导致一个不存在的元素有可能对应的比特位为 1，这就是所谓 假阳性。相对地，假阴性 在BF中是绝不会出现的

Bloom Filter 通过极少错误换取了存储空间极大节省，布隆过滤器认为不在的，一定不会在集合中；布隆过滤器认为在的，不一定存在集合中

Bloom filter 的实现一般由一个或多个 bitmap 和多个哈希函数组成，可以用于检索一个元素是否在一个集合中

二 🏠 核心

布隆过滤器优缺点

优点：

节省空间 ：不需要存储数据本身，只需要存储数据对应 hash 比特位
时间复杂度低 ：插入和查找的时间复杂度都为 O(k) ，k 为哈希函数的个数

缺点：

存在假阳性 ：布隆过滤器判断存在，但可能元素实际不在集合中（ 误判率取决于哈希函数个数）
不支持删除元素 ：如果一个元素被删除，但是却不能从布隆过滤器中删除

不支持删除

Counting Bloom Filter 将标准 Bloom Filter 位数组的每一位扩展为一个小的计数器（counter）

在插入元素时给对应的k（k为哈希函数个数）个Counter 的值分别加1，删除元素时给对应的 k 个 Counter 的值分别减 1。Counting Bloom Filter通过多占用几倍的存储空间的代价，给Bloom Filter增加了删除操作

三 🏠 结语

身处于这个浮躁的社会，却有耐心看到这里，你一定是个很厉害的人吧 👍👍👍

各位博友觉得文章有帮助的话，别忘了点赞 + 关注哦，你们的鼓励就是我最大的动力

博主还会不断更新更优质的内容，加油吧！技术人！ 💪💪💪