资源限制技巧汇总
1）布隆过滤器用于集合的建立与查询，并可以节省大量空间。
2）一致性哈希解决数据服务器的负载管理问题。
3）利用并查集结构做岛问题的并行计算。
4）哈希函数可以把数据按照种类均匀分流。
5）位图解决某一范围上数字的出现情况，并可以节省大量空间。
6）利用分段统计思想、并进一步节省大量空间。
7）利用堆、外排序来做多个处理单元的结果合并。
32位无符号整数的范围是0~4,294,967,295，现在有一个正好包含40亿个无符号整数的文件，可以使用最多1GB的内存，怎么找到出现次数最多的数？
- 利用哈希函数的特性，可以把数据按照种类分类来做。分流后用hashmap来统计记录数。我们来估算一下1G内存大概容纳多大的哈希表，key和value都是int类型一共占用八个字节，假设40亿数据都是不重复的那么我们需要大概8*40=320亿字节的空间，而10亿字节大概等于1G的大小，理论上我们需要的内存空间是32g,而现在内存却只有1G这样的方法是行不通的。我们可以用40台机器来分流，利用hash函数每个文件中的数据都算出一个哈希值，然后对40取模，数字必去向其中一台机器，由于哈希函数具有离散型，不同种类的数字一定会均匀分布在这四十个文件中，且相同的数字一定会去到相同文件中，我们在对每个文件进行统计，现在一个小文件就算全部不同也就是需要1G大小的空间，是可以统计的下的，记录此时这个文件中最多的数字，同样的方法计算其余九个文件汇总最多的数字，最后在十个数字再进行比较，就可以得出文件中出现次数最多的数字。（我认为核心点在于 种类均匀分布在每个文件中致使内存不会因为种类过多而爆掉，还有就是每一种数字只会出现在一个文件，便于统计个数，利用了技巧的第4点）。
32位无符号整数的范围是0~4,294,967,295，现在有一个正好包含40亿个无符号整数的文件，所以在整个范围中必然存在没出现过的数。可以使用最多1GB的内存，怎么找到所有未出现过的数？
【进阶】
内存限制为 10MB，但是只用找到一个没出现过的数即可。
用有限变量，找到一个没有出现过的数。
- 利用位数组来解。首先需要一个长度为2^32-1的维数组大概等于 500多兆是完全符合题意中的1G内存的，此时我们利用小标作为数字，统计每个数字的词频。最后只需要统计词频为0的下标就是没有出现过的数。
- 进阶：内存只有是10MB，位数组的方法已经行不通了，我们看10兆能申请多大的整形数组，一个整形占4字节，10兆大概等于2621440整数，也就是大小这么大的数组，我们不申请这么大的数组，而是申请一个 2^n<=2621440 这个输的空间大小，然后认为的把0~4,294,967,295 分成2^n分，每个数元素只统计对应区间的此数字词频个数，如果最后某一个区间的词频个数小于这个区间实际应该有的个数，没有出现过的数字一定在这个区间中，那么我们在对这个区间进行上述操作，直到最后能通过给定内存大小用比特位统计的时候结束。
- 进阶2：在0~4,294,967,295上二分取mid 值，统计04,294,967,295范围上，大于mid的个数，小于等于mid的个数，如果哪一边的个数大于了04,294,967,295范围的一半，那么在小于的一边一定有没有出现过得数，继续这样二分，最后一定找到一个没有出现过的数。
有一个包含100亿个URL的大文件，假设每个URL占用64B，请找出其中所有重复的URL。
【补充】
某搜索公司一天的用户搜索词汇是海量的(百亿数据量)，请设计一种求出每天热门Top100词汇的可行办法。
- 解法一，如果允许有失误率，那么可用布隆过滤器。
- 解法二，不允许有失误率。
询问清楚可以给多少台机器，加入1000，利用哈希函数，可以均匀的吧种类分不到1000台机器上，减少种类，我们不怕一台机器上的相同种类很多。每台机器上再用哈希函数2，在细分成小文件，直到可以利用现有资源处理为止，然后在汇总求答案。 - 补充：大流程也是通过哈希函数分到不同的机器上，然后份文件，直到能利用当前资源处理，然后汇总。相同机器小文件可以用外排，各个小文件的顶部进行PK，每次选一个最大。也可以用二维堆，每个小文件组织成大根堆，每个小文件顶部的元素在组织成大根堆，每次弹出堆顶元素，每个小根堆在做调整，然后堆顶组织成的大根堆在调整，继续弹出，重复上面的过程，知道收集到100个元素为止。
32位无符号整数的范围是0~4294967295，
现在有40亿个无符号整数，可以使用最多1GB的内存，找出所有出现了两次的数。
- 位数组求解，申请一个大小为2^33-1大小的位数组，内存大小大约为1G，用过位数组中的两位代表出现次数，列入 第一位第二位代表第一个数字，如果出现零次就是00，出现一次就是01，出现两次机以上就是11，最后统计所有01的个数就知道出现两次的数量了 。
32位无符号整数的范围是0~4294967295，现在有40亿个无符号整数
可以使用最多10MB的内存，怎么找到这40亿个整数的中位数？
- 申请一个整形数组，10M空间，那么数组的大小大概是10 * 1024*1024/4,数组中每一位记录一段的词频统计，加入求40亿的中位数就是求第二十亿大的数，那么我们通过数组的词频可以缩小范围，第二十亿小具体在哪个元素中，然后在这个范围继续划分，直到可用内存可以统计中位数为止。
32位无符号整数的范围是0~4294967295，
有一个10G大小的文件，每一行都装着这种类型的数字，整个文件是无序的，给你5G的内存空间，请你输出一个10大小的文件，就是原文件所有数字排序的结果。
维护一个5G大小的小根堆，在维护一张map表，记录某个数金没有进入过小根堆，key是这个数 value 是词频，如果进入小根堆的元素没有堆顶的元素大就不进如小根堆（其实小根堆放着全部数据的前k大，并且还有出现的次数），每一轮都会排好一部分数据，当这一轮结束时用一个临时变量记录下此时堆中最小的数字，下一轮大于等于临时变量这个数的都不允许进小根堆，重复以上过程直到排好序。
