一、十大海量数据处理方法总结

青旅半醒 2024-04-18 11:22 77阅读 0赞

# 一、布隆过滤器(BloomFilter) #

如果想***判断一个元素是不是在一个集合***里，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路，存储位置要么是磁盘，要么是内存。很多时候要么是以时间换空间，要么是以空间换时间。

在响应时间要求比较严格的情况下，如果我们存在内里，那么随着集合中元素的增加，我们需要的存储空间越来越大，以及检索的时间越来越长，导致内存开销太大、时间效率变低。

此时需要考虑解决的问题就是，在数据量比较大的情况下，既满足时间要求，又满足空间的要求。即我们需要一个时间和空间消耗都比较小的数据结构和算法。Bloom Filter就是一种解决方案。

**适用范围：**可以用来**实现数据字典**，进行**数据的判重**，或者**集合求交集**

## 1、原理 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3MyOTQ4NzgzMDQ_size_16_color_FFFFFF_t_70][]

A、B、C、D 四个数据各自经过 **f1 和 f2** 方法进行两次 hash 算法，然后分别指向位上面，只有当 f1 和 f2 指向的位上面都为 1 时，才会标记为存在。

布隆过滤器的原理是，当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们***只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在***。这就是布隆过滤器的基本思想。

## 2、缺点 ##

bloom filter之所以能做到在时间和空间上的效率比较高，是因为***牺牲了判断的准确率、删除的便利性***

*  存在误判，可能要查到的元素并没有在容器中，但是hash之后得到的k个位置上值都是1。如果bloom filter中存储的是黑名单，那么可以通过建立一个白名单来存储可能会误判的元素。

*  删除困难。一个放入容器的元素映射到bit数组的k个位置上是1，删除的时候不能简单的直接置为0，可能会影响其他元素的判断。可以采用[Counting Bloom Filter][]

1.  举例 1：上图的 A 和 B，虽然 f2 计算的位都是同样的 1，但是各自的 f1 计算出的位是不一样的，所以由此判断出 A 和 B 是不一样的数据。
2.  举例 2：上图的 B 和 C，经过 f1 和 f2 计算出的两个位是一样的，所以由此判断出 B 和 C 是一样的数据。

## 3、如何确定位数组 m 的大小及hash函数 个数 ##

当hash函数个数k=(ln2)\*(m/n)时错误率最小。在错误率不大于E的情况下，m至少要等于n\*lg(1/E)才能表示任意n个元素的集 合。但m还应该更大些，因为还要保证bit数组里至少一半为0，则***m应该>=nlg(1/E)\*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。***

## ***4、*****扩展** ##

Bloom filter将集合中的元素映射到位数组中，用k（k为哈希函数个数）个映射位是否全1表示元素在不在这个集合中。**Counting bloom filter（CBF）将位数组中的每一位扩展为一个counter，从而支持了元素的删除操作。Spectral Bloom Filter（SBF）将其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。**

问题实例：给你A,B两个文件，各存放50亿条URL，每条URL占用64字节(Byte)，内存限制是4G，让你找出 A,B文件共同的URL。如果是三个乃至n个文件呢？

根据这个问题我们来计算下内存的占用，4G=2^32大概是 40亿\*8 大概是340 亿，n=50亿，如果按出错率0.01算需要的大概是650亿个bit。现在可用的是340亿，相差并不多，这样可能会使出错率上升些。另外如果这些 url ip是一 一对应的，就可以转换成ip，则大大简单了。

# 二、Hashing #

**适用范围：快速查找，删除的基本数据结构**，通常需要**总数据量可以放入内存**

## **1、基本原理及要点** ##

hash函数选择，针对字符串，整数，排列，具体相应的hash方法。

碰撞处理，一种是open hashing，也称为拉链法；另一种就是closed hashing，也称开地址法，opened addressing。

## 2、碰撞处理 ##

链接地址（拉链法）是早期提出的可以适应溢出方法的方式。如果你用哈希函数计算的地址***已经被占用，那么一个存储关键字的溢出表将产生，然后在主哈希表的占位地址指向这个溢出表。***如果有更多的冲突发生，这些关键字项将存储于溢出表，并用指针指向这个新添的数据项，所有这些溢出表链将共有一个哈希值。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3MyOTQ4NzgzMDQ_size_16_color_FFFFFF_t_70 1][]

开放地址也是一种选择。开放地址最简单的方法命名很有趣，叫做“线性探针”。如果你要存储一个元素但发现哈希函数计算的地址***已经被占用，那么就继续找到下一个没有被占用的地址，然后将元素存储到这个地址***。这样的结果保证了所有元素都是在哈希表中是线性存储的。

当你要查找用这种方式存储数据方式的元素时，通过哈希函数计算并在表中线性查找直到找到或者找到了空项即可停止。哈希表认为是环形表。比如，最后一个地址的下一个地址是第一个地址。

## 3、**扩展** ##

**d-left hashing**中的d是多个的意思，我们先简化这个问题，看一看2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半，分别叫做T1和T2，给T1和T2分别配备一个哈希函数，h1和h2。在存储一个新的key时，同 时用两个哈希函数进行计算，得出两个地址h1\[key\]和h2\[key\]。这时需要检查T1中的h1\[key\]位置和T2中的h2\[key\]位置，***哪一个 位置已经存储的（有碰撞的）key比较多，***然后将新key存储在负载少的位置。如果两边一样多，比如两个位置都为空或者都存储了一个key，***就把新key 存储在左边的T1子表中，2-left也由此而来。在查找一个key时，必须进行两次hash，同时查找两个位置。***

## **4、问题实例：** ##

1)、海量日志数据，提取出某日访问百度次数最多的那个IP。

**IP的数目还是有限的，最多2^32个**，所以可以考虑使用hash将ip直接存入内存，然后进行统计。

# 三、**bit-map** #

32位机器上，对于一个整型数，比如 int a=1 在内存中占 32bit 位，这是为了方便计算机的运算。但是对于某些应用场景而言，这属于一种巨大的浪费，因为我们可以用对应的 32bit 位对应存储十进制的 0-31个 数（**32个数字**），而这就是Bit-map的基本思想。

Bit-map算法利用这种思想***处理大量数据的排序、查询以及去重***。Bitmap在***用户群做交集和并集运算***的时候也有极大的便利。

## 1、排序 ##

假设我们要对0-7内的5个元素**(4,7,2,5,3)** 进行排序(这里假设元素没有重复)。我们可以使用BitMap算法达到排序目的。要表示8个数，我们需要8个byte。

*  　首先开辟一个字节(8byte)的空间，将这些空间的所有的byte位都设置为0，数组**左侧为第1位**
 *  　遍历这5个元素，第一个元素是4，因为**下标从0开始**，因此我们把第五个字节的值设置为1
 *  　然后再处理剩下的四个元素，最终8个字节的状态如下图
 *  现在我们遍历一次bytes区域，把值为1的byte的位置输出(2,3,4,5,7)，这样便达到了排序的目的

![20190906005934215.png][]

## 2、**去重** ##

2.5亿个整数中***找出不重复的整数的个数***，内存空间不足以容纳这2.5亿个整数。

1.  首先，根据“**内存空间不足以容纳这2.5亿个整数**”我们可以快速的联想到 Bit-map。
2.  int有4个字节，32位bit，最多可表示232个正整数，即4G个正整数(1G=230,1K=210)。
3.  用2Bitmap法，每个正整数用**两个bit的标志位，00表示没有出现，01表示出现1次，10表示出现多次**。
4.  开辟一个用2Bitmap法标志4G个正整数的桶数组，则总共需要4G\*2bit=1G内存。
5.  扫描整数，如果标志位为00（=0），则将对应位置的标志置为01（=1）。如果为01，则置为10（=2）。

## 3、**查询** ##

如何快速**判断一个数字是够存在于上述的2.5亿个数字集合中**。

**方法一：分治法**

对于大数据相关的算法题，分治法是一个非常好的方法。针对这一题来说，主要思路为：可以根据实际可用内存的情况，确定一个Hash函数，比如：hash(value)%1000，通过这个Hash函数可以把这2.5亿个数字划分到1000个文件中去（a1，a2……，a1000），然后再对待查找的数字使用同样的Hash函数求出Hash值，假设计算出的Hash值为i，如果这个数存在，那么它一定在文件ai中。通过这种方法就可以把题目转化为文件ai中是否存在这个数。那么接下来的求解过程中可以选用的思路计较多，有：

（1）由于划分后的文件比较小了，就可以直接装载到内存中去，可以把文件中所有的数字都保存到hash\_set中，然后判断待查找的数字是否存在。

（2）如果这个文件中的数字占用的空间还是太大，那么可以用1相同的方法把这个文件继续划分为更小的文件，然后确定待查找的数字可能存在的文件，然后在相应的文件中继续查找。

**方法二：位图法**

对于这一类判断数字是否存在、判断数字是否重复的问题，位图法是一种非常高效的方法。以32位整型为例，它可以表示数字的个数为2^32.可以申请一个位图，让每个整数对应的位图中的一个bit，这样2^32个数需要的位图的大小为512MB。具体实现的思路为：**申请一个512MB的位图，**并把所有的位都初始化为0；接着遍历所有的整数，对遍历到的数字，把相应的位置上的bit设置为1，最后判断待查找的数对应的位图上的值是多少，如果是0，那么表示这个数字不存在，如果是1，那么表示这个数字存在。

## 4、扩展： ##

bloom filter可以看做是对bit-map的扩展

## 5、问题实例： ##

**1)**、已知某个文件内包含一些电话号码，每个号码为8位数字，**统计不同号码的个数**。

8位最多99 999 999，大概需要 99m 个bit，大概 10 几 m 字节的内存即可。

**例如：**

61234567 对应位 0x00001000

61234568 对应位 0x0001 0000

1.  这样，每一个电话号码也就有了它自己的唯一标识，***而且这个标识只占用1位***，***如果电话号码被统计过，这个位就标识为1，否则标识为0。***
2.  首先 建立一个对应的bitmap，每一位表示某个号码是否统计过（存在），这样 用一个bitmap就表示了所有可能出现的电话号码
3.  然后遍历所有号码，去bitmap查找当前遍历到的号码是否已经出现过，是则个数加一，否则遍历下一个就能统计出来不同号码的个数。
4.  ***已知电话号码是8位，于是相当于范围是从00000000 ---> 9999 9999***，这样无非需要 1亿个bit，也就是95.3M的内存。

# 四、**堆** #

**适用范围**：海量数据前n大，并且n比较小，堆可以放入内存

## 1、基本原理及要点 ##

**问题：**最大堆求前n小，最小堆求前n大。

**方法：**比如**求前n小**，我们比较当前 元素与最大堆里的最大元素，如果它**小于最大元素，则应该替换那个最大元素**。这样最后得到的n个元素就是最小的n个。适合大数据量，求前n小，n的大小比较小的情况，这样可以扫描一遍即可得到所有的前n元素，效率很高。

## 2、扩展 ##

双堆，一个最大堆与一个最小堆结合，可以用来维护中位数。

## 3、问题实例 ##

1)、100w个数中找最大的前100个数。

用一个100个元素大小的最小堆即可。

# 五、**双层桶划分** #

参考:

1、[https://www.cnblogs.com/z941030/p/9218356.html][https_www.cnblogs.com_z941030_p_9218356.html]

2、[https://www.xuebuyuan.com/1304407.html][https_www.xuebuyuan.com_1304407.html]

3、[https://mp.weixin.qq.com/s?\_\_biz=MzU3MzgwNTU2Mg==&mid=2247485151&idx=1&sn=665e5e284934aecd2fcf3d69e26e3b52&chksm=fd3d404aca4ac95c3e4d89a346c797f28bca36aa04640f5c689777eb5fa17b323158544a4c6f&scene=21\#wechat\_redirect][https_mp.weixin.qq.com_s_biz_MzU3MzgwNTU2Mg_mid_2247485151_idx_1_sn_665e5e284934aecd2fcf3d69e26e3b52_chksm_fd3d404aca4ac95c3e4d89a346c797f28bca36aa04640f5c689777eb5fa17b323158544a4c6f_scene_21_wechat_redirect]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3MyOTQ4NzgzMDQ_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/d76f9f34b1c54e23a21d9f3a42261bfd.png
[Counting Bloom Filter]: http://wiki.corp.qunar.com/confluence/download/attachments/199003276/US9740797.pdf?version=1&modificationDate=1526538500000&api=v2
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3MyOTQ4NzgzMDQ_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/44f95e2e6cac4539b5fdef996f7fb94c.png
[20190906005934215.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/9db5e99460084d4bb7a357693197f975.png
[https_www.cnblogs.com_z941030_p_9218356.html]: https://www.cnblogs.com/z941030/p/9218356.html
[https_www.xuebuyuan.com_1304407.html]: https://www.xuebuyuan.com/1304407.html
[https_mp.weixin.qq.com_s_biz_MzU3MzgwNTU2Mg_mid_2247485151_idx_1_sn_665e5e284934aecd2fcf3d69e26e3b52_chksm_fd3d404aca4ac95c3e4d89a346c797f28bca36aa04640f5c689777eb5fa17b323158544a4c6f_scene_21_wechat_redirect]: https://mp.weixin.qq.com/s?__biz=MzU3MzgwNTU2Mg==&mid=2247485151&idx=1&sn=665e5e284934aecd2fcf3d69e26e3b52&chksm=fd3d404aca4ac95c3e4d89a346c797f28bca36aa04640f5c689777eb5fa17b323158544a4c6f&scene=21#wechat_redirect