大数据处理

一：hash分流

分而治之/hash映射 -> hash统计 -> 堆/快速/归并排序 -> 就是先映射，而后统计，最后排序:

用于海量数据中查找次数最多的几个数据

• 分而治之/hash映射: 针对数据太大，内存受限，只能是: 把大文件化成(取模映射)小文件，即16字方针: 大而化小，各个击破，缩小规模，逐个解决

• hash_map统计: 当大文件转化了小文件，那么我们便可以采用常规的hash_map(ip，value)来进行频率统计。

• 堆/快速排序: 统计完了之后，便进行排序(可采取堆排序)，得到次数最多 / TopK

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

1. 首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中。
2. 注意到IP是32位的，最多有个2³²个IP。
3. 同样可以采用映射的方法，比如%1000，把整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP(可以采用hashMap对那1000个文件中的所有IP进行频率统计，然后依次找出各个文件中频率最大的那个IP)及相应的频率。
4. 然后再在这1000个最大的IP中，找出那个频率最大的IP，即为所求。

Hash取模是一种等价映射，不会存在同一个元素分散到不同小文件中的情况，即这里采用的是mod1000算法，那么相同的IP在hash取模后，只可能落在同一个文件中，不可能被分散的。因为如果两个IP相等，那么经过Hash(IP)之后的哈希值是相同的，将此哈希值取模(如1000)，必定仍然相等

举个例子：寻找热门查询，300万个查询字符串中统计最热门的10个查询（TopK问题）

如果数据大则划为小的，如如一亿个ip求Top 10，可先%1000将ip分到1000个小文件中去，并保证一种ip只出现在一个文件中，再对每个小文件中的ip进行hashmap计数统计并按数量排序，最后归并或者最小堆依次处理每个小文件的Top 10以得到最后的结。

如果数据规模比较小，能一次性装入内存呢, 我们可以考虑把他们都放进内存中去(300万个字符串假设没有重复，都是最大长度，那么最多占用内存0.75G。所以可以将所有字符串都存放在内存中进行处理)，而现在只是需要一个合适的数据结构，在这里，HashTable绝对是我们优先的选择。

所以我们放弃分而治之 / hash映射的步骤，直接上hash统计，然后排序。

所以针对此类典型的TOP K问题，采取的对策往往是: hashmap + 堆。

举个例子：有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词

1. 分而治之：顺序读取文件中，对于每一个x, 取hash(x) % 5000，然后按照该值存储到5000个小文件，这样每一个文件大概是200k左右，如果其中的文件超过了1M的大小，将继续往下分，直到分解得到的小文件的大小都不超过1M。
2. hashMap统计：对于每一个小的文件，采用trie树 / hashMap等统计每一个文件中出现的词和相应的频率。
3. 堆 / 归并排序：将这些每一个文件中的最大的10个值的频率存入得到相应的5000个文件，最终进行归并排序。

举个例子：海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10

如果每个数据元素只出现一次，而且只出现在某一台机器中，那么可以采取以下步骤统计出现次数TOP10的数据元素

• 在每台电脑上求出TOP10，可以采用包含10个元素的堆完成(TOP10小，用最大堆，TOP10大，用最小堆，比如求TOP10大，我们首先取前10个元素调整成最小堆，如果发现，然后扫描后面的数据，并与堆顶元素比较，如果比堆顶元素大，那么用该元素替换堆顶，然后再调整为最小堆。最后堆中的元素就是TOP10大)。
• 求出每台电脑上的TOP10后，然后把这100台电脑上的TOP10组合起来，共1000个数据，再利用上面类似的方法求出TOP10就可以了。

但如果同一个元素重复出现在不同的电脑中

• 遍历一遍所有数据，重新hash取摸，如此使得同一个元素只出现在单独的一台电脑中，然后采用上面所说的方法，统计每台电脑中各个元素的出现次数找出TOP10，继而组合100台电脑上的TOP10，找出最终的TOP10。
• 或者，暴力求解: 直接统计统计每台电脑中各个元素的出现次数，然后把同一个元素在不同机器中的出现次数相加，最终从所有数据中找出TOP10

举个例子：给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url

可以估计每个文件安的大小为5G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。

• 分而治之/hash映射: 遍历文件a，对每个url求取，然后根据所取得的值将url分别存储到1000个小文件(记为，这里漏写个了a1)中。这样每个小文件的大约为300M。遍历文件b，采取和a相同的方式将url分别存储到1000小文件中(记为)。这样处理后，所有可能相同的url都在对应的小文件()中，不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。

• hash_set统计: 求每对小文件中相同的url时，可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了

二：双层桶

1：什么是双层桶

什么是双层桶

事实上，与其说双层桶划分是一种数据结构，不如说它是一种算法设计思想。

面对一堆大量的数据我们无法处理的时候，我们可以将其分成一个个小的单元，然后根据一定的策略来处理这些小单元，从而达到目的。

使用范围

第k大，中位数，不重复或重复的数字

思想

因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。

可以通过多次缩小，双层只是一个例子，分治才是其根本（只是“只分不治”）。

2：双层桶案例

五亿个int中找到中位数

• 思路一

首先我们将int划分为2¹⁶个区域，然后读取数据统计落到各个区域里的数的个数，之后我们根据统计结果就可以判断中位数落到那个区域，同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。

实际上，如果不是int是int64，我们可以经过3次这样的划分即可降低到可以接受的程度。

即可以先将int64分成2²⁴个区域，然后确定区域的第几大数，在将该区域分成2²⁰个子区域，然后确定是子区域的第几大数，然后子区域里的数的个数只有2²⁰，就可以直接利用direct addr table进行统计了。

• 思路二

同样需要做两遍统计，如果数据存在硬盘上，就需要读取2次。

方法同基数排序有些像，开一个大小为65536的Int数组，第一遍读取，统计Int32的高16位的情况，也就是0-65535，都算作0,65536 - 131071都算作1。

就相当于用该数除以65536。Int32 除以 65536的结果不会超过65536种情况，因此开一个长度为65536的数组计数就可以。每读取一个数，数组中对应的计数+1，考虑有负数的情况，需要将结果加32768后，记录在相应的数组内。

第一遍统计之后，遍历数组，逐个累加统计，看中位数处于哪个区间，比如处于区间k，那么0- k-1的区间里数字的数量sum应该<n/2(2.5亿)。

而k+1 - 65535的计数和也<n/2，第二遍统计同上面的方法类似，但这次只统计处于区间k的情况，也就是说(x / 65536) + 32768 = k。统计只统计低16位的情况。

利用刚才统计的sum，比如sum = 2.49亿，那么现在就是要在低16位里面找100万个数(2.5亿-2.49亿)。

这次计数之后，再统计一下，看中位数所处的区间，最后将高位和低位组合一下就是结果了。

三：外排序

借助外部存储进行排序

• 适用范围: 大数据的排序，去重
• 基本原理及要点: 外排序的归并方法，置换选择败者树原理，最优归并树

1：经典问题

输入：一个最多含有n个不重复的正整数的文件，其中每个数都小于等于n，且n=10^7（1000万个）。

输出：得到按从小到大升序排列的包含所有输入的整数的列表。

条件：

1. 最多有大约1MB的内存空间可用，但磁盘空间足够。

2. 且要求运行时间在5分钟以下，10秒为最佳结果。

2：位图排序法

用一个20位长的字符串来表示一个所有元素都小于20的简单的非负整数集合

边框用如下字符串来表示集合{1,2,3,5,8,13}：0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0；

上述集合中各数对应的位置则置1，没有对应的数的位置则置0。

所以，此问题用位图的方案分为以下三步进行解决：

• 第一步，将所有的位都置为0，从而将集合初始化为空。
• 第二步，通过读入文件中的每个整数来建立集合，将每个对应的位都置为1。
• 第三步，检验每一位，如果该位为1，就输出对应的整数。

经过以上三步后，产生有序的输出文件。令n为位图向量中的位数（本例中为1000 0000），程序可以用伪代码表示如下：

//磁盘文件排序位图方案的伪代码
//copyright@ Jon Bentley
//July、updated，2011.05.29。
 
//第一步，将所有的位都初始化为0
for i ={0,....n}    
   bit[i]=0;
   
//第二步，通过读入文件中的每个整数来建立集合，将每个对应的位都置为1。
for each i in the input file   
   bit[i]=1;
 
//第三步，检验每一位，如果该位为1，就输出对应的整数。
for i={0...n}    
  if bit[i]1      
    write i on the output file

上述的位图方案，共需要扫描输入数据两次，具体执行步骤如下：

• 第一次，只处理1—4999999之间的数据，这些数都是小于5000000的，对这些数进行位图排序，只需要约5000000/8=625000Byte，也就是0.625M，排序后输出。
• 第二次，扫描输入文件时，只处理4999999-10000000的数据项，也只需要0.625M（可以使用第一次处理申请的内存）。

因此，总共也只需要0.625M

位图的的方法有必要强调一下，就是位图的适用范围为针对不重复的数据进行排序，若数据有重复，位图方案就不适用了

3：多路归并排序

我们以一个包含很多个整数的大文件为例，来说明多路归并的外排序算法基本思想。

假设文件中整数个数为N(N是亿级的)，整数之间用空格分开。

首先分多次从该文件中读取M（十万级）个整数，每次将M个整数在内存中使用内部排序之后存入临时文件，这样就得到多个外部文件

对应于多个外部文件，我们可以利用多路归并将各个临时文件中的数据一边读入内存，一边进行归并输出到输出文件。

显然，该排序算法需要对每个整数做2次磁盘读和2次磁盘写。

我们来编程实现上述磁盘文件排序的问题，代码思路对应上面图由两部分构成：

• 内存排序
  • 由于要求的可用内存为1MB，那么每次可以在内存中对250K的数据进行排序，然后将有序的数写入硬盘。
  • 那么10M的数据需要循环40次，最终产生40个有序的文件。
• 归并排序
  • 将每个文件最开始的数读入(由于有序，所以为该文件最小数)，存放在一个大小为40的first_data数组中；
  • 选择first_data数组中最小的数min_data，及其对应的文件索引index；
  • 将first_data数组中最小的数写入文件result，然后更新数组first_data(根据index读取该文件下一个数代替min_data)；
  • 判断是否所有数据都读取完毕，否则返回2

四：bitMap

BitMap，即位图，使用每个位表示某种状态，适合处理整型的海量数据。本质上是哈希表的一种应用实现，原理也很简单，给定一个int整型数据，将该int整数映射到对应的位上，并将该位由0改为1。例如：

bitMap的核心就是如何用一个bit位表示一个数

每一位表示一个数，0表示不存在，1表示存在，这正符合二进制

这样我们可以很容易表示{1,2,4,6}这几个数：

计算机内存分配的最小单位是字节，也就是8位，那如果要表示{12,13,15}怎么办呢？当然是在另一个8位上表示了：

这样的话，好像变成一个二维数组了

1个int占32位，那么我们只需要申请一个int数组长度为int tmp[1+N/32]即可存储，其中N表示要存储的这些数中的最大值，于是乎：

tmp[0]：可以表示0~31

tmp[1]：可以表示32~63

tmp[2]：可以表示64~95

。。。

如此一来，给定任意整数M，那么M/32就得到下标，M%32就知道它在此下标的哪个位置

1：添加 -> 异或

这里有个问题，我们怎么把一个数放进去呢？例如，想把5这个数字放进去，怎么做呢？

首先，5/32=0，5%32=5，也是说它应该在tmp[0]的第5个位置，那我们把1向左移动5位，然后按位或

2：清除 -> 0位与

只需将该数所在的位置为0即可

1左移6位，就到达6这个数字所代表的位，然后按位取反，最后与原数按位与，这样就把该位置为0了

每一位代表一个数字，1表示存在，0表示不存在。通过把该为置为1或者0来达到添加和清除，那么判断一个数存不存在就是判断该数所在的位是0还是1

假设，我们想知道3在不在，那么只需判断 b[0] & (1<<3) 如果这个值是0，则不存在，如果是1，就表示存在

int a[i] = {1, 2, 3, 4, 5, 6};
BitSet bitSet = new BitSet(6); // nbits -> 6

for (int i = 0; i < a.length; i ++) {
    bitSet.add(a[i], true); // 对应的位置成true
}

sout(bitSet.size()); // 64
sout(bitSet.get(7)); // false
sout(bitSet.get(3)); // true

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

方案1: 采用2-Bitmap(每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义)进行，共需内存2^32 2 bit=1 GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。

方案2: 也可采用分治，划分小文件的方法。然后在小文件中找出不重复的整数，并排序。然后再进行归并，注意去除重复的元素。

五：布隆过滤器

直观的说，bloom算法类似一个hash set，用来判断某个元素（key）是否在某个集合中。

和一般的hash set不同的是，这个算法无需存储key的值，对于每个key，只需要k个比特位，每个存储一个标志，用来判断key是否在集合中。

1：布隆过滤器概述

如果想判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。

链表，树等等数据结构都是这种思路. 但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢。

不过世界上还有一种叫作散列表（又叫哈希表，Hash table）的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列（Bit Array）中的一个点。

这样一来，我们只要看看这个点是不是1就知道可以集合中有没有它了。这就是布隆过滤器的基本思想。

Hash面临的问题就是冲突。

假设Hash函数是良好的，如果我们的位阵列长度为m个点，那么如果我们想将冲突率降低到例如1%, 这个散列表就只能容纳 m/100 个元素。显然这就不叫空间有效了

解决方法也简单，就是使用多个 Hash，如果它们有一个说元素不在集合中，那肯定就不在。如果它们都说在，虽然也有一定可能性它们在说谎，不过直觉上判断这种事情的概率是比较低的。

2：算法

1. 首先需要k个hash函数，每一个函数可以将key散列成为一个整数
2. 初始化的时候，需要一个长度是n的bit的数组，每一个bit位初始化为0
3. 某一个key加入到集合中，用k个hash函数算出k个散列值，并将数组中对应的bit位置为1
4. 判断某个key是否在集合时，用k个hash函数计算出k个散列值，并查询数组中对应的比特位，如果所有的比特位都是1，认为在集合中。

3：优缺点

• 不需要存储key节省时间

• 算法判断key在集合中时，有一定的概率key其实不在集合中

• 无法进行删除

下图是布隆过滤器假正例概率p与位数组大小m和集合中插入元素个数n的关系图

假定Hash函数个数选取最优数目：

4：布隆过滤器解决redis缓存穿透