Question

大数据问题

Answer 1

大数据问题，确切来说是很大数据量下的空间限制问题，解决方法有以下7种（图源左程云基础班）：

先思考用一个大的HashMap的情况。 key是某个整数，value是该整数出现的次数，这样可以统计词频，然后得出TOP10词频。计算此时使用的内存，4字节无符号整数范围是0到42亿多（如果是有符号整数范围是-21亿多到21亿多），范围是比40亿大的。最差情况下如果40亿个数都不同，此时HashMap使用的空间为40亿条记录，每条记录中key（无符号整数）是4字节，value（词频）也是4字节（int类型），总共8字节，总计320亿字节，即32G（10亿字节可估算为1G），哈希表爆掉了。

这里先补充一下哈希函数的特征：
特征1.输入域无穷大，输出域相对有限。
特征2.没有任何随机的成分，是确定规则的函数。输入相同那么输出一定相同；不同的输入可能会有相同输出（哈希碰撞）。
特征3. 输入哪怕很接近，最终的计算结果也很离散，和输入规律没有关系。这一点也是最关键的特征。
特征4.输出再模上一个数，取模的结果也是离散的

反推1G内存的HashMap可以有多少条记录，保守点1亿条，意味着该HashMap处理的包含数的种类（不是个数）不要超过1亿种，怎么处理？40亿个整数的大文件，每个数字用哈希函数处理完再取模100，只会是0到99。根据哈希函数特征3，不同输入会均匀分布到0到99上，40亿个数如果拥有的不同数的种类是K种的话，这样处理完后，每个小文件里几乎有100/k这么多种数，这样每个小文件里就不到1亿种了。再用HashMap一个一个文件去处理词频，搞出100个文件各自的TOP10，哈希函数相同输入则相同输出，所以不会出现一个数字落到不同文件里的情况。对文件的TOP10合并，就得到全局TOP10。

上面取模取40其实就可以了，40亿个数种类数K小于等于40亿，所以K/40小于等于1亿，符合上面要求的1G内存，但取的是100而不是40是为了更保险。

使用位图，用某个bit表示某个数出现过还是没出现过。如果是哈希表，表示一个数出现与否需要用一个键值对，键和值都占4字节，那么一条记录所占的空间就是64bit（8字节）。用位图的话，1bit表示1个数，数范围多大就用多少位bit；42亿多bit/8 = 5亿多byte = 500多M（10亿byte=1G）；在1G空间内拿下。

用两个bit位表示某个数字出现的频率。00表示出现0次；01表示出现1次；10表示出现2次；11表示出现3次，如果出现次数更多大于3次，11不变。这样最后统计下来就可以知道所有出现2次的数字，与原来相比就多了一倍空间，1G空间拿下。

位图不能用了，3KB空间太小了。先计算3KB能做多长的无符号数组，一个无符号数大小为4B，3KB/4B=750，然后750距离2的某次方哪个最近，512，那就申请一个长度为512的无符号整型数组arr（arr占用空间大小显然不超过3KB）。题目中数字范围是0到2的32次方减一（一共有2的32次方这么多个数），因为和512一样都是2的某次方，所以2的32次方一定可以均分成512份（每一份大小是8388608）；arr[0]表示512份里的第0份（范围0~8388607），表示这一份上的词频统计；而且因为一共只有40亿个数，那么arr[0]统计的数字一定不会溢出（40亿 < 2的32次方减一 = 42亿多，一无符号数是32位）；如果统计所有数出现的频率到对应范围的份上，一定有某一份词频不够83888608；假设不足的那一份是第a份，那么下次把3KB在第a份这个范围上再分512份，最终往下分，总能找到哪个数字没出现。

总体时间复杂度：以 512 为底的 2的32次方 的对数。这是个很小的数。且按行读文件占用内存是很少的，读文件并不是一次性把所有文件都load到内存里去，而是在硬盘文件里用偏移量找到某一行数据，读下一行的时候前一行的空间就可以被释放了；所以维持一个句柄句尾还有偏移量就可以按行读文件了。

整个范围是0到2的32次方减一。计算出中点Mid并统计0到Mid范围出现多少个数记为a，统计Mid+1到结尾范围出现多少数记为b个；a和b中一定有一个不满，不满的那个再二分，最终一定能定位到某个数字没出现，遍历次数以 2 为底 2的32次方 对数次，即32次

面对空间限制类题目，从范围数据状况入手，分区间统计的思想。

用哈希函数把URL分配到很多机器上去，每台机器上的文件再用哈希函数分成小文件，每个小文件分区间统计之后，找到重复的URL

利用堆、外排序来做多个处理单元的结果合并
通过1G内存分流文件，这1G用于存储哈希表。哈希函数特性是同样的URL会进到一个文件里去，文件大小为分流到1G可以统计下为止，从而把100亿个URL的大文件分流成小文件。哈希表的key是64字节（URL大小），value是long类型（因为是100亿个，无符号整数不够用）8字节。然后算1G内存最多可以放多少条这种记录，就可以知道小文件容忍的的不同的URL最多有多少条；从而反推出假设100亿个URL都是不同的，需要多少个小文件保证1G不超。

计算：64+8=72字节，哈希表内部可能有索引空间的占用，可以算的富裕一点，算作一条记录要100字节；1G=10亿字节，得出哈希表最多放1千万条记录，即记录1千万种不同的URL；最坏情况100亿个URL都不同，100亿/1千万得需要1千个小文件，那么原来的URL大文件用哈希函数算完再模上1千，分到对应的小文件里（根据哈希函数的性质，每个小文件里种类差不多是均分的，而且每个文件里记录数差不多1千万左右，不会超出多少）。然后在这1G空间里统计每个小文件里词频的TOP100，1千个文件有1千个TOP100，然后在每个文件里建立用词频作为排序的大根堆。

把每个堆的堆顶再组成一个大根堆，构成堆上堆，二维堆（即上图中的二叉树结构）；例如上图里包含甲、乙、丙；a、b、c；α、β、θ三个堆，现在堆顶元素甲、a、α构成大根堆

如上图所示，假如调整完发现α是最大的，那么α与a交换时是α这一串与a这一串交换，就输出了α作为整个词频中TOP1。

如上图所示，α输出后β顶上来，但β未必是全局最大值，所以堆顶元素组成的大根堆开始heapify；假如甲此时是全局最大值，那么甲这一串与β那一串交换......如此循环往复，每次堆上堆输出一个最大值，下面的元素顶上来，然后堆上堆再调整，整个串交换；二维堆每次输出一个，输出100次就是TOP100。
如果是遍历，时间代价O(100)；用堆结构可以加速到O(log100)。从这里可以看出外排每次决定一个东西是遍历一遍每个堆堆顶并比较大小。

假设给的空间限制为3KB，和前面一样分成512份且每一份都能统计下词频，第一份假设这些数出现a个，第二份假设这些数出现b个，第三份假设这些数出现c个，所有段的词频都有，然后把a、b、c……加起来，看在哪个范围上刚超20亿或刚好20亿，就把第20亿定位在这个范围上了。

举例假如第 i 份加完是19亿个，第 i + 1份加完是21亿个，那么20亿就在第 i + 1份上且是第 i + 1份上的第1亿个，接下来在第 i + 1份上再分512份去词频统计，看哪一份是刚超1亿或刚好到1亿，如此下去，总有统计出来的时候。