您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

布隆过滤器:一种低空间成本的判断元素是否存在的方式

时间:2022-09-13 13:45:40  来源:今日头条  作者:java保佑我发大财

简介

布隆过滤器(BloomFilter)是一种用于判断元素是否存在的方式,它的空间成本非常小,速度也很快。

但是由于它是基于概率的,因此它存在一定的误判率,它的Contains()操作如果返回true只是表示元素可能存在集合内,返回false则表示元素一定不存在集合内。因此适合用于能够容忍一定误判元素存在集合内的场景,比如缓存。

它一秒能够进行上百万次操作(主要取决于哈希函数的速度),并且1亿数据在误判率1%的情况下,只需要114MB内存

原理

数据结构

布隆过滤器的数据结构是一个位向量,也就是一个由0、1所组成的向量(下面是一个初始向量):

 

添加

每个元素添加进布隆过滤器前,都会经过多个不同的哈希函数,计算出不同的哈希值,然后映射到位向量上,也就是对应的位上面置1:

 

判断存在

判断元素是否存在也是如上图流程,根据哈希函数映射的位置,判断所有映射位置是否都为1,如果是则元素可能存在,否则元素一定不存在。

由于不同的值通过哈希函数之后可能会映射到相同的位置,因此如果一个不存在的元素对应地位位置都被其他元素所设置位1,则查询时就会误判:

 

假设上图元素3334并没有加入集合,但是由于它映射的位置已经被其他元素所映射,则查询时会误判。

哈希函数

布隆过滤器里面的哈希函数需要是彼此独立且均匀分布(类似于哈希表的哈希函数),而且需要尽可能的快,比如murmur3就是一个很好的选择。

布隆过滤器的性能严重依赖于哈希函数的性能,而一般哈希函数的性能则依赖于输入串(一般为字节数组)的长度,因此为了提高布隆过滤器的性能建议减少输入串的长度。

下面是一个简单的性能测试,单位是字节,可以看到时间的消耗随着元素的增大基本是线性增长的:

cpu: Intel(R) Core(TM) i5-10210U CPU @ 1.60GHz
BenchmarkAddAndContains/1-8              1805840               659.6 ns/op         1.52 MB/s           0 B/op          0 allocs/op
BenchmarkAddAndContains/2-8              1824064               696.4 ns/op         2.87 MB/s           0 B/op          0 allocs/op
BenchmarkAddAndContains/4-8              1819742               649.5 ns/op         6.16 MB/s           0 B/op          0 allocs/op
BenchmarkAddAndContains/8-8              1828371               653.2 ns/op        12.25 MB/s           0 B/op          0 allocs/op
BenchmarkAddAndContains/16-8             1828426               642.0 ns/op        24.92 MB/s           0 B/op          0 allocs/op
BenchmarkAddAndContains/32-8             2106834               565.7 ns/op        56.57 MB/s           0 B/op          0 allocs/op
BenchmarkAddAndContains/64-8             2063895               579.3 ns/op       110.48 MB/s           0 B/op          0 allocs/op
BenchmarkAddAndContains/128-8            1767673               666.1 ns/op       192.17 MB/s           0 B/op          0 allocs/op
BenchmarkAddAndContains/256-8            1292918               916.9 ns/op       279.21 MB/s           0 B/op          0 allocs/op
BenchmarkAddAndContains/512-8             749666              1590 ns/op         322.11 MB/s           0 B/op          0 allocs/op
BenchmarkAddAndContains/1024-8            388015              2933 ns/op         349.12 MB/s           0 B/op          0 allocs/op
BenchmarkAddAndContains/2048-8            203404              5603 ns/op         365.51 MB/s           0 B/op          0 allocs/op
BenchmarkAddAndContains/4096-8            105134             11303 ns/op         362.38 MB/s           0 B/op          0 allocs/op
BenchmarkAddAndContains/8192-8             52305             22067 ns/op         371.23 MB/s           0 B/op          0 allocs/op
复制代码

布隆过滤器大小、哈希函数数量、误判率

布隆过滤器的大小、哈希函数数量和误判率之间是互相影响的,如果我们想减少误判率,则需要更大的布隆过滤器和更多的哈希函数。但是我们很难直观地计算出这些参数,还好有两个公式可以帮助我们计算出准确的数值:

在我们可以确定我们的元素数量和能够容忍的错误率的情况下,我们可以根据下面公式计算布隆过滤器大小和哈希函数数量:

n = 元素数量
m = 布隆过滤器大小(位数)
k = 哈希函数数量
fpr = 错误率(falsePositiveRate,假阳性率)

m = n*(-ln(fpr)/(ln2*ln2))
k = ln2 * m / n
复制代码

应用场景

数据库

布隆过滤器可以提前过滤所查询数据并不存在的请求,避免对磁盘访问的耗时。比如LevelDB就使用了布隆过滤器过滤请求github.com/google/leve… 。

黑名单

假设有10亿个黑名单URL,每个URL大小为64字节。使用Bloom Filter,如果错误率为0.1%,只需要1.4GB内存,如果错误率为0.0001%,也只需要2.9GB内存。

实现

这里简单的介绍一下Golang的实现方式。

代码:github.com/jiaxwu/gomm…

数据结构

由于我们没办法直接申请一个bit组成的数组,因此我们使用uint64表示64个bit。

type Filter struct {
	bits    []uint64     // bit数组
	bitsCnt uint64       // bit位数
	hashs   []*hash.Hash // 不同哈希函数
}
复制代码

初始化

在初始化的时候,我们需要根据上面提到的两个公式,计算布隆过滤器的大小和哈希函数的数量。

// capacity:容量
// falsePositiveRate:误判率
func New(capacity uint64, falsePositiveRate float64) *Filter {
	// bit数量
	ln2 := math.Log(2.0)
	factor := -math.Log(falsePositiveRate) / (ln2 * ln2)
	bitsCnt := mmath.Max(1, uint64(float64(capacity)*factor))

	// 哈希函数数量
	hashsCnt := mmath.Max(1, int(ln2*float64(bitsCnt)/float64(capacity)))
	hashs := make([]*hash.Hash, hashsCnt)
	for i := 0; i < hashsCnt; i++ {
		hashs[i] = hash.New()
	}

	return &Filter{
		bits:    make([]uint64, (bitsCnt+63)/64),
		bitsCnt: bitsCnt,
		hashs:   hashs,
	}
}
复制代码

添加元素

添加元素的时候,把每个哈希函数映射的位置都设置为1。这里需要注意,因为是用的uint64的数组,因此需要把按照bit计算的偏移,转换为按照64位计算的数组下标和对应下标元素里面的偏移。

// 添加元素
func (f *Filter) Add(b []byte) {
	for _, h := range f.hashs {
		index, offset := f.pos(h, b)
		f.bits[index] |= 1 << offset
	}
}

// 获取对应元素下标和偏移
func (f *Filter) pos(h *hash.Hash, b []byte) (uint64, uint64) {
	hashValue := h.Sum64(b)
	// 按照位计算的偏移
	bitsIndex := hashValue % f.bitsCnt
	// 因为一个元素64位,因此需要转换
	index := bitsIndex / uint64Bits
	// 在一个元素里面的偏移
	offset := bitsIndex % uint64Bits
	return index, offset
}
复制代码

判断元素是否存在

同理,只是这里我们如果发现某一位不为1则可以直接返回false。

// 元素是否存在
// true表示可能存在
func (f *Filter) Contains(b []byte) bool {
	for _, h := range f.hashs {
		index, offset := f.pos(h, b)
		mask := uint64(1) << offset
		// 判断这一位是否位1
		if (f.bits[index] & mask) != mask {
			return false
		}
	}
	return true
}


Tags:布隆过滤器   点击:( )  评论:( )
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:[email protected]),我们将及时更正、删除,谢谢。
▌相关推荐
简介布隆过滤器(BloomFilter)是一种用于判断元素是否存在的方式,它的空间成本非常小,速度也很快。但是由于它是基于概率的,因此它存在一定的误判率,它的Contains()操作如果返回tru...【详细内容】
2022-09-13  Tags: 布隆过滤器  点击:(0)  评论:(0)  加入收藏
布隆过滤器(BloomFilter)类似于hash set,用来判断元素是否在集合中。但是与hash set区别是:布隆过滤器不需要存储元素值,就能判断元素是否在集合中。说一下布隆过滤器优缺点: 优点...【详细内容】
2020-09-29  Tags: 布隆过滤器  点击:(188)  评论:(0)  加入收藏
作者:jack_xujuejin.im/post/5e9c110151882573793e8940不知道从什么时候开始,本来默默无闻的布隆过滤器一下子名声大燥,在面试中面试官问到怎么避免缓存穿透,你的第一反应可能就...【详细内容】
2020-05-13  Tags: 布隆过滤器  点击:(101)  评论:(0)  加入收藏
为什么引入我们的业务中经常会遇到穿库的问题,通常可以通过缓存解决。如果数据维度比较多,结果数据集合比较大时,缓存的效果就不明显了。因此为了解决穿库的问题,我们引入Bloom...【详细内容】
2020-05-05  Tags: 布隆过滤器  点击:(80)  评论:(0)  加入收藏
Redis概述:Redis是一个开源的Key-Value存储系统,其中Value支持String、list、set、hash、zset五种数据结构,这些数据都支持push/pop、add/remove、取交集并集、排序等丰富的操...【详细内容】
2020-01-17  Tags: 布隆过滤器  点击:(296)  评论:(0)  加入收藏
在项目开发中,我们经常会遇到去重问题。比如:判断一个人有没有浏览过一篇文章,判断一个人当天是否登录过某个系统,判断一个ip是否发过一个请求,等等。...【详细内容】
2019-10-08  Tags: 布隆过滤器  点击:(311)  评论:(0)  加入收藏
概述布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数,布隆过滤器可以用于检索一个元素是否在一个集合中。如果想要判...【详细内容】
2019-08-30  Tags: 布隆过滤器  点击:(364)  评论:(0)  加入收藏
URL去重应用URL去重广泛应用于网络爬虫方面,主要体现在以下两点: 实现增量爬虫时,需要判断哪些网页已经爬取了,哪些网页是新产生的,对新产生的网页,增量爬虫需要抓取其内容; 避免爬...【详细内容】
2019-08-26  Tags: 布隆过滤器  点击:(468)  评论:(0)  加入收藏
▌哈哈电竞推荐
简介布隆过滤器(BloomFilter)是一种用于判断元素是否存在的方式,它的空间成本非常小,速度也很快。但是由于它是基于概率的,因此它存在一定的误判率,它的Contains()操作如果返回tru...【详细内容】
2022-09-13  java保佑我发大财  今日头条  Tags:布隆过滤器   点击:(0)  评论:(0)  加入收藏
1、A GPU accelerated Genetic Algorithm for the Construction of Hadamard Matrices Andras Balogh, Raven Ruiz这篇论文使用遗传算法来构建Hadamard矩阵。 生成随机矩...【详细内容】
2022-09-06  deephub  今日头条  Tags:遗传算法   点击:(18)  评论:(0)  加入收藏
导读:ClickHouse已经成为行业主流且热门的开源引擎。随着业务数据量扩大,场景覆盖变广泛,在复杂query场景下,ClickHouse容易存在查询异常问题,影响业务正常推进。本次主要分享字...【详细内容】
2022-09-05  互联共商     Tags:ClickHouse   点击:(14)  评论:(0)  加入收藏
我们知道悲观锁在高并发的场景下,激烈的锁竞争会造成线程阻塞,大量阻塞线程会导致系统上下文切换,增加系统的性能开销。那么有没有可能实现一种非阻塞的锁机制来保证线程的安全...【详细内容】
2022-08-28  互联网资讯看板  网易  Tags:乐观锁   点击:(21)  评论:(0)  加入收藏
0 | 0001100 10100010 10111110 10001001 01011100 00 | 10001 | 1 1001 | 0000 00000000twitter在把存储系统从MySQL迁移到Cassandra的过程中由于Cassandra没有顺序ID生成...【详细内容】
2022-08-20  梦幻随风    Tags:snowflake   点击:(28)  评论:(0)  加入收藏
雪花算法SnowFlake 算法,是 Twitter 开源的分布式 id 生成算法。其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 id。在分布式系统中的应用十分广泛,且ID 引入...【详细内容】
2022-08-16  雪地大懒猫    Tags:雪花算法   点击:(28)  评论:(0)  加入收藏
本题来自Leetcode,题目传送门:「链接」难度:困难编程语言:Go1. 题目介绍给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。引用自Lee...【详细内容】
2022-08-15  XieYiwen    Tags:算法   点击:(19)  评论:(0)  加入收藏
前言红黑树是一种特殊的B树是B树种2-3-4树的一种特殊实现,红黑树保证了每个节点只会有两个子节点,通过对每个节点进行染色,然后通过不同颜色的节点组合来分别代表2-3-4的2节点...【详细内容】
2022-08-15  七包辣条  CSDN  Tags:红黑树   点击:(26)  评论:(0)  加入收藏
前言今天继续算法学习,本次学习的是高级排序之快速排序。本文代码部分存在调用公共方法,可在文章:简单排序算法之冒泡、插入和选择排序-Java实现版 ,高级排序之归并排序、希尔排...【详细内容】
2022-08-08  人生就是一场修行321    Tags:排序算法   点击:(30)  评论:(0)  加入收藏
随机森林是一种监督式算法,使用由众多决策树组成的一种集成学习方法,输出是对问题最佳答案的共识。随机森林可用于分类或回归。 什么是随机森林? 随机森林是用于分类和回归的一...【详细内容】
2022-08-05  NVIDIA英伟达中国    Tags:随机森林   点击:(52)  评论:(0)  加入收藏
站内最新
站内热门
站内头条