【高阶数据布局】布隆过滤器（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：

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

复制代码

hash.go：

1. package hash
3. import "hash/crc32"
5. // HashFunc 哈希函数类型
6. type HashFunc struct {
7.         capacity int // 容量
8.         seed     int // 随机数种子
9. }
11. // InitHashFunc 初始化哈希函数
12. func InitHashFunc(capacity, seed int) *HashFunc {
13.         return &HashFunc{
14.                 capacity: capacity,
15.                 seed:     seed,
16.         }
17. }
19. // Hash 哈希方法: 返回key映射结果
20. func (hashFunc *HashFunc) Hash(key string) int {
21.         v := int(crc32.ChecksumIEEE([]byte(key)))
22.         return (hashFunc.capacity * hashFunc.seed % 80) & (v >> 16)
23. }

复制代码

bitmap.go：

1. package mybitmap
3. // MyBitMap 自定义位图结构体
4. type MyBitMap struct {
5.         elem     []byte // 字节数组
6.         usedSize int    // 存储的元素个数
7. }
9. // InitBitMap 初始化函数
10. func InitBitMap() *MyBitMap {
11.         var bitMap MyBitMap
12.         bitMap.elem = make([]byte, 10)
13.         bitMap.usedSize = 0
14.         return &bitMap
15. }
17. // Set 添加元素
18. func (bitMap *MyBitMap) Set(num int) {
19.         if num < 0 {
20.                 panic("num必须大于等于0!")
21.         }
22.         // 1. 获取字节数组对应存储下标
23.         var elemIndex = num / 8
24.         // 2. 获取所在字节的比特位
25.         var bitIndex = num % 8
26.         // 3. 使用或运算
27.         bitMap.elem[elemIndex] |= 1 << bitIndex
28.         // 4. 存储元素个数+1
29.         bitMap.usedSize++
30. }
32. // Get 查找某个元素是否存在
33. func (bitMap *MyBitMap) Get(num int) bool {
34.         if num < 0 {
35.                 panic("num必须大于等于0!")
36.         }
37.         // 1. 获取字节数组对应存储下标
38.         var elemIndex = num / 8
39.         // 2. 获取所在字节的比特位
40.         var bitIndex = num % 8
41.         // 3. 使用与运算
42.         return !(bitMap.elem[elemIndex]&(1<<bitIndex) == 0)
43. }
45. // Reset 重置某个元素
46. func (bitMap *MyBitMap) Reset(num int) {
47.         if num < 0 {
48.                 panic("num必须大于等于0!")
49.         }
50.         // 1. 获取字节数组对应存储下标
51.         var elemIndex = num / 8
52.         // 2. 获取所在字节的比特位
53.         var bitIndex = num % 8
54.         // 3. 查找元素是否存在
55.         if bitMap.Get(num) {
56.                 bitMap.usedSize--
57.         }
58.         // 4. 使用 ~运算 + &运算
59.         bitMap.elem[elemIndex] &= ^(1 << bitIndex)
60. }
62. // Reset2 重置某个元素
63. func (bitMap *MyBitMap) Reset2(num int) {
64.         if num < 0 {
65.                 panic("num必须大于等于0!")
66.         }
67.         // 1. 获取字节数组对应存储下标
68.         var elemIndex = num / 8
69.         // 2. 获取所在字节的比特位
70.         var bitIndex = num % 8
71.         // 3. 查找元素是否存在
72.         if bitMap.Get(num) {
73.                 // 使用异或
74.                 bitMap.elem[elemIndex] ^= 1 << bitIndex
75.                 bitMap.usedSize--
76.         } else {
77.                 // nothing to do....
78.         }
79. }
81. // GetUsedSize 获取已经存储元素个数
82. func (bitMap *MyBitMap) GetUsedSize() int {
83.         return bitMap.usedSize
84. }

复制代码

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

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

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

复制代码

2.3 查询数据

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

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

复制代码

  💡 提示：布隆过滤器存在误判的大概！实用于对误判率敏感度不高的场景
  2.4 删除数据

如果接纳上述布局来实现布隆过滤器，不发起提供删除操纵，由于会增长其他元素的误判率！好比存在一种情况"baidu"映射的位置是1、5、7，"tencent"映射的位置是1、3、4，此时删除"baidu"对应的1、5、7，就会导致1处为0，查询"tencent"就会返回不存在！
   💡 温馨提示：如果想要让布隆过滤器支持删除操纵，可以修改对应数据布局，好比给对应比特位设置 k 个计数器（k为哈希函数的个数），删除一次就将对应k个计数器-1，但是仍然存在以下缺点：
  

• 存在序号回绕标题：计数器的值大概溢出
  
• 仍然无法办理布隆过滤器的误判标题
  

  2.5 完备代码

1. package mainimport (        "bloomfilter/hash"        "bloomfilter/mybitmap"        "fmt")// MyBloomFilter 自定义布隆过滤器
2. type MyBloomFilter struct {
3.         bitMap    mybitmap.MyBitMap // 自定义位图
4.         hashArray [3]hash.HashFunc  // 自定义哈希函数数组
5.         seeds     [3]int            // 随机数种子
6.         usedSize  int               // 存储元素个数
7. }
9. // InitBloomFilter 初始化布隆过滤器函数
10. func InitBloomFilter() *MyBloomFilter {
11.         var bloomFilter MyBloomFilter
12.         bloomFilter.bitMap = *mybitmap.InitBitMap()
13.         bloomFilter.seeds = [3]int{11, 22, 33}
14.         bloomFilter.usedSize = 0
15.         for i := 0; i < 3; i++ {
16.                 bloomFilter.hashArray[i] = *hash.InitHashFunc(100, bloomFilter.seeds[i])
17.         }
18.         return &bloomFilter
19. }
20. // Insert 插入值到布隆过滤器当中
21. func (bloomFilter *MyBloomFilter) Insert(key string) {
22.         // 分别计算三个哈希函数计算值
23.         for i := 0; i < len(bloomFilter.hashArray); i++ {
24.                 value := bloomFilter.hashArray[i].Hash(key)
25.                 // 插入到位图中
26.                 bloomFilter.bitMap.Set(value)
27.         }
28. }
29. // MightContain 从布隆过滤器中查询元素
30. func (bloomFilter *MyBloomFilter) MightContain(key string) bool {
31.         // 分别计算三个哈希函数对应值
32.         for i := 0; i < len(bloomFilter.hashArray); i++ {
33.                 value := bloomFilter.hashArray[i].Hash(key)
34.                 // 判断值是否为0
35.                 if !bloomFilter.bitMap.Get(value) {
36.                         return false
37.                 }
38.         }
39.         // 全部为1判断为存在（存在误判可能）
40.         return true
41. }
42. 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"))}

复制代码

步伐运行结果：

3. 布隆过滤器小结

3.1 长处

• 布隆过滤器的插入和查询时间复杂度都为O(k)，k为哈希函数的个数，服从非常高
  
• 布隆过滤器可以存在多个哈希函数，在分布式场景下也可以并行盘算提升服从，且相互不干扰
  
• 布隆过滤器可以存储字符串等范例，相比位图扩展性更高
  
• 布隆过滤器在海量数据场景下，存储空间使用率高
  
• 布隆过滤器不存储值自己，实用于一些数据敏感场景
  

3.2 缺点

• 布隆过滤器天然存在误判的标题
  
• 布隆过滤器无法获取值自己
  
• 一样寻常情况下布隆过滤器难以实现删除操纵
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。