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

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 缺点

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/957501.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Linux内存管理(Linux内存架构，malloc，slab的实现)

Linux内存管理(Linux内存架构，malloc，slab的实现)

文章目录 前言一、Linux进程空间内存分配二、malloc的实现机理三、物理内存与虚拟内存1.物理内存2.虚拟内存 四、磁盘和物理内存区别五、页页的基本概念&#xff1a;分页管理的核心概念&#xff1a;Linux 中分页的实现&#xff1a;总结&#xff1a; 六、伙伴算法伙伴算法的核心…
阅读更多...
2025/1/21 学习Vue的第四天

2025/1/21 学习Vue的第四天

睡觉。 --------------------------------------------------------------------------------------------------------------------------------- 11.Object.defineProperty 1.在我们之前学习JS的时候&#xff0c;普通得定义一个对象与属性。 <!DOCTYPE html> <h…
阅读更多...
机器学习10-解读CNN代码Pytorch版

机器学习10-解读CNN代码Pytorch版

机器学习10-解读CNN代码Pytorch版 我个人是Java程序员&#xff0c;关于Python代码的使用过程中的相关代码事项&#xff0c;在此进行记录 文章目录 机器学习10-解读CNN代码Pytorch版1-核心逻辑脉络2-参考网址3-解读CNN代码Pytorch版本1-MNIST数据集读取2-CNN网络的定义1-无注释版…
阅读更多...
python学opencv|读取图像（四十）掩模：三通道图像的局部覆盖

python学opencv|读取图像（四十）掩模：三通道图像的局部覆盖

【1】引言 前序学习了使用numpy创建单通道的灰色图像&#xff0c;并对灰色图像的局部进行了颜色更改&#xff0c;相关链接为&#xff1a; python学opencv|读取图像&#xff08;九&#xff09;用numpy创建黑白相间灰度图_numpy生成全黑图片-CSDN博客 之后又学习了使用numpy创…
阅读更多...
【MySQL篇】使用mysqldump导入报错Unknown collation: ‘utf8mb4_0900_ai_ci‘的问题解决

【MySQL篇】使用mysqldump导入报错Unknown collation: ‘utf8mb4_0900_ai_ci‘的问题解决

&#x1f4ab;《博主介绍》&#xff1a;✨又是一天没白过&#xff0c;我是奈斯&#xff0c;从事IT领域✨ &#x1f4ab;《擅长领域》&#xff1a;✌️擅长阿里云AnalyticDB for MySQL(分布式数据仓库)、Oracle、MySQL、Linux、prometheus监控&#xff1b;并对SQLserver、NoSQL(…
阅读更多...
WPF2-在xaml为对象的属性赋值

WPF2-在xaml为对象的属性赋值

1. AttributeValue方式 1.1. 简单属性赋值1.2. 对象属性赋值 2. 属性标签的方式给属性赋值3. 标签扩展 (Markup Extensions) 3.1. StaticResource3.2. Binding 3.2.1. 普通 Binding3.2.2. ElementName Binding3.2.3. RelativeSource Binding3.2.4. StaticResource Binding (带参…
阅读更多...
软考 系统架构设计师系列知识点之面向服务架构设计理论与实践（5）

软考 系统架构设计师系列知识点之面向服务架构设计理论与实践（5）

接前一篇文章&#xff1a;软考 系统架构设计师系列知识点之面向服务架构设计理论与实践&#xff08;4&#xff09; 所属章节&#xff1a; 第15章. 面向服务架构设计理论与实践 第2节 SOA的发展历史 15.2 SOA的发展历史 15.2.3 SOA的微服务化发展 随着互联网技术的快速发展&a…
阅读更多...
ICLR顶会论文学习|DRL-based改进启发式求解方法JSSP

ICLR顶会论文学习|DRL-based改进启发式求解方法JSSP

论文名&#xff1a;Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop Scheduling Authors: Cong Zhang, Zhiguang Cao, Wen Song, Yaoxin Wu, Jie Zh… 论文发表致&#xff1a;ICLR 2024 论文链接&#xff1a;https://doi.org/10.48550/arXiv.2211.1…
阅读更多...
OpenCV简介、OpenCV安装

OpenCV简介、OpenCV安装

OpenCV简介、OpenCV安装 本文目录&#xff1a; 零、时光宝盒 一、OpenCV简介 二、OpenCV图像处理基础知识 三、OpenCV-Python环境安装 2.1、纯python环境下安装OpenCV 2.2、Anaconda管理环境下安装 OpenCV 四、如何用OpenCV 中进行读取展示图像 五、OpenCV读取图像、显…
阅读更多...
利用预训练检查点进行序列生成任务

利用预训练检查点进行序列生成任务

摘要 大型神经模型的无监督预训练最近彻底改变了自然语言处理。通过从公开发布的检查点进行热启动&#xff0c;自然语言处理从业者在多个基准测试中推动了最先进的技术&#xff0c;同时节省了大量的计算时间。到目前为止&#xff0c;重点主要集中在自然语言理解任务上。在本文…
阅读更多...
5、原来可以这样理解C语言_数组(5)sizeof 计算数组元素个数

5、原来可以这样理解C语言_数组(5)sizeof 计算数组元素个数

目录 5. sizeof 计算数组元素个数 5. sizeof 计算数组元素个数 在遍历数组的时候&#xff0c;我们经常想知道数组的元素个数&#xff0c;那C语⾔中有办法使⽤程序计算数组元素个数 吗&#xff1f; 答案是有的&#xff0c;可以使⽤sizeof。 sizeof 中C语⾔是⼀个关键字&#xff…
阅读更多...
vue中echarts-中国地图，世界地图显示（echarts5.6版本本地导入)

vue中echarts-中国地图，世界地图显示（echarts5.6版本本地导入)

地图去掉南海诸岛右下角的框显示&#xff08;因为显示的不是现在的10段线&#xff09; 资源里面主要是有个改好的中国地图json其他的无所谓&#xff0c;用现有的json也行&#xff0c;主要是为了解决10段线的问题 引入需要注意 import * as echarts from “./echarts”; 目录…
阅读更多...
Ubuntu系统更改IP，保姆级教程

Ubuntu系统更改IP，保姆级教程

原理概述 本篇文章所用工具&#xff1a; Xshell&#xff1a;点击下载 VMware Workstation Pro&#xff1a;点击下载 密钥需要自行搜索所下载的VMware对应版本密钥。 IP 地址 IP 地址&#xff08;Internet Protocol Address&#xff09;是分配给每个连接到计算机网络的设备的…
阅读更多...
IO进程----进程

IO进程----进程

进程 什么是进程 进程和程序的区别 概念&#xff1a; 程序&#xff1a;编译好的可执行文件 存放在磁盘上的指令和数据的有序集合&#xff08;文件&#xff09; 程序是静态的&#xff0c;没有任何执行的概念 进程&#xff1a;一个独立的可调度的任务 执行一个程序分配资…
阅读更多...
使用插件SlideVerify实现滑块验证

使用插件SlideVerify实现滑块验证

作者gitee地址&#xff1a;https://gitee.com/monoplasty/vue-monoplasty-slide-verify 使用步骤&#xff1a; 1、安装插件 npm install --save vue-monoplasty-slide-verify 2、在main.js中进行配置 import SlideVerify from vue-monoplasty-slide-verify; Vue.use(SlideV…
阅读更多...
初探——【Linux】程序的翻译与动静态链接

初探——【Linux】程序的翻译与动静态链接

我们所写的C/C程序计算机是看不懂的&#xff0c;它只认识0101这样的机器码。所以我们就需要借助编译器对这些源代码进行翻译&#xff0c;使之成为计算机能够执行的二进制指令。这个过程通常分为几个关键步骤&#xff1a;预处理、编译、汇编和链接。 一.预处理&#xff08;Prep…
阅读更多...
亲测有效！如何快速实现 PostgreSQL 数据迁移到 时序数据库TDengine

亲测有效！如何快速实现 PostgreSQL 数据迁移到 时序数据库TDengine

小T导读&#xff1a;本篇文章是“2024&#xff0c;我想和 TDengine 谈谈”征文活动的优秀投稿之一&#xff0c;作者从数据库运维的角度出发&#xff0c;分享了利用 TDengine Cloud 提供的迁移工具&#xff0c;从 PostgreSQL 数据库到 TDengine 进行数据迁移的完整实践过程。文章…
阅读更多...
matlab实现数据极坐标显示

matlab实现数据极坐标显示

%% % 读取文件数据 filename E:\ProjectWorkspace\866\866data\665hangji.txt;%代码 距离 方位相对正北 时间 地址 横滚角度 TRK importdata(filename); filename1 E:\ProjectWorkspace\866\866data\665dianji.txt;%代码 距离 方位相对正北 时间 地址 横滚角度 PLOT …
阅读更多...
Jenkins 启动

Jenkins 启动

废话 这一阵子感觉空虚&#xff0c;心里空捞捞的&#xff0c;总想找点事情做&#xff0c;即使这是一件微小的事情&#xff0c;空余时间除了骑车、打球&#xff0c;偶尔朋友聚会 … 还能干什么呢&#xff1f; 当独自一人时&#xff0c;究竟可以做点什么&#xff0c;填补这空虚…
阅读更多...
人工智能之深度学习_[4]-神经网络入门

人工智能之深度学习_[4]-神经网络入门

文章目录 神经网络基础1 神经网络1.1 神经网络概念1.1.1 什么是神经网络1.1.2 如何构建神经网络1.1.3 神经网络内部状态值和激活值 1.2 激活函数1.2.1 网络非线性因素理解1.2.2 常见激活函数1.2.2.1 Sigmoid 激活函数1.2.2.2 Tanh 激活函数1.2.2.3 ReLU 激活函数1.2.2.4 SoftMa…
阅读更多...
最新文章

Copyright @ 2022~2023