广告
返回顶部
首页 > 资讯 > 后端开发 > 其他教程 >C++BloomFilter布隆过滤器应用及概念详解
  • 251
分享到

C++BloomFilter布隆过滤器应用及概念详解

C++BloomFilter布隆过滤器C++BloomFilterC++布隆过滤器 2023-03-08 11:03:36 251人浏览 八月长安
摘要

目录一、布隆过滤器概念二、布隆过滤器应用三、布隆过滤器实现1.插入2.查找3.删除四、布隆过滤器优缺五、结语一、布隆过滤器概念 布隆过滤器是由布隆(Burton Howard Blo

一、布隆过滤器概念

布隆过滤器是由布隆(Burton Howard Bloom)在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构,特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”,它是用多个哈希函数,将一个数据映射到位图结构中。此种方式不仅可以提升查询效率,也可以节省大量的内存空间 .

位图的优点是节省空间,快,缺点是要求范围相对集中,如果范围分散,空间消耗上升,同时只能针对整型,字符串通过哈希转化成整型,再去映射,对于整型没有冲突,因为整型是有限的,映射唯一的位置,但是对于字符串来说,是无限的,会发生冲突,会发生误判:此时的情况的是不在是正确的,在是不正确的,因为可能不来是不在的,但是位置跟别人发生冲突,发生误判

此时布隆过滤器就登场了,可以降低误判率:让一个值映射多个位置,但是并不是消除误判

可能还是会出现误判:

虽然布隆过滤器还是会出现误判,因为这个数据的比特位被其他数据所占,但是判断一个数据不存在是准确,不存在就是0!

布隆过滤器改进:映射多个位置,降低误判率(位置越多,消耗也越多)

如果布隆过滤器长度比较小,比特位很快会被占为1,误判率自然会上升,所以布隆过滤器的长度会影响误判率,理论上来说,如果一个值映射的位置越多,则误判的概率越小,但是并不是位置越多越好,空间也会消耗:大佬们自然也能够想得到,所以有公式:

我们可以来估算一下,假设用 3 个哈希函数,即K=3,ln2 的值我们取 0.7,那么 m 和 n 的关系大概是 m = n×k/ln2=4.2n ,也就是过滤器长度应该是插入元素个数的 4 -5倍

二、布隆过滤器应用

不需要一定准确的场景。比如游戏注册时候的昵称的判重:如果不在那就是不在,没被使用,在的话可能会被误判。

提高查找效率:客户端中查找一个用户的ID与服务器中的是否相同,在增加一层布隆过滤器提高查找效率:

三、布隆过滤器实现

布隆过滤器的插入元素可能是字符串,也可能是其他类型,只要提供对应的哈希函数将该类型的数据转换成整型就可以了。

一般情况下布隆过滤器都是用来处理字符串的,所以布隆过滤器可以实现为一个模板类,将模板参数 T 的缺省类型设置为 string:

template <size_t N,size_t X = 5,class K=string,
		class HashFunc1 = BKDRHash,
		class HashFunc2 = APHash,
		class HashFunc3 = DJBHash>
class BloomFilter
	{
    public:
    private:
		bitset<N * X> _bs;
	};

这里布隆过滤器提供三个哈希函数,由于布隆过滤器一般处理的是字符串类型的数据,所以我们默认提供几个将字符串转换成整型的哈希函数:选取综合评分最高的 BKDRHash、APHash 和 DJBHash这三种哈希算法

   struct BKDRHash
	{
		size_t operator()(const string& key)
		{
			size_t hash = 0;
			for (auto ch : key)
			{
				hash *= 131;
				hash += ch;
			}
			return hash;
		}
	};
	struct APHash
	{
		size_t operator()(const string& key)
		{
			size_t hash = 0;
			int i = 0;
			for (auto ch : key)
			{
				if ((i & 1) == 0)
				{
					hash ^= ((hash << 7) ^ (ch) ^ (hash >> 3));
				}
				else
				{
					hash ^= (~((hash << 11) ^ (ch) ^ (hash >> 5)));
				}
				++i;
			}
			return hash;
		}
	};
	struct DJBHash
	{
		size_t operator()(const string& key)
		{
			size_t hash = 5318;
			for (auto ch : key)
			{
				hash += (hash << 5) + ch;
			}
			return hash;
		}
	};

1.插入

布隆过滤器复用bitset的 set 接口用于插入元素,插入元素时,我们通过上面的三个哈希函数分别计算出该元素对应的三个比特位,然后在位图中设置为1即可:

        void set(const K& key)
		{
			size_t hash1 = HashFunc1()(key) % (N * X);
			size_t hash2 = HashFunc2()(key) % (N * X);
			size_t hash3 = HashFunc3()(key) % (N * X);
			_bs.set(hash1);
			_bs.set(hash2);
			_bs.set(hash3);
			_bs.set(hash4);
		}

2.查找

通过三个哈希函数分别算出对应元素的三个哈希地址,得到对应的比特位,然后去判断这三个比特位是否都被设置成了1

如果出现一个比特位未被设置成1说明该元素一定不存在,也就是如果一个比特位为0就是false;而如果三个比特位全部都被设置,则return true表示该元素已经存在(注:可能会出现误判)

        bool test(const K& key)
		{
			size_t hash1 = HashFunc1()(key) % (N * X);
			if (!_bs.test(hash1))
			{
				return false;
			}
			size_t hash2 = HashFunc2()(key) % (N * X);
			if (!_bs.test(hash2))
			{
				return false;
			}
			size_t hash3 = HashFunc3()(key) % (N * X);
			if (!_bs.test(hash3))
			{
				return false;
			}
			return true;
		}

3.删除

布隆过滤器一般没有删除,因为布隆过滤器判断一个元素是会存在误判,此时无法保证要删除的元素在布隆过滤器中,如果此时将位图中对应的比特位清0,就会影响到其他元素了:

这时候我们只需要在每个比特位加一个计数器,当存在插入操作时,在计数器里面进行 ++,删除后对该位置进行 -- 即可

但是布隆过滤器的本来目的就是为了提高效率和节省空间,在每个比特位增加额外的计数器,空间消耗那就更多了

四、布隆过滤器优缺

\1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数,一般比较小),与数据量大小无关

\2. 哈希函数相互之间没有关系,方便硬件并行运算

\3. 布隆过滤器不需要存储元素本身,在某些对保密要求比较严格的场合有很大优势

\4. 在能够承受一定的误判时,布隆过滤器比其他数据结构有这很大的空间优势

\5. 数据量很大时,布隆过滤器可以表示全集,其他数据结构不能

\6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

\1. 有误判率,不能准确判断元素是否在集合中(补救方法:再建立一个白名单,存储可能会误判的数据)

\2. 不能获取元素本身

\3. 一般情况下不能从布隆过滤器中删除元素

五、结语

给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?分别给出精确算法和近似算法?

近似算法:利用布隆过滤器,交集的就一定会进去,但是可能会存在误判:不同的也会进去,这是近似

精准算法:query一般是查询指令,比如可能是网络请求,或者是一个数据库sql语句

100亿个query,假设平均每个query是50byte,则100亿个query那就是合计500GB

相同的query,是一定进入相同编号的小文件,再对这些文件放进内存的两个set中,编号相同的ai和Bi小文件找交集即可

到此这篇关于c++ BloomFilter布隆过滤器应用及概念详解的文章就介绍到这了,更多相关C++ BloomFilter内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

--结束END--

本文标题: C++BloomFilter布隆过滤器应用及概念详解

本文链接: https://www.lsjlt.com/news/199004.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑,方便收藏和打印~

下载Word文档
猜你喜欢
  • C++BloomFilter布隆过滤器应用及概念详解
    目录一、布隆过滤器概念二、布隆过滤器应用三、布隆过滤器实现1.插入2.查找3.删除四、布隆过滤器优缺五、结语一、布隆过滤器概念 布隆过滤器是由布隆(Burton Howard Blo...
    99+
    2023-03-08
    C++ BloomFilter布隆过滤器 C++ BloomFilter C++布隆过滤器
  • C++ BloomFilter布隆过滤器如何应用
    这篇“C++ BloomFilter布隆过滤器如何应用”文章的知识点大部分人都不太理解,所以小编给大家总结了以下内容,内容详细,步骤清晰,具有一定的借鉴价值,希望大家阅读完这篇文章能有所收获,下面我们一起来看看这篇“C++&nbs...
    99+
    2023-07-05
  • victoriaMetrics库布隆过滤器初始化及使用详解
    目录概述限速器的初始化总结代码路径:/lib/bloomfilter 概述 victoriaMetrics的vmstorage组件会接收上游传递过来的指标,在现实场景中,指标或瞬时指...
    99+
    2022-11-13
  • C++哈希应用的位图和布隆过滤器
    目录C++哈希应用的位图和布隆过滤器 一、位图1.位图的概念2.位图的面试题3.位图的实现4.位图的应用二、布隆过滤器1.布隆过滤器的提出2.布隆过滤器的概念3.布隆过滤器的插入4....
    99+
    2022-11-12
  • C++哈希应用之位图,哈希切分与布隆过滤器详解
    目录一、位图1、位图的概念2、大厂面试题3、位图的优缺点二、哈希切分三、布隆过滤器1、布隆过滤器的概念2、布隆过滤器的应用场景3、布隆过滤器的删除4、布隆过滤器的优缺点5、布隆过滤器...
    99+
    2023-05-14
    C++位图 C++哈希切分 C++布隆过滤器 C++哈希
  • Redis 布隆过滤器命令的使用详解
    目录一、Docker 安装 Redis 布隆过滤器学习历史重要原因之一,就是要学会感恩,因为我们都是站在巨人的肩膀上。1.1、安装注意:1.2、测试二、RedisBloom 命令讲解...
    99+
    2022-11-13
  • Redis 布隆过滤器命令的使用详解
    目录一、docker 安装 Redis 布隆过滤器学习历史重要原因之一,就是要学会感恩,因为我们都是站在巨人的肩膀上。1.1、安装注意:1.2、测试二、RedisBloom 命令讲解2.1、命令大纲2.2、BF.ADD ...
    99+
    2022-08-26
  • 详解SpringBoot中如何使用布隆过滤器
    目录前言一、Guava 实现布隆过滤器二、Hutool 布隆过滤器三、Redission 布隆过滤器四、小结五、Guava 布隆过滤器结合 Redis 使用昨天写了一篇Redis布隆...
    99+
    2022-11-13
  • C++位图,哈希切分与布隆过滤器怎么应用
    本篇内容主要讲解“C++位图,哈希切分与布隆过滤器怎么应用”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“C++位图,哈希切分与布隆过滤器怎么应用”吧!一、位图1、位图的概念所谓位图,就是用每一位...
    99+
    2023-07-05
  • C++详细讲解模拟实现位图和布隆过滤器的方法
    目录位图引论概念解决引论位图的模拟实现铺垫结构构造函数存储set,reset,testflip,size,countany,none,all重载流运算符测试位图简单应用位图代码汇总布...
    99+
    2022-11-13
  • Vue过滤器(filter)实现及应用场景详解
    1. 简单介绍 Vue.js 允许你自定义过滤器(filter),可被用于一些常见的文本格式化。 过滤器可以用在两个地方:双花括号插值和 v-bind 表达式 (后者从 2.1.0...
    99+
    2022-11-12
软考高级职称资格查询
编程网,编程工程师的家园,是目前国内优秀的开源技术社区之一,形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容,为IT开发者提供了一个发现、使用、并交流开源技术的平台。
  • 官方手机版

  • 微信公众号

  • 商务合作