C++进阶篇5---番外-位图和布隆过滤器

哈希的应用

一、位图

情景:给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中???

看到查找元素的范围,暴力肯定是过不了的,我们要么二分要么哈希,但是二分要求排序,题目说没排过序,只剩下哈希,但是如果用正常的哈希表肯定不行,数据量太大了(可以算一下,大概15G),根本加载不进内存,更别谈放到哈希表中了,那怎么办? 

这时候就需要用到位图---本质就是状态压缩版的哈希表,用一个比特位表示一个数字,大大压缩了数据量,(整形是4字节,如果是哈希表只能用来表示一个数字,但是位图可以用来表示4*8=32个数),数据量缩小了32倍,大概0.5G,具体的实现如下

namespace zxws
{
	template <size_t N=100>
	class bitset
	{
	public:
		bitset()
		{
			bit.resize(N/32+1);
		}

		void set(size_t x)//增
		{
			size_t i = x / 32;
			size_t j = x % 32;
			bit[i] |= (1u << j);//1u代表unsigned int类型的1
		}

		void reset(size_t x)//删
		{
			size_t i = x / 32;
			size_t j = x % 32;
			bit[i] &= ~(1u << j);
		}

		bool test(size_t x)//查
		{
			size_t i = x / 32;
			size_t j = x % 32;
			return (bit[i] >> j) & 1u;
		}
	private:
		vector<int>bit;
	};
}

模拟实现没啥难度,就是要了解位运算,当然这只是位图的最重要的几个函数,还有一些其他的不常用的就不模拟实现了,有兴趣大家可以去查看文档

那么了解了位图的实现原理,我们再来看看下面的几个题

1. 给定100亿个整数,设计算法找到只出现一次的整数?
2. 给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集?
3. 位图应用变形:1个文件有100亿个int,1G内存,设计算法找到出现次数不超过2次的所有整数
题1:正常用一个位图,不好做,因为一个数字对应一个比特位,而一个比特位只有0 / 1两个状态,无法表示没出现,出现1次和出现多次这3个状态,那怎么办?既然一个比特位无法表示,那两个比特位呢?共有00,01,10,11四个状态,绰绰有余,实现如下
namespace zxws
{
	template <size_t N = 100>
	class twobitset
	{
	public:
		void set(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;
			if (bs1.test(x) == false && bs2.test(x) == false)//00->01
			{
				bs1.set(x);
			}
			else if (bs1.test(x) == true && bs2.test(x) == false)//01->10
			{
				bs1.reset(x);
				bs2.set(x);
			}
		}
        void test(size_t x)
		{
			return bs1.test(x) == true && bs2.test(x) == false;//01--代表只出现一次
		}
	private:
		bitset<N>bs1;
		bitset<N>bs2;
	};
}

题2:找文件交集,这个就很明显了,两个位图分别存放两个文件中的数字,然后比特位之间&一下,比特位上为1的就是交集

题3:这题其实和第1题一样,都是查看数字出现次数,要求不出现两次,即有没出现,出现1次,出现2次和出现2次以上四个状态,两个位图正好够了,实现同题1

二、布隆过滤器

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

实现原理图

一般来说用三个哈希函数就差不多了

上图是网上的研究数据显示结果,仅供参考(k,m,n满足上诉关系时,不容易发生哈希冲突)

布隆过滤器的作用范围还是很广泛的,尤其是在不怎么关心某一个东西是否真的存在的场景下,举个例子,比如说取用户ID,当你取的id没人用时,OK你创建成功,当你取的id显示有人用时,如果是真的有人用了,那我们就换一个,如果没人用,它误判了,那我们也就是不能用这个id而已,没有啥太大影响,这时布隆过滤器就非常合适

当然如果说用户投诉说明明没人用这个id,却不让用,要求我们修复bug,这时我们只要让在布隆过滤器过滤后显示为存在的数据再去数据库中校验一下即可,

当然也有人会觉得反正都要去数据库校验还要布隆过滤器干嘛,注意:1.布隆过滤器它为啥叫过滤器,关键就是它只能确定不存在的数据,不能确定存在的数据。2.网络上通讯会比较耗时,如果每一个id的确认都需要与服务器上的数据库校验,就会浪费时间

实现如下

//哈希函数就自行去网上找哪些不容易产生哈希冲突的就行
template <size_t N, 
	class K=string, 
	class HashFunc1=HashFun<K>, 
	class HashFunc2=DGBHash<K>, 
	class HashFunc3=APHash<K> >
class BloomFiler {
public:
	void set(const K& key)
	{
		size_t hash1 = HashFunc1()(key) % N;
		size_t hash2 = HashFunc2()(key) % N;
		size_t hash3 = HashFunc3()(key) % N;

		_bs.set(hash1);
		_bs.set(hash2);
		_bs.set(hash3);
	}

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

		return true;
	}
private:
	bitset<N*5>_bs;
};

两个问题:

1. 给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?分别给出精确算法和近似算法(具体下面一个专题讲)

2. 如何扩展BloomFilter使得它支持删除元素的操作?一般来说是不能支持的,因为删除一个元素的映射会影响其他元素的哈希映射(因为它们会出现冲突),但是我们可以给它们加一个引用计数,这样就能在删除它的同时不影响其他元素的映射

优点
1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数,一般比较小),与数据量大小无关
2. 哈希函数相互之间没有关系,方便硬件并行运算
3. 布隆过滤器不需要存储元素本身,在某些对保密要求比较严格的场合有很大优势
4. 在能够承受一定的误判时,布隆过滤器比其他数据结构有这很大的空间优势
5. 数据量很大时,布隆过滤器可以表示全集,其他数据结构不能
6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

三、哈希分割---哈希思想的扩展

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址?如何找到top K的IP?

100G的file很显然太大,我们的想法是将它分割成一个个小文件,然后在小文件中计数,我们将文件按Hash(id) % 100,得到100个1G的小文件(理想情况),然后我们就可以在小文件中统计每个id出现的次数(因为同一个id经过哈希映射会在同一个小文件中),但是,上面的只是理想情况,如果某一个小文件的大小为10G,也就是分完之后还是太大了,我们又该怎么办?

出现上诉情况共分两种可能:

1.相同的id太多
2.哈希冲突太多,导致多个不同的id都放在了同一个小文件中

如果是情况一,我们不用管,map中只会插入一次这个id,空间足够

如果是情况二,会报内存错误,这时我们就对这个小文件进行二次哈希分割即可

top K问题用堆实现就行,之前再二叉树数据结构中讲过的


下面,我们回过头去看看

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

近似算法就是用布隆过滤器,但是精确的算法呢?

这个query的大小也要考虑到,假设query的大小为50字节,那么一共5000亿字节,约等于500G,很明显了哈希切割,当然我们得先将query转成整数,Hash(query)%500,两个文件各自分成500个1G的小文件(理想情况),这样两个文件中相同的query会分别放在同一个余数的两个小文件中,如下图

当然它也会出现小文件太大的情况,处理方法同上,注意这个不能用位图的原因是query里面存的不一定是整数,这样不同的query查询也有可能映射到用一个比特位(这也是布隆过滤器不准确的原因之一),就不精确了


如果上诉内容对你理解哈希有帮助的话,不要忘记点赞+评论哟!!!

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

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

相关文章

什么游戏搬砖挣钱,还不费时间?

游戏搬砖的项目挺多的&#xff0c;但是不费时间&#xff1f;估计就Steam搬砖或叫CSGO搬砖。 正常的游戏搬砖的项目&#xff0c;想要挣钱&#xff0c;没有不费时间的。因为游戏搬砖是需要耗费大量的时间去玩游戏&#xff0c;熟悉游戏&#xff0c;利用自己的时间和技巧手段在游戏…

TDA4VM MCUSW

文章目录 1. 原文概述2. 如何配置MCUSW?2.1 向TI申请EB安装包2.2 安装EB配置工具3. MCAL支持的外设注意:本篇主要参考的文档在这里哈:ti-processor-sdk-rtos-j721e-evm-09_00_01_01/mcusw/mcal_drv/docs/drv_docs/mcusw_c_ug_top.html 1. 原文概述 J721E/J7200/J721S2/J78…

高中生分科考试--座位编排系统

这个系统是帮我一同学的哥哥的做的座位编排系统&#xff0c;他是某个学校的教育从事者 基本需求&#xff1a;就是能够根据他提供的各个分科班级同学的成绩单来选择相同分科的考场编排&#xff08;按成绩高低&#xff09;&#xff0c;同时输入相应的考场数&#xff0c;和每个考…

MPPT工作流程及算法和硬件的选择

MPPT算法选择 目前&#xff0c;MPPT算法有开路电压比率(离线)、短路电流比率(离线)、观察调节(在线)、极限追踪控制法(在线)。 在光伏控制系统中&#xff0c;因为日照、温度等条件的变化&#xff0c;光伏电池的输出功率也是在不断变化的&#xff0c;为保证使得光伏电池的输出功…

Python基础语法之学习运算符

Python基础语法之学习运算符 一、代码二、效果 一、代码 print("1 1 ", 1 1) print("1 - 1 ", 1 - 1) print("1 * 1 ", 1 * 1) print("11 / 5 ", 11 / 5) print("11 // 5 ", 11 // 5) print("9 % 5 ", 9…

【单调栈】最大二叉树

题目&#xff1a; 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建: 创建一个根节点&#xff0c;其值为 nums 中的最大值。递归地在最大值 左边 的 子数组前缀上 构建左子树。递归地在最大值 右边 的 子数组后缀上 构建右子树。 返回 nums…

linux用户身份切换su和 sudo

su 切换root&#xff0c;但是&#xff0c;环境变量是之前用户的 可以看到利用su切换&#xff0c;根目录还是pro1的 su - 连同环境一起切换成root&#xff0c;切换后工作目录都不一样了&#xff0c;看输入内容左侧信息&#xff0c;和第一个图片比较 -c仅执行一次命令&#xff0…

INFINI Gateway 与华为鲲鹏完成产品兼容互认证

何为华为鲲鹏认证 华为鲲鹏认证是华为云围绕鲲鹏云服务&#xff08;含公有云、私有云、混合云、桌面云&#xff09;推出的一项合作伙伴计划&#xff0c;旨在为构建持续发展、合作共赢的鲲鹏生态圈&#xff0c;通过整合华为的技术、品牌资源&#xff0c;与合作伙伴共享商机和利…

脚本绑邦引流脚本拓客软件短视频获客直播间截流抖音快手小红书自动引流关注点赞私信评论截流涨粉

一、引流脚本是什么&#xff1f; 引流脚本是一种自动化的工具&#xff0c;可以帮助你在各​种短视频、​社交媒体平台上进行批量关注、点赞、私信、评论等操作&#xff0c;从而吸引更多的流量和粉丝。通过引流脚本&#xff0c;你可以自动化地执行各种操作&#xff0c;解放双手…

kafka如何保证消息不丢失 不重复消费 消息的顺序

如何保证消息的不丢失 消息为什么会丢失 想要保证消息不丢失就要首先知道消息为什么会丢失,在哪个环节会丢失,然后在丢失的环节做处理 1.生产者生产消息发送到broker,broker收到消息后会给生产者发送一个ack指令.生产者接收到broker发送成功的指令,这个时候我们就可以认为消息…

RPG项目01_UI登录

首先创建一个项目 将资源包导进Resources文件夹 创建一个Scripts脚本文件夹 然后再对Scripts脚本文件夹分门别类 导入UI资源包 创建一个Image 按住Alt 选择右下角 image就会覆盖整个面板 修改image名字为BG 将image图片放置背景栏 再创建一个image 改名为MainMenu 修改MainMenu…

Spring Boot 3.2.0 Tomcat虚拟线程初体验 (部分装配解析)

写在前面 spring boot 3 已经提供了对虚拟线程的支持。 虚拟线程和平台线程主要区别在于&#xff0c;虚拟线程在运行周期内不依赖操作系统线程&#xff1a;它们与硬件脱钩&#xff0c;因此被称为 “虚拟”。这种解耦是由 JVM 提供的抽象层赋予的。 虚拟线程的运行成本远低于平…

zblog插件-zblog采集插件下载

在当今数字化的时代&#xff0c;博客已经成为人们分享思想、经验和知识的重要平台。而对于使用zblog博客系统的用户来说&#xff0c;充实博客内容是提高用户体验和吸引读者的不二法门。然而&#xff0c;手动收集内容对于博主来说既费时又繁琐。在这个背景下&#xff0c;zblog插…

什么是数据填报?

数据填报是报表用以满足用户提出的灵活报送数据的需求&#xff0c;能快速开发各类数据采集系统的专业功能。多源填报模型&#xff0c;可实现数据的多源抽取与多源回填&#xff0c;在同一张填报表上实现数据提交至多个不同的数据表、数据库。 随着业务快速变化和扩大&#xff0c…

python基础练习题库实验5

文章目录 题目1代码实验结果题目2代码实验结果题目3代码实验结果![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/6058fb4b66994aed838f920f7fe75706.png)题目4代码实验结果题目总结题目1 编写一个程序,使用while循环语句和字符串格式显示以下精确输出。 例如: …

【Spring集成MyBatis】MyBatis的多表查询

文章目录 1. 一对一什么是一对一User、Order类及Mapper&#xff0c;User、Order表一对一操作的实现一对一操作实现的第二种方式 2. 一对多什么是一对多一对多操作实现 3. 多对多什么是多对多多对多的实现 4. 小结 1. 一对一 什么是一对一 一对一指的是表与表之间通过外键进行…

使用C语言库函数qsort排序注意点

目录 题目背景错误C语言代码&#xff1a;正确C语言代码&#xff1a;注意点 题目背景 高校团委组织校园歌手比赛&#xff0c;进入决赛的校园歌手有10位,歌手编号从1到10进行编号。组委会随机抽取方式产生了决赛次序为&#xff1a;3,1,9,10,2,7,5,8,4,6。比赛现场有5个评委为参赛…

4、stable diffusion

github 安装anaconda环境 conda env create -f environment.yaml conda activate ldm安装依赖 conda install pytorch1.12.1 torchvision0.13.1 torchaudio0.12.1 cudatoolkit11.3 -c pytorch pip install transformers4.19.2 diffusers invisible-watermark pip install -e…

6、信息收集(1)

文章目录 一、DNS信息查询1、利用dig工具查询各类DNS的解析。2、使用DNS子域名爆破工具&#xff0c;针对子域名进行爆破&#xff0c;同时解析出对应的IP地址。3、利用多地Ping工具&#xff0c;查看域名真实IP。4、针对部分IP进行信息收集 二、DNS域传输实验原理方法一方法二 三…

C语言——数组转换

将的两行三列数组转换为三行两列的数组 #define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h> int main() {int a[2][3]{{1,2,3},{4,5,6}};int b[3][2],i,j;for ( i 0; i <1; i){for ( j 0; j <2; j){printf("%5d",a[i][j]);b[j][i]a[i][j];}printf(&…