哈希思想的应用:位图、布隆过滤器及哈希切割

一.位图引入

给40定亿个不重复的无符号整数存储在文件中,如何判断一个数在不在其中?

分析:最容易想到的思路是将这些数字存储到某个能够实现快速查找的容器中,如红黑树或哈希表。

但是,10亿个字节大约占1G内存,那么40亿个整数如果想要在内存中存储需要16G空间。

故使用set(红黑树)或unordered_set(哈希表)等容器来存储是不现实的,主要原因就是内存不够。 

对于这种判断在不在的问题,不需要将数字直存储起来,而是用数字映射一个比特位,该bit标识在与不在两种状态即可。这样的数据结构,就叫做位图。

二.位图实现

  1. 非类型模版参数N,表示你想要开多少个bit的位图,这取决于数据的范围。如果数据是100以内的正整数,只需要开100bit;如果数据是unsigned int,需要开2^32个bit(512M内存)
  2. 数字的映射方法(哈希方法):直接定址法,数字x映射第x个比特位
  3. set接口:将x对应的比特位置为1,标识x在位图中
  4. reset接口:将x对应的比特位置为0,标识x不在位图中
  5. test接口:判断x是否在位图中,只需判断x对应的比特位是0还是1
template<size_t N>class bitset{private:vector<char> _bits;public:bitset(): _bits(N/8+1, 0){}void set(size_t x){size_t i = x / 8;size_t j = x % 8;//将_bits[i]的第j位置为1_bits[i] |= (1 << j);}void reset(size_t x){size_t i = x / 8;size_t j = x % 8;//将_bits[i]的第j位置为0_bits[i] &= ~(1 << j);}bool test(size_t x){size_t i = x / 8;size_t j = x % 8;if (_bits[i] & (1 << j)){return true;}return false;}};

三.位图和哈希表的比较 

  1. 相同点:二者都应用了哈希的思想,即用一个值映射另一个值的思想。二者都用值映射存储位置,只不过哈希表映射的每个存储单元较大,可以存储各种各样类型的数据,但位图映射的每个存储单元只有一个bit,存储的信息非常有限
  2. 不同点:哈希表将值存入了映射的存储空间,而位图没有。故哈希表可以处理哈希冲突(线性探测法或哈希桶),这是因为搜索时可以用值去和存储单元中的值进行比较。而位图不能发生哈希冲突,一个bit只能对应一个值,这也是我们采用直接定址法来映射的原因。

四.位图的应用 

1.给定100亿个整数,找只出现一次的整数

与开头的题目类似,不过这里要想办法表示一个数的三种状态,即出现0次,出现1次,出现2次以上,这需要两个bit才能标识。故可以使用两个位图。

00:第一个位图中x对应的bit位0,第二个位图中x对应的bit为0,表示x出现0次

01:第一个位图中x对应的bit位0,第二个位图中x对应的bit为1,表示x出现1次

10:第一个位图中x对应的bit位1,第二个位图中x对应的bit为0,表示x出现2次及以上

template<size_t N>class twobitset{private:bitset<N> _bs1;bitset<N> _bs2;public:void set(size_t x){if (_bs1.test(x) == false && _bs2.test(x) == false){//00->01bs2.test(x);}else if (_bs1.test(x) && _bs2.test(x) == true){//01->10;bs1.set(x);bs2.reset(x);}}bool test(size_t x){//01->出现1次return bs2.test(x) == true;}};

2.给两个文件,分别有100亿个整数,如何找两个文件的交集--交集中没有没有重复数字

方法一:分别将两个文件的数字放进两个位图,然后遍历每一个比特位,如果该比特位都是1,则对应的数字是交集 

方法二:先将一个文件中的数字放进位图,然后遍历另一个文件,看数字在不在位图中,如果在,则该数字是交集,同时将该数字对应的比特位置0,防止重复。

当文件中的数字个数大于2^32时,遍历比特位的方法更优,否则遍历文件的方法更优

五.布隆过滤器 

位图的缺点是只能只能映射整型,遇到字符串或者其它自定义类型无能为力。哈希表可以映射字符串,它是怎么做的呢?哈希表是先将字符串映射整型,然后再映射存储位置,做了两次哈希。

位图是否可以借鉴这种思路呢?答案是不可以,因为字符串无穷无尽,而整型是有限的,不管你怎么优化哈希方法,一定会存在多个字符串对应一个整型的情况,即使你再采用直接定址法照样会产生哈希冲突,而前面说了由于位图中没有把值存下来,所以不允许哈希冲突,否则判断时可能会出错。

而布隆过滤器直接另辟蹊径,既然哈希冲突可能会使判断出错,那么总有判断结果准确的时候,我不要求判断结果百分百正确,但是我可以想办法降低判断出错的概率。这就是布隆过滤器,它适用于允许判断出错的场景。

那么布隆过滤器是怎么降低出错概率的呢?

以string为例,布隆过滤器采用多种不同的哈希方法,将一string映射出多个整型值,然后再用整型值映射比特位(除留取余法)。这样一来,一个string对应多个bit,只有这几个bit都是1的时候才给出结论;string在位图中,当有一个bit为0时,给出string不在位图中的结论。

具体用几个哈希方法?哈希函数越多,映射的位就越多,误判率越低,但需要的空间就越多。这里直接给出结论,3个哈希函数比较合适,具体的数学推导有兴趣自行研究。

  1. 当给出在位图中的结论时,字符串不一定在位图中,因为这几个bit不一定是该字符串映射的。
  2. 当给出不在位图中的结论时,字符串一定不在位图中,因为没有字符串映射这几个bit

以上两点就是布隆过滤器的核心逻辑,也就是说,判断值不在,这个结论一定是准确的。因此,布隆过滤器才能发挥它的“过滤”功能。

template<size_t N, class K, class Hash1, class Hash2, class Hash3>class BloomFilter{private:bitset _bs;Hash1 _hf1;Hash2 _hf2;Hash3 _hf3;public:void set(const K& key){size_t hash1 = _hf1(key) % N;size_t hash2 = _hf2(key) % N;size_t hash3 = _hf3(key) % N;_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);}bool test(const K& key){size_t hash1 = _hf1(key) % N;size_t hash2 = _hf2(key) % N;size_t hash3 = _hf3(key) % N;return _bs.test(hash1) && _bs.test(hash2) && _bs.test(hash3);}};

六.布隆过滤器的应用

一个典型的例子,当用户注册账号时,需要填写昵称。

可以先将数据库中的所有昵称放进布隆过滤器中,当用户输入昵称时,快速在布隆过滤器中查找昵称是否已经存在。若给出的结果是不在,则一定不在,提示用户昵称可用;若给出的结果是不在,则不能确定在不在,此时再去数据库中查找,以该结果为准,提示用户昵称是否可用。

布隆过滤器的意义在于过滤掉了那些一定不在数据库中的昵称,这样可以减少访问数据库的次数,从而提升效率。

七.布隆过滤器的删除

布隆过滤器原则上是不支持删除的,将一个字符串对应的多个比特位置0,可能会影响其它字符串。

 如图,删除str2就影响了str1,所以布隆过滤器原则上是不支持删除的。

如果想要支持删除,就要使用引用计数的方法,每一个存储单元不再只用一个bit来标识在与不在两种状态,而是用若干个bit作为一个存储单元,标识有多少个值映射到该存储单元。

例如三个bit作为一个存储单元,则该存储单元最多有8个值能映射,set就加1,reset就减1。当判断某个值在不在,只需判断它映射的若干个存储单元是否都不为0即可。

八. 哈希切割

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

近似算法:先将一个文件中的字符串放进布隆过滤器,布隆过滤器越大越好,这样可以减少哈希冲突。既然有1G空间,我们直接开2^33个bit(要用unsigned long long表示)。然后我们再遍历另一个文件,逐一判断字符串是否在布隆过滤器中。

精确算法怎么实现呢?位图只能放整型数据,哈希表,红黑树等又存不下。对此,我们的思路是分块处理,逐个击破,将文件分成若干个小份,不就可以加载进内存了吗?

如何分?平均分吗?分了等于没分,要找交集还是得遍历文件。

这里的问题在于要使的相同的字符串进入同一个文件,于是哈希思想的又一重大应用——哈希切割闪亮登场。

100亿个字符串,假定每个字符串50byte,则有500G大小。我们预计将每个大文件分为500个小文件,于是给每个文件编号:A0,A1,A2……A499,B0,B1,B2……B499。

分别遍历两个文件,所有字符串都用某个固定的哈希方法,映射成整型值,然后模上500,结果是多少,就存入几号文件。

相同的字符串映射出的整型值相同,因此会进入同一个文件。这样,我们就能对每个小文件单独处理了。例如将A0文件的字符串全部加载到内存,哈希表存储,遍历B0文件,逐一判断每个字符串是否在哈希表中。

这里还有一个细节,由于不是平均切割,某个文件可能会特别大,有两种情况。第一,可能是有很多重复的字符串,这并不影响,因为哈希表有去重功能,不会把这些重复的都存进去。第二,可能是有很多相似的字符串经过某种哈希方法映射到了相同文件,这时需要更换哈希方法,将该小文件再次切分成更小的文件。

综上,一开始可以不用考虑这个细节,直接读取文件存进哈希表,当内存不够时会抛出异常,我们只需捕获异常,然后再切分文件。

再看一个问题:

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

解决方案:

哈希切割成若干个小文件,依次处理每个小文件,使用一个unordered_map/map统计ip出现的次数。

如果统计过程中出现抛内存异常,则说明单个文件过大,冲突太多,更换哈希函数,再次哈希切割这个小文件

如果没有抛异常,则正常统计,统计完一个小文件,记录最大的,释放内存,再统计下一个小文件。

如果要求次数最多的ip,则去记录的所有最大值中的最大值。如果要求top K,则建立K个元素的小堆,遍历记录的值来更新堆。最终留下的就是top K。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

智能优化算法应用:基于旗鱼算法无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于旗鱼算法无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于旗鱼算法无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.旗鱼算法4.实验参数设定5.算法结果6.参考文献7.MATLAB…

java springboot测试类Transactional解决 测试过程中在数据库留下测试数据问题

好 目前 我们已经完成了表现层对应的测试了 但这里有个坑 如果我们在执行某个声明周期时 包含了测试的过程 它会在数据库中留下一条数据 但真实企业开发 绝对不允许 过一遍留一组数据的 那么 我们的期望就是 执行测试过程 但不要留下任何数据 这是我们的数据库表 然后 这里…

BGP基本配置

一、知识补充 1、BGP BGP是Border Gateway Protocol&#xff08;边界网关协议&#xff09;的缩写。它是用于在互联网中交换路由信息的一种协议。BGP被广泛应用于大规模的自治系统&#xff08;AS&#xff09;之间&#xff0c;用于实现跨网络的路由选择和交换。 BGP的主要功能…

Unity中Shader的Standard材质解析(二)

文章目录 前言一、我们对 Standard 的 PBR 的 GI 进行解析1、我们先创建一个PBR的.cginc文件&#xff0c;用于整理用到的函数2、然后在Standard的Shader中引用该cginc文件 二、依次整理函数到该cginc文件中我们来看一下PBR中GI的镜面反射做了些什么 二、最终代码.cginc代码&…

中兴亮相中国国际现代化铁路技术装备展览会 筑智铁路5G同行

近日&#xff0c;第十六届中国国际现代化铁路技术装备展览会在北京中国国际展览中心举办&#xff0c;中兴以“数智铁路&#xff0c;5G同行”主题亮相本次展览会&#xff0c;并全面展示了“数字铁路网络基础设施”、“云边结合的铁路行业云”、“数字铁路赋能赋智”等方面的最新…

github国内访问小解(windows)

git 下载安装 使用 github 前必须确保电脑上已经安装了 Git&#xff0c;可以从 Git 官方网站去下载。 官方的网站在国内访问会比较慢&#xff0c;这里可以选择国内镜像&#xff1a;https://registry.npmmirror.com/binary.html?pathgit-for-windows/ github 之旅 确认电脑已…

HCIA-H12-811题目解析(1)

1、【多选题】关于动态 MAC 地址表说法正确的是&#xff1f; A、通过报文中的源MAC地址学习获得的动态MAC表项会老化 B、通过查看指定动态MAC地址表项的个数&#xff0c;可以获取接口下通信的用户数 C、在设备重启后&#xff0c;之前的动态表项会丢失 D、在设备重启后&…

运维 在Windows上搭建小型Git服务

文章目录 1、Git选型1.1、主要特性1.2、代码管理1.3、工单管理1.4、Pull/Merge requests1.5、第三方集成1.6、选型结论 2、环境搭建2.1、Gitea下载2.2、Gitea安装2.3、配置服务信息2.4、运行服务2.5、注册Gitea为服务2.6、正常使用 1、Git选型 1.1、主要特性 1.2、代码管理 1.…

VUE2+THREE.JS项目搭建

THREE项目搭建 简介学习文档推荐搭建1.下载three.js2.新建3DWorkShop.vue文件3.创建utils/three/tool.js4.创建components/three/draw.vue[重点]4.1 引入文件4.2 初始化场景4.3 初始化渲染器4.4 初始化光源4.5 初始化相机(人眼模式)4.6 初始化控制器4.7 初始化动画4.8 添加全局…

GB28181学习(十七)——基于jrtplib实现tcp被动和主动发流

前言 GB/T28181-2022实时流的传输方式介绍&#xff1a;https://blog.csdn.net/www_dong/article/details/134255185 基于jrtplib实现tcp被动和主动收流介绍&#xff1a;https://blog.csdn.net/www_dong/article/details/134451387 本文主要介绍下级平台或设备发流功能&#…

【心得】XXE漏洞利用个人笔记

XML中关于DTD类型(内部(SYSTEM)的和外部(PUBLIC)的区别) xxe的利用 XML Entity 实体注入 当程序处理xml文件时&#xff0c;没有禁止对外部实体的处理&#xff0c;容易造成xxe漏洞 危害 主流是任意文件读取 XML 文件 一般表示带有结构的数据 祖父 3个叔父 8个堂弟堂妹 …

【C++】string模拟

string讲解&#xff1a;【C】String类-CSDN博客 基本框架 #pragma once #include <iostream> using namespace std; ​ namespace wzf {class string{public:// 默认构造函数string(): _str(new char[1]), _size(0), _capacity(0){_str[0] \0; // 在没有内容时仍要有终…

ChatGPT 使用入门

背景 ChatGPT是一个强大的聊天机器人助手&#xff0c;内置了大量的互联网知识文档&#xff0c;且具有上下文记忆&#xff0c;可以帮我们快速地查找一些资料&#xff0c;了解一个知识&#xff0c;帮我们回答问题&#xff0c;编写代码等。此外&#xff0c;在使用ChatGPT时具有一…

拼图游戏制作

2.创建用户界面 package domain; /** * ClassName: User * Author: Kox * Data: 2023/2/2 * Sketch: */ public class User { private String username; private String password; public User() { } public User(String username, String p…

简单好用!日常写给 ChatGPT 的几个提示词技巧

ChatGPT 很强&#xff0c;但是有时候又显得很蠢&#xff0c;下面是使用 GPT4 的一个实例&#xff1a; 技巧一&#xff1a;三重冒号 """ 引用内容使用三重冒号 """&#xff0c;让 ChatGPT 清晰引用的内容&#xff1a; 技巧二&#xff1a;角色设定…

【数据清洗 | 数据规约】数据类别型数据 编码最佳实践,确定不来看看?

&#x1f935;‍♂️ 个人主页: AI_magician &#x1f4e1;主页地址&#xff1a; 作者简介&#xff1a;CSDN内容合伙人&#xff0c;全栈领域优质创作者。 &#x1f468;‍&#x1f4bb;景愿&#xff1a;旨在于能和更多的热爱计算机的伙伴一起成长&#xff01;&#xff01;&…

mysql8下载与安装教程

文章目录 1. MySQL下载2. 方式一&#xff1a;msi文件安装2.1 安装2.2 添加环境变量2.3 登录mysql 3. 方式二&#xff1a;zip文件安装3.1 安装3.2 配置文件3.3 加入环境变量3.4 初始化mysql3.5 登录mysql 1. MySQL下载 以下两个网址二选一 官网&#xff1a;https://downloads.…

LeetCode(46)汇总区间【区间】【简单】

目录 1.题目2.答案3.提交结果截图 链接&#xff1a; 汇总区间 1.题目 给定一个 无重复元素 的 有序 整数数组 nums 。 返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说&#xff0c;nums 的每个元素都恰好被某个区间范围所覆盖&#xff0c;并且不存在属于某…

知识蒸馏代码实现(以MNIST手写数字体为例,自定义MLP网络做为教师和学生网络)

dataloader_tools.py import torchvision from torchvision import transforms from torch.utils.data import DataLoaderdef load_data():# 载入MNIST训练集train_dataset torchvision.datasets.MNIST(root "../datasets/",trainTrue,transformtransforms.ToTens…

鸿蒙系统扫盲(三):鸿蒙开发用什么语言?

1.两种开发方向 我们常说鸿蒙开发&#xff0c;但是其实鸿蒙开发分为两个方向&#xff1a; 一个是系统级别的开发&#xff0c;比如驱动&#xff0c;内核和框架层的开发&#xff0c;这种开发以C/C为主 还有一个是应用级别的开发&#xff0c;在API7以及以下&#xff0c;还是支持…