[C++]哈希应用-海量数据处理

文章目录

海量数据处理
前言
哈希切分
- 问题1：给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？
- 问题2：给一个超过100G大小的log file, log中存着IP地址, 设计算法找到top K的IP？
位图应用
- 问题3：给定100亿个整数，设计算法找到只出现一次的整数？
- 问题4：给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
- 问题5：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数
布隆过滤器
- 问题6：给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法

海量数据处理

哈希的一大重要运用就是对于大数据的处理，通过本章的学习，将会带您解决如下面试题：

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？
与上题条件相同，如何找到top K的IP？
给定100亿个整数，设计算法找到只出现一次的整数？
给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数
给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法

我们将把上述7个问题分成3个部分：

1~2：哈希切分

3~5：位图应用

6：布隆过滤器

前言

对于占用空间极大的文件，我们按理来说确实可以通过对硬盘进行IO的方式来实现需求（即将数据的处理主要放在硬盘中进行，而非内存），但是需要明确几点：

（主要）内存的IO速度远超硬盘的IO速度，所以单次硬盘IO于多次硬盘IO的速度差别是十分大的
在硬盘中，各种数据结构的实现较为麻烦（如map、priority_queue…）

哈希切分

问题1：给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？

问题分析：

100G的文件 -> 普通人的内存中肯定放不下，所以需要一种方式来存储
需要记录IP出现的次数

如何存储？

使用位图来存储，可能是很多人第一时间想到的方案，但是他存在几个问题：

如何记录数据的出现次数？或许你可以通过扩展位图的方式（多个bit记录一个数据，这样就可以记录数据出现的次数），但是在极端情况下（如100G的文件全是同一个IP），你不知道应该将几个bit用来记录一个数据的出现次数
假设我们有8G的内存，如果使用位图存储，假设不记录出现次数，那么假设这100G的IP都不相同，每个IP占10个字节。那么要想将他们全部存储到位图中，则位图需要开辟100G/10B=10,485,760即10G的空间，此时已经不够用了（更不用说扩展位图来增加对数据的计数了）

所以我们就需要使用哈希切分的方法

解决方案：

使用哈希切分，原理：

在这里插入图片描述

如果一次性将100G的数据全部处理，那么我们的内存是放不下的，但是如果将这个文件分成了多个小文件（比如，分成100个大小为1G的文件，那么这些小文件内的数据就可以全部读入内存中）

遍历这个100G的文件（因为一次只提取一个IP数据，所以不会存在内存空间不够的情况）
对遍历到的每一个IP做一次哈希映射并模100，得到的数据是多少，就追加写入第几个小文件中，这样就保证相同的IP一定会进入相同的文件
遍历完之后，将每个小文件中的数据放入内存中，用map或unordered_map来记录IP的出现次数，通过比较找出最大值

这里我们对100G文件在极端情况下进行说明：

如果IP值全一样，那么这100G的数据全部会映射到一个小文件中（小文件可以很大，前面只是假设为1G），那这个小文件内的所有数据也放不进内存中，岂不是和没有映射一样了吗？对，这确实和没有映射一模一样，采用map或unordered_map可以解决这种情况下数据不能全放入内存的问题
如果IP值全不一样，那么这100G的数据在进行映射+模后，会出现如下情况：
- 哈希函数设置的合理：100G的IP映射到了各种不同的小文件中，这样每次只对一个小文件进行处理，内存空间就足够收纳所有的小文件的数据了
- 哈希函数设置的不合理：产生了大量的冲突，导致大量的IP都进入了一个文件中，此时你可以进行一下检查：如果你的小文件中的数据大小已经超过了1G，则使用另一个哈希函数继续对这个1G的小文件进行哈希切分（即再用几个1G的文件来映射该小文件的内容）

问题2：给一个超过100G大小的log file, log中存着IP地址, 设计算法找到top K的IP？

方法1：在前面的基础上，进行多次最大值的查找，每一次都将前一次查找最大值屏蔽掉。

方法2：使用priority_queue代替map来存储数据，控制priority_queue的大小为K，就可以实现了

位图应用

问题3：给定100亿个整数，设计算法找到只出现一次的整数？

问题分析：

100亿个整数 -> 如果使用1个bit记录一个数据，假设整数占4个字节，则一个位图需要占用2*2147483647/(8*1024*1024*1024)=0.5G的空间
只出现一次的整数 -> 则意味着需要一个计数的玩意，最次也需要一个状态位来判断出现的次数是否超过1次，所以可以采用扩展位图或者使用两个位图的方法

如何记录出现次数？

这里采用2个位图，由于一个位图需要占用0.5G的内存，所以2个位图完全够用。如果数据出现次数==1，则在位图1中的对应位置置1，第2次出现时，在位图2中对应位置置1。出现次数>2时，不对位图进行任何修改。

最后通过2个位图对应位置进行^操作，就可以判断哪些数据只出现了1次。

问题4：给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？

这里我们假设整数为int占4个字节，那么总共有2*2147483647个数据。需要使用2个位图，假设一个位图的最大存储空间为0.5G，则每个文件可存储0.5*1024*1024*1024*8=4,294,967,296个数据，能覆盖整数的范围，所以1G的内存完全可以放的下两个位图

方法和前面一样，2个位图，一个记录文件1的数据，一个记录文件2的数据，最后进行一下&操作就可以实现

问题5：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数

这里我们假设整数占4个字节，那么总共有2*2147483647个数据。需要使用3个位图，假设一个位图的最大存储空间为0.3G，则每个文件可存储0.3*1024*1024*1024*8=2,576,980,377个数据，此时发现不能覆盖整数的范围（该位图不能表示整数的全部数据），所以需要进行哈希切分。

在这里插入图片描述