C++进阶(十)哈希的应用——位图布隆过滤器

在这里插入图片描述


📘北尘_:个人主页

🌎个人专栏:《Linux操作系统》《经典算法试题 》《C++》 《数据结构与算法》

☀️走在路上,不忘来时的初心

文章目录

  • 一、位图
    • 1、位图概念
    • 2、位图的实现
    • 3、位图的应用
  • 二、布隆过滤器
    • 1、布隆过滤器提出
    • 2、布隆过滤器概念
    • 3、布隆过滤器的插入
    • 4、布隆过滤器的查找
    • 5、布隆过滤器删除
    • 6、布隆过滤器优点
    • 7、布隆过滤器缺陷
  • 三、海量数据面试题
    • 1、 哈希切割应用
    • 2、位图应用
    • 3、布隆过滤器应用

一、位图

1、位图概念

给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在
这40亿个数中。【腾讯】

  1. 遍历,时间复杂度O(N)
  2. 排序(O(NlogN)),利用二分查找: logN
  3. 位图解决
    数据是否在给定的整形数据中,结果是在或者不在,刚好是两种状态,那么可以使用一
    个二进制比特位来代表数据是否存在的信息,如果二进制比特位为1,代表存在,为0
    代表不存在。比如:
    在这里插入图片描述

所谓位图,就是用每一位来存放某种状态,适用于海量数据,数据无重复的场景。通常是用
来判断某个数据存不存在的。

注意:由于分大小端的问题,左移,我们就可以当成,是向位数大的方向移动。

2、位图的实现

namespace zsc
{
	template<size_t N>
	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] |= (1 << j);
		}
		void reset(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;
			_bit[i] &= ~(1 << j);

		}
		bool test(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;
			return _bit[i] & (1 << j);
		}

	private:
		vector<int> _bit;
	};
}

3、位图的应用

  1. 快速查找某个数据是否在一个集合中(数据必须是整型)
  2. 排序 + 去重
  3. 求两个集合的交集、并集等
  4. 操作系统中磁盘块标记

二、布隆过滤器

1、布隆过滤器提出

我们在使用新闻客户端看新闻时,它会给我们不停地推荐新的内容,它每次推荐时要去重,去掉
那些已经看过的内容。问题来了,新闻客户端推荐系统如何实现推送去重的? 用服务器记录了用
户看过的所有历史记录,当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选,过滤掉那
些已经存在的记录。 如何快速查找呢?

  1. 用哈希表存储用户记录,缺点:浪费空间
  2. 用位图存储用户记录,缺点:位图一般只能处理整形,如果内容编号是字符串,就无法处理
    了。
  3. 将哈希与位图结合,即布隆过滤器

2、布隆过滤器概念

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

3、布隆过滤器的插入

在这里插入图片描述
代码实现:

struct BKDRHash
{
	size_t operator()(const string& key)
	{
		// BKDR
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}

		return hash;
	}
};

struct APHash
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (size_t i = 0; i < key.size(); i++)
		{
			char ch = key[i];
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
			}
		}
		return hash;
	}
};

struct DJBHash
{
	size_t operator()(const string& key)
	{
		size_t hash = 5381;
		for (auto ch : key)
		{
			hash += (hash << 5) + ch;
		}
		return hash;
	}
};

template<size_t N,class K=string,class HashFunc1=BKDRHash,class HashFunc2=APHash,class HashFunc3=DJBHash>
class BloomFinlter
{
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;
		if (_bs.test(hash1) == false)
			return false;

		size_t hash2 = HashFunc1()(key) % N;
		if (_bs.test(hash2) == false)
			return false;

		size_t hash3 = HashFunc1()(key) % N;
		if (_bs.test(hash3) == false)
			return false;

		return true;


	}
private:
	bitset<N> _bs;
};

4、布隆过滤器的查找

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中,因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找:分别计算每个哈希值对应的比特位置存储的是否为零,只要有一个为零,代表该元素一定不在哈希表中,否则可能在哈希表中。
注意:布隆过滤器如果说某个元素不存在时,该元素一定不存在,如果该元素存在时,该元素可能存在,因为有些哈希函数存在一定的误判。

5、布隆过滤器删除

布隆过滤器不能直接支持删除工作,因为在删除一个元素时,可能会影响其他元素。
一种支持删除的方法:将布隆过滤器中的每个比特位扩展成一个小的计数器,插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一,删除元素时,给k个计数器减一,通过多占用几倍存储空间的代价来增加删除操作。
缺陷:

  1. 无法确认元素是否真正在布隆过滤器中
  2. 存在计数回绕

6、布隆过滤器优点

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

7、布隆过滤器缺陷

  1. 有误判率,即存在假阳性(False Position),即不能准确判断元素是否在集合中(补救方法:再
    建立一个白名单,存储可能会误判的数据)
  2. 不能获取元素本身
  3. 一般情况下不能从布隆过滤器中删除元素
  4. 如果采用计数方式删除,可能会存在计数回绕问题

三、海量数据面试题

1、 哈希切割应用

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址?
在这里插入图片描述

2、位图应用

  1. 给定100亿个整数,设计算法找到只出现一次的整数?
    运用双位图思想,出现0次,第一个位图对应映射的位置为0,第二个位图对应映射的位置为0。
    出现一次,第一个位图对应映射的位置为0,第二个位图对应映射的位置为1。

  2. 给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集?
    二个文件各自映射到位图中,如果都存在,即为文件的交集。

  3. 位图应用变形:1个文件有100亿个int,1G内存,设计算法找到出现次数不超过2次的所有整数
    运用双位图思想,出现次,第一个位图对应映射的位置为0,第二个位图对应映射的位置为0。
    出现一次,第一个位图对应映射的位置为0,第二个位图对应映射的位置为1。
    出现二次,第一个位图对应映射的位置为1,第二个位图对应映射的位置为0。
    出现二次及以上,第一个位图对应映射的位置为1,第二个位图对应映射的位置为1。

3、布隆过滤器应用

  1. 给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

  1. 如何扩展BloomFilter使得它支持删除元素的操作
    运用引用计数的方法。

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

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

相关文章

ZYNQ:CAN总线功能应用

前言 上篇文章解决了ZYNQ搭建PS和PL系统的问题&#xff0c;相当于完成最小系统板搭建。因此&#xff0c;本篇文章主要用于记录搭建CAN外设系统会出现的问题。由于ZYNQ系统包含PS和PL两个部分&#xff0c;PS部分往往问题较少&#xff0c;所以考虑先搭建PS系统的CAN外设系统。熟…

微信网页授权之使用完整服务解决方案

目录 微信网页授权能力调整造成的问题 能力调整的内容和理由 原有运行方案 is_snapshotuser字段 改造原有方案 如何复现测试场景 小结 微信网页授权能力调整造成的问题 依附于第三方的开发&#xff0c;做为开发者经常会遇到第三方进行规范和开发的调整&#xff0c;如开…

PCL安装以及CGAL构建三维凸包

基础理论专栏目录 - 知乎 (zhihu.com) 凸包问题——概述 - 知乎 (zhihu.com) 1、安装PCL 安装pcl,我的是window10,vs2019。我安装的是1.13 win10系统下 VS2019点云库PCL1.12.0的安装与配置_windows 10使用pcl-CSDN博客 照着上述博客进行配置&#xff0c;再结合这个设置环境变…

微信小程序(三十三)promise异步写法

注释很详细&#xff0c;直接上代码 上一篇 新增内容&#xff1a; 1.promise异步与普通异步的写法区别 2.promise异步的优势 源码&#xff1a; index.wxml <view class"preview" bind:tap"onChoose"><image src"{{avatar}}" mode"…

WorkPlus Meet视频会议系统,支持局域网部署

随着科技的不断发展&#xff0c;视频会议系统已经成为企业、教育机构和医疗领域等各行各业远程协作和沟通的重要工具。恒拓高科的WorkPlus Meet视频会议系统以其强大的功能和便捷的操作&#xff0c;满足了不同行业的实际需求&#xff0c;成为市场上备受青睐的解决方案。 在金融…

Vue3+TS+Vite+Pinia最全学习总结

VUE3介绍 vue2和vue3之间的区别 因为需要遍历data对象上所有属性&#xff0c;所以如果data对象属性结构嵌套很深&#xff0c;就会存在性能问题。因为需要遍历属性&#xff0c;所有需要提前知道对象上有哪些属性&#xff0c;才能将其转化为getter和setter,所以vue2中无法将data新…

【详细教程】Kubernetes集群部署:使用kubeadm创建集群

文章目录 一、虚拟机准备&#xff08;一&#xff09;主机基本配置&#xff08;二&#xff09;安装docker&#xff08;三&#xff09;配置cri-docker环境&#xff08;四&#xff09;安装kubeadm、kubelet、kubectl&#xff08;五&#xff09;克隆主机 二、环境配置工作&#xff…

阿里计算巢:开启数据集市场的宝库,助力AI研究和应用

阿里计算巢 阿里数据巢提供了一个丰富的数据集市场&#xff0c;官方地址&#xff1a; https://computenest.console.aliyun.com/dataset/service/cn-hangzhou 可以看到数据集内容涵盖了多个领域&#xff0c;且还在不断增加中。关键是免费&#xff01;且支持下载到本地。 以下…

MC插件服教程-paper+游戏云VPS

首先必须要先买一台VPS&#xff0c;这里以i9的机型做演示 购买完成等待大约1分钟服务器就会创建完成&#xff0c;之后在管理页可以看到服务器的连接信息 image772356 43 KB 首先复制下远程连接地址&#xff0c;此处即k.rainplay.cn:13192 之后在系统里搜索“rdp”或“远程桌面…

一文学会yum源配置(联网/未联网)以及yum常用命令

1、yum源介绍 yum&#xff08;Yellow dog Updater Modified的简称&#xff09;&#xff0c;yum的宗旨是自动化地升级&#xff0c;安装/移除rpm包&#xff0c;收集rpm包的相关信息&#xff0c;检查依赖性并自动提示用户解决。yum的关键之处是要有可靠的repository&#xff0c;顾…

Linux安装svn服务器和权限配置_亲测成功

Linux安装svn服务器和权限配置_亲测成功 SVN简介 SVN是Subversion的简称&#xff0c;是一个开放源代码的版本控制系统&#xff0c;通过采用分支管理系统的高效管理&#xff0c;简而言之就是用于多个人共同开发同一个项目&#xff0c;实现共享资源&#xff0c;实现最终集中式的…

C# OMRON PLC FINS TCP协议简单测试

FINS(factory interface network service)通信协议是欧姆龙公司开发的用于工业自动化控制网络的指令&#xff0f;响应系统。运用 FINS指令可实现各种网络间的无缝通信&#xff0c;包括用于信息网络的 Etherne(以太网)&#xff0c;用于控制网络的Controller Link和SYSMAC LINK。…

【C++】C++入门 — 类和对象初步介绍

类和对象 1 类的作用域2 类的实例化3 类对象模型4 this指针介绍&#xff1a;特性&#xff1a; Thanks♪(&#xff65;ω&#xff65;)&#xff89;谢谢阅读&#xff01;下一篇文章见&#xff01;&#xff01;&#xff01; 1 类的作用域 类定义了一个新的作用域&#xff0c;类的…

stable-diffusion | v1-5-pruned.ckpt和v1-5-pruned-emaonly.ckpt的区别

https://github.com/runwayml/stable-diffusion?tabreadme-ov-file#reference-sampling-script 对于 1.5 模型&#xff0c;其中可能包括四部分&#xff1a;标准模型、文本编码器、VAE模型、EMA模型。 标准模型&#xff1a;生成图片的核心模块&#xff0c;潜空间中的前向扩散和…

创新大赛专访丨南沙人才荣膺2023年度人才寻猎标杆品牌:吸纳海内外高学历人才,助力南沙精准“选苗”

日前&#xff0c;2023第三届全国人力资源创新大赛颁奖典礼暨成果展圆满举行。自2023年10月份启动以来&#xff0c;大赛共吸引了457个案例报名参赛&#xff0c;经组委会专家团队评审严格审核&#xff0c;企业赛道共有103个案例获奖、72家企业、13位个人、7个产业园斩获荣誉。 广…

SpringMVC-组件解析

一、引子 我们在上一篇文章Spring MVC-基本概念中&#xff0c;为读者解释了如何使用SpringMVC框架&#xff0c;将承接客户端请求的工作从原生的Servlet转移到我们熟知的Controller中。那么我们不禁会好奇&#xff0c;SpringMVC框架到底做了什么&#xff0c;是怎么把请求分发给…

【涵子来信】——拆机,感想

大家好&#xff0c;我是涵子。 初中的第一个学期结束了&#xff0c;来临寒假。我在寒假做了一件有趣的事情&#xff1a;拆机&#xff0c;修手机。今天我来分享分享这件事情。 拆机 情况介绍 拆机对象&#xff1a; iPhone 6 Plus 情况&#xff1a; 电池健康度100%&#xff08…

张维迎《博弈与社会》威胁与承诺(4)宪政与民主

有限政府 动态博弈理论对我们理解民主与法治具有重要的意义。 自人类进入文明时代以来&#xff0c;政府就是社会博弈重要的参与人。任何社会要有效运行&#xff0c;都需要赋予政府一些自由裁量权。但如果政府的自由裁量权太大&#xff0c;政府官员为所欲为&#xff0c;不仅老百…

最新酒桌小游戏喝酒骰子小程序源码/带流量主

2023最新酒桌小游戏喝酒小程序源码-带流量主&#xff0c;喝酒神器3.6修改增加了广告位&#xff0c;直接上传源码到开发者端即&#xff0c;可通过后改广告代码&#xff0c;然后关闭广告展示提交&#xff0c;通过后打开即可。 流量主ID替换插屏广告位 adunit-29629a7b54a41a8b视频…

2024年【G2电站锅炉司炉】模拟试题及G2电站锅炉司炉考试试题

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2024年【G2电站锅炉司炉】模拟试题及G2电站锅炉司炉考试试题&#xff0c;包含G2电站锅炉司炉模拟试题答案和解析及G2电站锅炉司炉考试试题练习。安全生产模拟考试一点通结合国家G2电站锅炉司炉考试最新大纲及G2电站锅…