海量数据处理

空间换算：

目前成都创新互联已为上1000+的企业提供了网站建设、域名、虚拟主机、网站托管、服务器托管、企业网站设计、珠海网站维护等服务，公司将坚持客户导向、应用为本的策略，正道将秉承"和谐、参与、激情"的文化，与客户和合作伙伴齐心协力一起成长，共同发展。

1 Byte = 8 Bits
1 KB = 1024 Bytes
1 MB = 1024 KB
1 GB = 1024 MB

2^2 = 4;

2^4 = 16;

2^8 = 256;

2^10 = 1024;

2^16 = 65 536

2^20 = 1 048 576

2^32 = 4 294 967 296

基本方法

1. hash法

    Hash一般被称为散列，它是以一种映射关系，即给定一个数据元素，其关键字为key，按一个确定的散列函数计算出hash(key)，把hash(key)作为关键字key对应元素的存储地址（或称散列地址），再进行数据元素的插入和检索操作。简而言之，散列函数就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

    散列表是具有固定大小的数组，其中，表长应该为质数。散列函数是用于关键字与存储地址之间的一种映射关系，但是，不能保证每个元素的关键字与函数值是一一对应的，因为极有可能出现对应于不同的元素，却计算出相同的函数值，这就是哈希冲突。

1.1 常用散列函数的构建方法：

1.1.1 直接寻址法

    h(key) = key 或者 h(key) = a * key + b;

1.1.2 取模法

    h(key) = key mod p;

1.1.3 数字分析法

1.1.4 折叠法

1.1.5 平方取中法

1.1.6 保留余数法

    h(key) = key % p;

1.1.7 随机数法

    h(key) = random(key);

1.2 常用的解决冲突办法

1.2.1 开放地址法

    当发生地址冲突时，在散列表中再按照某种方法继续探测其他的存储地址，知道找到空闲的地址为止。

1.2.2 链地址法

1.2.3 再散列法

    当发生冲突时，使用第二个、第三个...散列函数计算地址，直到无冲突为止。时间消耗会增加。

1.2.4 建立一个公共溢出区

优缺点：

    Hash主要是用来进行“快速存取”，在O(1)时间复杂度里就可以查找到目标元素，或者判断其是否存在。Hash数据结构里的数据对外是杂乱无序的，因此其具体存储位置及各个存储元素位置之间的相互关系是无法得知的，但是却可以在常数时间里判断元素位置及存在与否。在处理海量数据的过程中，使用Hash方法一般可以快速存取、统计某些数据，将大量数据进行分类，例如提取某日访问网站次数最多的IP地址等。

2. Bit-map法

    bit-map(位图)法的基本原理是使用位数组来表示某些元素是否存在。

    bit-map法的结果是生成一个N位长的串，每位上以“1”或“0”表示需要的集合中的数。

例：对10亿个IPV4的IP地址进行排序，每个IP只会出现一次。

思路：可以通过简单的规则将10亿IP地址全部转换成32位的无符号整数，将这10亿整数排序后，然后再转回IP地址即可；更优的思路是申请长度为32位的bit类型的数组，然后将其对应到相应的位上，相比前一种方法，这个方法更节省空间。

4Byte * 10亿 = 40 0000 0000Byte = 40 0000 0000 / 1024 /1024 /1024 GB = 3.725G

上图计算得到的大小跟我算的不太一样？

2^32 bit = 4 294 967 296bit = 4 294 967 296bit / 8 /1024/1024 M = 512M

3. Bloom Filter法

以一个例子来说Bloom Filter（布隆过滤器）；

最差情况下使用hash表或者数据表存储，空间要求高：

64Byte*100亿 = 6400 0000 0000 /1024/1024/1024G = 596.046G

当遇到下面这几种情况，可以使用布隆过滤器：

布隆过滤器的特定：

对于上面题目的解决方案：

1. 建立一个bitarray数组，长度为m；

2. 有k个hash函数，输出域>=m，每个hash函数是优秀的且相互独立；

3. 对每个URL通过k个hash函数，计算求得k个hash值，对每个hash值对应到bitarray上，进行涂黑，如果已经是黑色，则保持不变；

判断某一个URL是不是黑名单里面的URL：

1. 将URL通过k个hash函数计算得到k个hash值；

2. 将k个hash值对应到bitarray数组中，如果对应的每个位都是黑色，则表示是黑名单URL；只要有一个位不是黑色，说明不是黑名单里面的URL；

当输入的URL过多，bitarray数组过小的时候，bitarray数组中大部分都被涂黑，很有可能会产生误判：因为这样会导致即使a不是黑名单里面的URL，也可能会出现对应的每个bitarray数组位上都被涂黑。

如何确定bitarray大小：

总结：

4. 数据库优化法

4.1 优秀的数据库管理工具

4.2 数据分区

4.3 索引

4.4 缓存机制

4.5 加大虚存

4.6 分批处理

4.7 使用临时表和中间表

4.8 优化查询语句

4.9 使用视图

4.10 使用存储过程

4.11 使用排序来取代非顺序存取

4.12 使用采样数据进行数据挖掘

5. 倒排索引

6. 外排序法

7. Trie树

8. 堆

9. 双层桶法

10. MapReduce法

Map-Reduce可以分为两个阶段：

1. Map阶段：把大任务分成若干个子任务（通过hash函数），然后将任务分配到某个节点上去处理；

2. Reduce阶段：子任务并发处理，然后合并结果；

Map-Reduce原理简单，工程上处理困难：

例：统计一片文章中每个单词出现的个数。

实例分析

常见海量处理题目解题关键

1.分而治之。通过哈希函数将大任务分流到机器，或分流成小文件。

2.常用的hashMap或bitmap。

难点：通讯、时间和空间的估算。

1. top K 问题（《Java程序员面试宝典》例题，在面试中与经常遇见）

    例如在搜索引擎中搜索最热门的10个搜索词；在歌曲库中下载最热门的前10首歌曲。

提示：可以结合Map-Reduce和Hadoop解决。

2.找个某个范围内漏掉的数字（某某跳动公司面试题）

    给定一个数组，数据的的范围是-2^32 ~ 2^32，现给定一个无序不重复数组，里面有几亿个数字，范围在给定的范围内，要求任意给出一个，数组中漏掉的数字（即这个数字不在数组中，但在-2^32 ~ 2^32）。同时对时间空间要求都比较苛刻，需要折中。

提示：二分法；最大最小值。

 2.1 这道题目是在牛客视频学习遇见，跟上面题目一样

    32位无符号整数的范围是0~4294967295.现在有一个正好包含40亿个无符号整数的文件，所以在整个范围中必然有没出现过的数。可以使用最多10M的内存，只用找到一个没出现过的数即可，该如何找？

分析：如果用哈希表来记录所有的数，最差情况下，将出现40亿个不同的数。每一条记录占有4字节，大约需要16G内存。

解法一：使用bitarray

解法二：分流

总结：

3.对10亿人的年龄进行排序

4.排序问题（《Java程序员面试宝典》例题）

5. 找出出现次数最多的数

    有一个包含20亿个全是32位整数的大文件，在其中找到出现次数最多的数。但是内存限制只有2G。

解法一：

解法二：

6. 找出每天最热的100词

    某搜索公司一天的用户搜索词汇是海量的，假设有百亿的数据量，请设计一种求出每天最热100词的可行方法。

7.在集群中实现缓存

    工程师常用服务器集群来设计和实现数据缓存，以下是常见的策略。

    01.无论是添加、删除还是查询数据，都先将数据id通过哈希函数转换成一个哈希值，记为key。

    02.如果目前机器有N台，则计算key%N的值，这个值就是该数据所属的机器编号，无论是添加、删除还是查询操作，都只在这台机器上进行。请分析这种缓存策略可能带来的问题，并提出改进的方案。

可能带来的问题：

解决方案：使用一致性哈希算法

    设定一个范围内的数据，然后收尾相连，形成一个环。根据机器id由hash函数计算得到机器在环上的位置。

    如何确定一条数据归属哪台机器：该数据的id用hash函数算出hash值，并映射到环中相应的位置，顺时针找到距离此位置最近的一台机器，那么这台机器就存放该数据。

   当添加节点应该怎么办：比如m3机器加入其中，则将data1中的数据复制到m3机器上，这样代价更小一点。

    当删除机器怎么办：只要将删除机器的数据全部复制到顺时针的下一台机器上即可。

部分理论参考《Java程序员面试宝典》，大多实例是我自己总结而来！

书籍分享：https://pan.baidu.com/s/1lh7xnfQvm9KaRC4P_3wyHg