海量数据处理总结

备战百度，在海量数据处理的主题上做一个总结。
详情来自cnblogs

1.Bloom Filter

将数据通过hash函数映射到位数组，比如hash(str)=3则将位数组第三位置为1
对每一条数据都用k个hash函数进行映射，也就是一条数据会将位数组的最多k位的值置1。

在查找数据是否存在的时候，则对其进行k次hash，如果位数组中对应的各位都被置1了，则说明该数据已经存在（明显是有一定错误率的）
Bloom Filter可以用来实现数据字典，进行数据的判重，或者集合求交集。
同时，对其进行改进，即位数组每一位不再是0/1，而是数据出现的次数counter，那么出现数据则+1，删除数据则-1，这样可以实现删除操作。

实例：

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

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

2.Hash 表

Hash 表主要是整合了线性表“定位容易，添加删除复杂”和链表“添加删除容易定位复杂”的特点，将二者结合起来。线性表每一个元素位一个指针，指向一个链表。通过hash函数将一个数据映射到某个元素指向的链表上。如此查找是可以通过hash定位到链表，在链表中进行添加删除操作。

散列的方法有很多，不同的散列算法会导致链表的分布均衡问题。比较好的算法是非波那契算法

index = (value * 理想乘数) >> 28

其中理想乘数为：

1. 对于16位整数而言，这个乘数是40503  
2. 对于32位整数而言，这个乘数是2654435769
3. 对于64位整数而言，这个乘数是11400714819323198485

适用

hash表适用于快速查找，但是需要数据可以全部放入内存。
作为扩展，可以使用d-left hashing。

D-left Hashing

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，同时查找两个位置。

实例：

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

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

3. Bit Map

类似遇Bloom Filter。若value==3，则将位数组第 3 位置 1 。这样，对于一串数字，进行如此造作后，从便利该位数组，若某位为1则输出下标，这样便完成了排序。
和插入排序很类似，但是其存储空间很小，适用于大量数据的排序，查重等操作。

实例

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

8位最多99 999 999，大概需要99m个bit，大概10几m字节的内存即可。 （可以理解为从0-99 999 999的数字，每个数字对应一个Bit位，所以只需要99M个Bit==12.4MBytes，这样，就用了小小的12.4M左右的内存表示了所有的8位数的电话）

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

将bit-map扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出现2次及以上，在遍历这些数的时候，如果对应位置的值是0，则将其置为1；如果是1，将其置为2；如果是2，则保持不变。或者我们不用2bit来进行表示，我们用两个bit-map即可模拟实现这个2bit-map，都是一样的道理。

4. 堆

二叉堆是一种二叉树，最大堆为例，没一个节点都小于它的字节点。树是完全平衡的，并且最后一层的树叶都在最左边。
堆的操作主要是添加和删除。

适用

海量数据前n大，并且n比较小，堆可以放入内存

实例

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

5. 双层桶思想

当数据量过大的时候，进行比较，查找处理较为复杂，因此可以考虑将大量数据操作划分位对很多小部分数据的操作。直接看例子：

实例

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

有点像鸽巢原理，整数个数为2^32,也就是，我们可以将这2^32个数，划分为2^8个区域(比如用单个文件代表一个区域)，然后将数据分离到不同的区域，然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间，就可以很方便的解决。 当然这个题也可以用我们前面讲过的BitMap方法解决，正所谓条条大道通罗马~~~

2).5亿个int找它们的中位数。

这个例子比上面那个更明显。首先我们将int划分为2^16个区域，然后读取数据统计落到各个区域里的数的个数，之后我们根据统计结果就可以判断中位数落到那个区域，同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。
实际上，如果不是int是int64，我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域，然后确定区域的第几 大数，在将该区域分成2^20个子区域，然后确定是子区域的第几大数，然后子区域里的数的个数只有2^20，就可以直接利用direct addr table进行统计了。

3).现在有一个0-30000的随机数生成器。请根据这个随机数生成器，设计一个抽奖范围是0-350000彩票中奖号码列表，其中要包含20000个中奖号码。

这个题刚好和上面两个思想相反，一个0到3万的随机数生成器要生成一个0到35万的随机数。那么我们完全可以将0-35万的区间分成35/3=12个区间，然后每个区间的长度都小于等于3万，这样我们就可以用题目给的随机数生成器来生成了，然后再加上该区间的基数。那么要每个区间生成多少个随机数呢？计算公式就是：区间长度_随机数密度，在本题目中就是30000_（20000/350000）。最后要注意一点，该题目是有隐含条件的：彩票，这意味着你生成的随机数里面不能有重复，这也是我为什么用双层桶划分思想的另外一个原因。

6.数据库索引

7.倒排索引

所谓倒排索引的意思，就是建立索引的时候，不是按照key-文档，value-语素这样的形式建立，而是按照key-语素，value-文档这种形式，而且在value中保存了文档编号和该文档中出现语素的次数等信息。
因此在检索的时候，不必遍历所有文档，而只需便利查找的query关键字即可。