资源限制类题目七大技巧 解决所有大数据资源限制类问题

有一个无符号整数的文件，数据个数有40亿个，如何通过1G的内存返回出现次数最多的数

1. 对每个数调用哈希函数得到哈希值，将哈希值模上100，进行小文件分类（相同的数一定在同一文件）

2. 将每个小文件内出现次数最大的数进行比较即可

布隆过滤器

目前有100亿个URL，需要通过黑名单来禁止访问（每个URL 64Byte），只需要添查操作。

使用布隆过滤器可以在很少空间内实现，但存在一定的失误率（不可避免），错将不在黑名单的URL认为在黑名单内。—— 宁错杀不放过

1. 使用整形数组来进行bitmap表示

2. 建立一个长度为m的bitmap，实际占用空间m/8 Byte

3. 添加黑名单：将URL通过哈希函数得到输出值%m，将该位设为1，再通过另一个哈希函数，同样处理，一共使用k个哈希函数

4. 查找时，通过同样的k个哈希函数，只有全是1时，判断该URL在黑名单内，有一个不是1，那么该URL不在黑名单内

提高m，会降低失误率，但随着m的逐渐增大，失误率的降低越来越慢。k与失误率的关系为一个对勾函数。

n(样本量)，p(失误率)

单样本的大小和布隆过滤器无关。

m=(n*lnp)/(ln2)^2

k=ln2*m/n=0.7*m/n

p=(1-e(-n*k/m))^k

两个参数都向上取整即可
 

哈希一致性

用于讨论数据服务器组织的问题，降低数据迁移的成本。

将哈希值的返回域想象成环，假设有三台机器，m1,m2,m3。

添加的时候只需要，将某个输入对应的哈希值，顺时针放到最近的服务器内即可

增加服务器：将m4与其逆时针最近服务器中间的数给到m4即可

删除服务器：数据全部给到顺时针最近的服务器内

存在的问题：

        1. 机器数量少时做不到分布均衡

        2. 增加或删除机器时会导致负载不均衡

使用虚拟节点解决：m1有一千个代表点，m2有一千个代表点，m3有一千个代表点，使用代表点来进行抢环。
 

位图解决某一范围上数字出现，节省大量空间

使用一个整形数组，来表示所有范围内的数是否出现。

可以使用哈希函数分流进行实现，同样使用位图来实现，但1/0只能表示数字是否出现过，所以需要使用两个位来表示一个数字出现的信息。

利用分段统计思想，节省空间

 假设3KB，申请长度512的整形数组，将题目中的这个范围分为512份，则每一份都是等量的（8388608）。每一个数组表示该范围内的数出现了多少次，统计范围内词频，一定会有一个数小于8388608，在该范围上继续分，循环往复下去。

利用范围统计的思想， 申请一个无符号整型数组做词频统计，然后从左到右对整型数组求词频和，第一次超过20亿时，最近加入的数组里一定包含所要求的中位数，周而复始即可。

利用堆、外排序来做多个处理单元的结果合并

10G文件，每个文件是一个无符号整数，使用5G内存，使其文件输出有序：

使用小根堆，小根堆里的数据是一个结构体，结构体包括数字及其出现的次数，小根堆根据数值组织，则5G内存肯定能支持一个2^28（N）条数据的小根堆，将整数的数值范围除N，等分为M个范围，首先对第一个范围的数排序，输出，依次下去即可。