===

Index

• 备忘
• 如何判断一个数是否在40亿个无重复整数中？
• 布隆过滤器
• 用2g内存找到20亿整数中出现次数最多的数
• 40亿个非负整数中找到没出现的数
• 100亿个URL中重复的URL及搜索词汇的topk问题
• 40亿个非负整数中找出现两次的数或所有数的中位数

备忘

• 1 GB: 十亿个字节（Byte）

  1(B) * 10*10^8 / 1024 / 1024 ≈ 953.67(MB) ≈ 1000(MB) ≈ 1(GB)

• 400 MB: 一亿个 4 字节（Byte） int 整型占用的内存

  4(B) * 10^8 / 1024 / 1024 ≈ 381.57(MB) ≈ 382(MB) ≈ 400(MB)

  • 10 亿个整型 -> 400(MB) * 10 = 4(GB)
  • 40 亿个整型 -> 4(GB) * 4 = 16(GB)
• 12 MB: 一亿个比特（bit）占用的内存（相比于 int 型，节省了 32 倍内存）

  1(b) * 10^8 / 8 / 1024 / 1024 ≈ 11.92(MB) ≈ 12(MB)

  • 10 亿个比特 -> 12(MB) * 10 = 120(MB) ≈ 4(GB)/32 = 128(MB)
  • 40 亿个整型 -> 120(MB) * 4 = 480(MB) ≈ 16(GB)/32 = 500(MB)

如何判断一个无符号数是否在40亿个整数中？

40亿个整数，占用160亿个字节，大约 16GB 内存。

1. 内存有2G，且有一批机器（>=8），怎么做？

使用分布式算法，把数据分散到8台机器上，每台2GB，每当来一个新数据，8台机器一起找，再汇总结果。

2.使用bitmap

每一个数对应一个二进制位，新的数转换为一个位，判断这一位是0还是1即可。

32位无符号整型范围为2的32次方，约42亿多点， 可以申请2的32次方个位，来一个新的数，比如1234，就去找第1234位是0还是1.

将一个31位int转换为32位bit，空间是原来1/32，大约 500MB。

3. 外部排序+二分

32位int的范围是42亿，40亿整数中肯定有一些是连续的，我们可以先对数据进行一个外部排序，然后用一个初始的数和一个长度构成一个数据结构，来表示一段连续的数，举个例子。

如果数据是1 2 3 4 6 7…… 这种的， 那么可以用(1,4)和(6,2)来表示，这样一来，连续的数都变成了2个数表示。

1, 2, 3, 4, 6, 7
----------  ----
(1, 4)      (6, 2)

来了一个新数之后，就用二分法进行查找了。

这样一来，最差情况就是2亿多的断点，也就是2亿多的结构体，每个结构体8个字节，大概16亿字节，1.6GB，在内存中可以放下。

布隆过滤器

题目描述：不安全网页黑名单包含100亿个黑名单网页，每个网页URL最多战64B，实现一种网页过滤系统，可以根据网页URL判断网页是否在黑名单上。

要求

• 允许有万分之一以下的判断失误率
• 使用的额外空间不超过30GB

思考 如果把黑名单中的URL用数据库或哈希表存储：每个URL 64B， 100亿个至少要640GB空间

哈希函数性质

• 典型的哈希函数具有无限输入值域
• 哈希函数输入值相同时，输出值也相同
• 哈希函数输入值不同时,输出值可能相同，也可能不同
• 很多不同的输入值所得到的输出值会均匀分布在哈希函数的值域上

一些经典的哈希函数实现：MD5, SHA1

布隆过滤器

假设有一个长为 m 的bit类型数组，每一位有0和1两种状态 假设有k个哈希函数，函数的输出值域S都大于等于m。对算出来的每一个结果对m取余(%m)，然后我在bitmap上把相应位设置为1。

检查阶段： 假设一个对象为a，要判断它是否是之前输入对象，就把a通过k个哈希函数算出k个值，对k个值对m取余，得到 [0, m-1]范围内的k个值，看这k个值在bitmap上是否都为1。

• 如果有一个不是1，则说明a一定不在这个集合中。
• 如果全部都是1，则说明a在这个集合中，但可能有误判。

根据输入数据规模n和失误率p，确定m和哈希函数个数k

布隆过滤器的大小m由以下公式确定：

       n * ln(p)
   m = ——————————
        (ln2)^2

当n等于100亿，p=0.01%时，m = 19.19n，向上取整为20n，即需要2000亿个bit，也就是25GB。 哈希函数个数由以下公式确定：

k = ln(2) * （m / n） = 0.7 * (m / n)          

哈希函数个数为k=14个。

然后用25GB的bitmap，再单独实现14个哈希函数，生成布隆过滤器即可。

用2g内存找到20亿整数中出现次数最多的数

分析： 通常做法是建立一个哈希表。key是某个数，value是出现次数，出现次数最多20亿，在int范围内。
如果20亿个数都不相同，哈希表中会有20亿条记录，每条记录占8B(key,value),需要内存为16GB。

方法

把包含20亿个数的大文件用哈希函数分成16个小文件，假设哈希函数足够好，每个小文件中不同的数不会大于2亿种，然后对每一个小文件用哈希表分别统计每个数出现次数，最后选出16个小文件中各自的第一名谁出现次数最多即可。

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

32位无符号整型范围是 0 ~ 4294967295, 现有一个包含40亿非负整数的文件，所以必然存在没出现的数，最多使用1G内存。

进阶：内存限制位10MB，只用找到一个没出现的数即可。

分析： 用哈希表存储需要16GB空间，不满足要求。

bitmap

可以申请2的32次方个位的bitmap，遍历40亿个数，遇到4000，就把bitArr[4000]设为1. 第二次遍历，bitArr中为0的数即是未出现的数，需要空间为 16GB/32 = 500MB。

进阶问题:
10MB内存，首先将0 ~ 4294967295范围平均分成64个区间，每个区间 2^26 个数

统计落在每个区间的数有多少，肯定有区间计数少于 2^26，可以找出未出现的数。

第一次遍历时：申请长度为64的数组，countArr，countArr[i],用于统计区间i上的数有多少，遍历40亿个数，根据当前数是多少决定哪一个区间上的计数增加。 例如，当前数为3422552090， 3422552090/67108864 = 51， 则 countArr[51]++。

遍历完成，至少会找到一个区间计数小于2^26，对找到的区间x，进行第二次遍历：

• 申请长度为 2^26 的bitmap，占用约 8MB 内存。
• 再遍历一遍40亿个数，只关注落在该区间的数
• 将num在该区间的偏移量设置为1，也就是只在该区间的bitmap上做映射。
• 在bitmap上找到没有设为1的位置，则 2^26 * x + i就是第一个没出现的数

100亿个url中重复的url及搜索词汇的topk问题

有一个包含100亿个URL的大文件，每个URL 64B，找出其中重复的URL。

补充： 在百亿搜索词汇量中，求出最热top 100词汇的方法。

思路：分而治之，将100亿大文件通过哈希函数分配到100台机器上或者在单机上拆分成1000个小文件

**补充问题：分而治之，处理每一个小文件时，哈希表统计每种词及其词频，再次遍历哈希表时，用一个大小为100的堆实时维护top100词频的词汇，对于每个哈希表的top100堆再进行合并（或者外排序），最终求出百亿数据量的top100.

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

32位无符号整型范围是 0 ~ 4294967295, 现有40亿个无符号整数，找出所有出现两次的数，最多使用1G内存。

补充问题：

最多使用10MB内存，怎么找到40亿个整数的中位数。

原问题：

bitmap，申请 4294967295 * 2 的bit类型数组bitArr，占用空间为1GB。遍历40亿个无符号数，第一个遇到num, 将bitArr[num2+1]和bitArr[num2]设置为01,第二次遇到设置为10，第三次遇到设置为11，以后再遇到，如果已经是11，就不再进行设置。 再次遍历，bitArr[num2+1]和bitArr[num2]设置为10的数是出现两次的数。

求中位数：

分区间处理，长度为2MB的无符号整型数组占用空间为8MB，所以将区间数量定为： 4294967295/2M 向上取整为2148个区间，第0 区间为0-2M-1, 第i区间为 2M * i ~ 2M * (i+1)-1 ....

申请长度为2148的无符号整型数组arr[0…2147]，arr[i]表示第 i个区间有多少个数,遍历并统计。

累加每个区间的出现次数，找到第20亿个数落在哪个区间， 比如0-K-1 区间个数和为19.998亿，加上第k个后就超过20亿，则第20个数是第K个区间上的第0.002亿个数。

接下来申请长度为2MB的无符号整型数组arr[0, 2M-1]，占用8MB，遍历40亿个数，对第K个区间上的num统计频率，找到第0.002亿个数。