当前位置： 首页 > article >正文

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

article 2025/1/22 23:17:42

1. 概念

1.1 背景引入

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

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

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

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 MyBloomFilter
	bloomFilter.bitMap = *mybitmap.InitBitMap()
	bloomFilter.seeds = [3]int{11, 22, 33}
	bloomFilter.usedSize = 0
	for i := 0; i < 3; i++ {
		bloomFilter.hashArray[i] = *hash.InitHashFunc(100, bloomFilter.seeds[i])
	}
	return &bloomFilter
}

hash.go：

package hash

import "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 MyBitMap
	bitMap.elem = make([]byte, 10)
	bitMap.usedSize = 0
	return &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. 存储元素个数+1
	bitMap.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 << bitIndex
		bitMap.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)
		// 判断值是否为0
		if !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，但是依旧存在以下缺点：

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

2.5 完整代码

package main

import (
	"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 MyBloomFilter
	bloomFilter.bitMap = *mybitmap.InitBitMap()
	bloomFilter.seeds = [3]int{11, 22, 33}
	bloomFilter.usedSize = 0
	for 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)
		// 判断值是否为0
		if !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"))
}

程序运行结果：

3. 布隆过滤器小结

3.1 优点

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

3.2 缺点

  • 布隆过滤器天然存在误判的问题
  • 布隆过滤器无法获取值本身
  • 一般情况下布隆过滤器难以实现删除操作

http://www.kler.cn/a/514116.html

相关文章：

  • 2. CSS 中的单位
  • mybatis（19/134）
  • 记一次常规的网络安全渗透测试
  • Dockerfile另一种使用普通用户启动的方式
  • 脚本工具：PYTHON
  • Jenkins 启动
  • 智能集群无人机组网技术关键要素详解
  • Spring boot面试题----SpringBoot性能如何优化
  • 如何利用边缘节点服务打造极致用户体验？
  • ‘openssl‘ 不是内部或外部命令，也不是可运行的程序或批处理文件
  • openssl 正确生成v3带SAN的证书
  • 前端【6】JavaScript基本语法
  • Kubernetes 集群中安装和配置 Kubernetes Dashboard
  • 数据结构详解——堆与二叉树
  • GDB相比IDE有什么优点
  • VSCode最新离线插件拓展下载方式
  • 八股学习 框架篇（spring mybatis）
  • 浅谈Java之AJAX
  • #HarmonyOS篇：build-profile.json5里面配置productsoh-package.json5里面dependencies依赖引入
  • 【网络协议】【http】【https】TLS1.3
  • PIM原理与配置
  • Redis 集群模式入门
  • 66，【6】buuctf web [HarekazeCTF2019]Avatar Uploader 1
  • 一文大白话讲清楚webpack基本使用——9——预加载之prefetch和preload以及webpackChunkName的使用
  • 2025年01月21日Github流行趋势
  • 简识JVM栈帧中的局部变量表