大数据和空间限制

布隆过滤器

网页黑名单系统、垃圾邮件过滤系统、爬虫网址判重系统，且系统容忍一定程度的失误率，但是对空间要求比较严格，这种问题一般考虑布隆过滤器。布隆过滤器想做到完全正确是不可能的，其优势在于使用很少的空间可以将准确度做到很高的程度。

哈希函数（散列函数）：输入域可以是非常大的范围，但是输出域是固定的范围。性质如下：1.无限输入域；2.传入相同输入值时，返回值一样；3.传入不同输入值时，返回值可能一样也可能不一样。4.返回值均匀分布

第四点性质是评价哈希函数优劣的关键，不同的输入值所得到的返回值均匀地分布在输出域上，哈希函数就越优秀，并且这种均匀分布与输入值出现的规律无关。

布隆过滤器：一个长为m的bit数组，每个位置只占一个bit，假设一共有k个哈希函数，这些函数的输出域都大于等于m。对一个输入对象，经过k个哈希函数算出结果，每个结果对m取余，然后在bit array上把相应的位置涂黑。检查一个对象是否是之前的某一个输入对象，就检查相应位置是否是黑的，如果有一个不是黑的，则该输入一定不在集合里。如果都是黑的，说明在集合中，但是可能误判。如果bit map的大小m相比输入对象的个数n过小，失误率会变大。假设输入个数为n，失误率为p，则bit map的大小由以下公式确定：

$m= -\frac{n lnp}{(ln2)^2}$

哈希函数的个数由以下公式决定：

$k = ln2 \frac{m}{n}$

因为在确定布隆过滤器大小的过程中选择了上下取整，所以还要用如下公式确定布隆过滤器真实失误率：

$(1-e^{-\frac{nk}{m}})^k$

只用20GB内存在20亿个整数中找到出现次数最多的数

【题目】有一个包含 20亿个全是32位整数的大文件，在其中找到出现次数最多的数

【要求】内存限制为2GB

【解答】想要在很多整数中找到出现次数最多的数，通常的做法是使用哈希表对出现的每一个数做词频统计。但是一次性用哈希表统计20亿个数的办法很可能导致内存不够。解决办法是把包含20亿个数的大文件用哈希函数分成16个小文件，根据哈希函数的性质，同一种数不可能被散列到不同的小文件上，同时每个小文件中不同的数一定不回大于2亿种。对每一个小文件用哈希表来统计其中每种数出现的次数，就得到了16个小文件种各自出现次数最多的数，还有各自的次数统计，接下来比较他们就好了。

把一个大的集合通过哈希函数分配到多台机器中，或者分配到多个文件里，这种技巧是处理大数据面试题最常用的技巧之一。

40亿个非负整数中找到未出现的数

【题目】32位无符号整数的范围是0~4294967295，现在有一个正好包含40亿个无符号整数的文件，可以使用最多1GB的内存，找出所有未出现过的数。

【解答】如果用哈希表的话需要占用很多空间，所以申请一个长度为4294976295的bitarray，遍历这40亿个数，把对应位置涂黑，然后再遍历bitarr，哪个位置不是黑的就没出现

【进阶】内存限制为10MB，但是只用找到一个没出现过的数即可

【解答】先将0~4294967295分为64个区间，遍历一次分别统计每个区间内的个数，找到某个区间个数少于67108864，这个区间一定有没出现过的数，再遍历一次，利用长度为67108864的bit arr，这占用大约8MB的空间，然后按照上面的方法即可。

找到100亿个URL中重复的URL及搜索词汇的top K问题

【题目】有一个包含100亿个URL的大文件，假设每个URL占用64B，请找出其中所有重复的URL。

【解答】把大文件通过哈希函数分配到机器，或者通过哈希函数把大文件拆成小文件，一直进行这种划分，直到划分的结果满足资源限制的要求。

【补充问题】某搜索公司一天的用户搜索词汇是海量的（百亿数据量），请设计一种求出每天热门top100词汇的可行办法

【解答】还是用哈希分流的思路来处理，把包含百亿数据量的词汇文件分流到不同的机器上，处理每一个小文件的时候，通过哈希表统计每种词及其词频，哈希表记录建立完成后，再遍历哈希表，遍历哈希表的过程中使用大小为100的小根堆来选出每一个小文件的top100，然后把各个维简排序后的top100进行外排序或者继续利用小根堆，就可以选出每台机器上的top100，然后继续。。。

40亿个非负整数中找到出现两次的数和所有数的中位数

【题目】32位无符号整数的范围是0~4294967295，现在有40亿个无符号整数，可以使用最多1GB的内存，找出所有出现了两次的数。

【解答】用bitarr的方式来表示数出现的情况，即申请一个长度为4294967295*2的数组，用两个位置表示一个数出现的词频，第一次设为01，第二次设为10，第三次及以上设为11，然后统计10的个数

【补充问题】可以使用最多10MB的内存，怎么找到这40亿个整数的中位数

【解答】用分区间的方式处理，长度为2M的无符号整型数组占用的空间为8MB，向上取整2148个区间，累加每个区间的出现次数，就可以找到40亿个数的中位数到底落在哪个区间上

一致性哈希算法的基本原理

如果用服务器集群来设计和实现数据缓存时，一种方法是，先将id通过哈希函数转换成一个哈希值，记为key，如果机器有N台，则计算key%N的值，这个值就是该数据所属的机器编号。这种方法的潜在问题是如果增删机器，即N变化，代价会很高，所有数据都不得不根据id重新计算一遍哈希值，将哈希值对新的机器数进行取模操作，然后进行大规模的数据迁移。

为了解决这一为题，引入一致性哈希算法。数据id通过哈希函数转换成的哈希值头尾相连，想像成一个闭合的环形，一个数据id在计算出哈希值后认为对应到环中的一个位置。然后将每台机器根据机器id算出来的哈希值确定机器在环中的位置。如何确定一条数据归属哪条机器？把数据id用哈希函数算出哈希值，映射到环中相应的位置，顺时针找到离这个位置最近的机器，那台机器就是数据的归属。这样增删机器时的代价就较小。

为解决机器负载不均的问题，引入虚拟节点机制，即对每一台机器通过不同的哈希函数计算出多个哈希值，对多个位置都放置一个服务节点，称为虚拟节点。具体做法可以在机器ip地址或主机名的后面增加编号或端口号来实现。