【高阶数据结构】布隆过滤器（BloomFilter）

1. 概念

1.1 背景引入

背景：在计算机软件中，一个常见的需求就是 在一个集合中查找一个元素是否存在 ，比如：1. Word 等打字软件需要判断用户键入的单词是否在字典中存在 2. 浏览器等网络爬虫程序需要保存一个列表来记录已经遍历过的 url，遇到一个 url 先判断是否已经访问过 3. FBI 系统中需要判断名称是否在嫌疑人名单中。一般来说都会考虑使用哈希表等键值结构进行存储，以此提高查询的效率，但是在海量数据情况下存在存储空间占用过高的情况：

例如：在 Gmail 等大型邮件服务商需要过滤垃圾邮件，但是发送垃圾邮件的地址不断会注册新地址，因此将它们全部存储起来需要大量内存资源，假设有 40亿个垃圾邮件地址，每个地址使用 4 字节存储，大概需要占用 16G 内存空间，常见的方案汇总如下：

直接使用哈希表进行存储，缺点：空间存储占用过高 ✖
使用位图数据结构，缺点：位图只适合存储整型数据，应对字符串无法适用 ✖
使用布隆过滤器，将位图和哈希映射有效结合 ✔

1.2 布隆过滤器概念

布隆过滤器：是位图 + 哈希的结合，简单来说就是通过多个哈希函数将键映射到位图当中，是一种紧凑的，高效的 概率型数据结构，它可以高效的进行插入、查询等操作，并且能够告诉你某一个元素 一定不存在或者可能存在

例如上图是一个简单的布隆过滤器示意图，hash1函数将"baidu"映射到位图为5的位置，hash2函数将"baidu"映射到位图为2的位置，hash3函数将"baidu"映射到位图为1的位置

2. 布隆过滤器模拟实现

2.1 结构定义

在上节已经介绍过，布隆过滤器本质就是 “哈希 + 位图” 的结合，因此我们想要自定义一个布隆过滤器，就需要准备位图和哈希函数：

位图：此处采用上节模拟实现的自定义位图结构
哈希函数：采用自定义 HashFunc 类型

目录结构：

main.go：

// MyBloomFilter 自定义布隆过滤器
type MyBloomFilter struct {bitMap    mybitmap.MyBitMap // 自定义位图hashArray [3]hash.HashFunc  // 自定义哈希函数数组seeds     [3]int            // 随机数种子usedSize  int               // 存储元素个数
}// InitBloomFilter 初始化布隆过滤器函数
func InitBloomFilter() *MyBloomFilter {var bloomFilter MyBloomFilterbloomFilter.bitMap = *mybitmap.InitBitMap()bloomFilter.seeds = [3]int{11, 22, 33}bloomFilter.usedSize = 0for i := 0; i < 3; i++ {bloomFilter.hashArray[i] = *hash.InitHashFunc(100, bloomFilter.seeds[i])}return &bloomFilter
}

hash.go：

package hashimport "hash/crc32"// HashFunc 哈希函数类型
type HashFunc struct {capacity int // 容量seed     int // 随机数种子
}// InitHashFunc 初始化哈希函数
func InitHashFunc(capacity, seed int) *HashFunc {return &HashFunc{capacity: capacity,seed:     seed,}
}// Hash 哈希方法: 返回key映射结果
func (hashFunc *HashFunc) Hash(key string) int {v := int(crc32.ChecksumIEEE([]byte(key)))return (hashFunc.capacity * hashFunc.seed % 80) & (v >> 16)
}

bitmap.go：

package mybitmap// MyBitMap 自定义位图结构体
type MyBitMap struct {elem     []byte // 字节数组usedSize int    // 存储的元素个数
}// InitBitMap 初始化函数
func InitBitMap() *MyBitMap {var bitMap MyBitMapbitMap.elem = make([]byte, 10)bitMap.usedSize = 0return &bitMap
}// Set 添加元素
func (bitMap *MyBitMap) Set(num int) {if num < 0 {panic("num必须大于等于0!")}// 1. 获取字节数组对应存储下标var elemIndex = num / 8// 2. 获取所在字节的比特位var bitIndex = num % 8// 3. 使用或运算bitMap.elem[elemIndex] |= 1 << bitIndex// 4. 存储元素个数+1bitMap.usedSize++
}// Get 查找某个元素是否存在
func (bitMap *MyBitMap) Get(num int) bool {if num < 0 {panic("num必须大于等于0!")}// 1. 获取字节数组对应存储下标var elemIndex = num / 8// 2. 获取所在字节的比特位var bitIndex = num % 8// 3. 使用与运算return !(bitMap.elem[elemIndex]&(1<<bitIndex) == 0)
}// Reset 重置某个元素
func (bitMap *MyBitMap) Reset(num int) {if num < 0 {panic("num必须大于等于0!")}// 1. 获取字节数组对应存储下标var elemIndex = num / 8// 2. 获取所在字节的比特位var bitIndex = num % 8// 3. 查找元素是否存在if bitMap.Get(num) {bitMap.usedSize--}// 4. 使用 ~运算 + &运算bitMap.elem[elemIndex] &= ^(1 << bitIndex)
}// Reset2 重置某个元素
func (bitMap *MyBitMap) Reset2(num int) {if num < 0 {panic("num必须大于等于0!")}// 1. 获取字节数组对应存储下标var elemIndex = num / 8// 2. 获取所在字节的比特位var bitIndex = num % 8// 3. 查找元素是否存在if bitMap.Get(num) {// 使用异或bitMap.elem[elemIndex] ^= 1 << bitIndexbitMap.usedSize--} else {// nothing to do....}
}// GetUsedSize 获取已经存储元素个数
func (bitMap *MyBitMap) GetUsedSize() int {return bitMap.usedSize
}

💡 提示：如果没有学过位图的数据结构实现，可以参考我的另一篇博客：https://blog.csdn.net/weixin_62533201/article/details/145216138

2.2 插入数据

上图为插入数据到布隆过滤器示意图：我们只需要分别调用三个哈希函数计算各自的位图存储位置，然后保存到位图即可！代码如下：

// Insert 插入值到布隆过滤器当中
func (bloomFilter *MyBloomFilter) Insert(key string) {// 分别计算三个哈希函数计算值for i := 0; i < len(bloomFilter.hashArray); i++ {value := bloomFilter.hashArray[i].Hash(key)// 插入到位图中bloomFilter.bitMap.Set(value)}
}

2.3 查询数据

上图为从布隆过滤器中查询数据示意图：我们依然需要分别调用三个哈希函数计算各自的位图存储位置，分别查询位图目标位置是否为1，如果某一个为 0，则表明这个数据一定不存在；如果全部为 1，则表明这个数据可能存在! 这也是布隆过滤器的缺点：会存在误判的可能！因为存在一种情况，如果其他 key 对应存储位置也恰好是 1、2、5，此时出现了哈希冲突，因此无法保障一个元素一定存在，代码如下：

// MightContain 从布隆过滤器中查询元素
func (bloomFilter *MyBloomFilter) MightContain(key string) bool {// 分别计算三个哈希函数对应值for i := 0; i < len(bloomFilter.hashArray); i++ {value := bloomFilter.hashArray[i].Hash(key)// 判断值是否为0if !bloomFilter.bitMap.Get(value) {return false}}// 全部为1判断为存在（存在误判可能）return true
}

💡 提示：布隆过滤器存在误判的可能！适用于对误判率敏感度不高的场景

2.4 删除数据

如果采用上述结构来实现布隆过滤器，不建议提供删除操作，因为会增加其他元素的误判率！比如存在一种情况"baidu"映射的位置是1、5、7，"tencent"映射的位置是1、3、4，此时删除"baidu"对应的1、5、7，就会导致1处为0，查询"tencent"就会返回不存在！

💡 温馨提示：如果想要让布隆过滤器支持删除操作，可以修改对应数据结构，比如给对应比特位设置 k 个计数器（k为哈希函数的个数），删除一次就将对应k个计数器-1，但是依旧存在以下缺点：

存在序号回绕问题：计数器的值可能溢出
依旧无法解决布隆过滤器的误判问题

2.5 完整代码

package mainimport ("bloomfilter/hash""bloomfilter/mybitmap""fmt"
)// MyBloomFilter 自定义布隆过滤器
type MyBloomFilter struct {bitMap    mybitmap.MyBitMap // 自定义位图hashArray [3]hash.HashFunc  // 自定义哈希函数数组seeds     [3]int            // 随机数种子usedSize  int               // 存储元素个数
}// InitBloomFilter 初始化布隆过滤器函数
func InitBloomFilter() *MyBloomFilter {var bloomFilter MyBloomFilterbloomFilter.bitMap = *mybitmap.InitBitMap()bloomFilter.seeds = [3]int{11, 22, 33}bloomFilter.usedSize = 0for i := 0; i < 3; i++ {bloomFilter.hashArray[i] = *hash.InitHashFunc(100, bloomFilter.seeds[i])}return &bloomFilter
}// Insert 插入值到布隆过滤器当中
func (bloomFilter *MyBloomFilter) Insert(key string) {// 分别计算三个哈希函数计算值for i := 0; i < len(bloomFilter.hashArray); i++ {value := bloomFilter.hashArray[i].Hash(key)// 插入到位图中bloomFilter.bitMap.Set(value)}
}// MightContain 从布隆过滤器中查询元素
func (bloomFilter *MyBloomFilter) MightContain(key string) bool {// 分别计算三个哈希函数对应值for i := 0; i < len(bloomFilter.hashArray); i++ {value := bloomFilter.hashArray[i].Hash(key)// 判断值是否为0if !bloomFilter.bitMap.Get(value) {return false}}// 全部为1判断为存在（存在误判可能）return true
}func main() {var bloomFilter = InitBloomFilter()// 插入数据bloomFilter.Insert("DiDi")bloomFilter.Insert("baidu")fmt.Println(bloomFilter.bitMap)// 查询元素fmt.Println(bloomFilter.MightContain("DiDi"))fmt.Println(bloomFilter.MightContain("baidu"))fmt.Println(bloomFilter.MightContain("tencent"))fmt.Println(bloomFilter.MightContain("alibaba"))
}