算法通关村——海量数据场景下的热门算法题的处理方法

1. 从40个亿中产生一个不存在的整数

题目要求：给定一个输入文件，包含40亿个非负整数，请设计一个算法，产生一个不存在该文件中的整数，假设你有1GB的内存来完成这项任务。
● 进阶：如果只有10MB的内存可用，该怎么办？

1.1 哈希存储

最坏的情况是里面数据都存在，那么这个哈希表的记录数就是40亿，而一个整数占4个字节，也就是说哈希表记录数占据160亿个字节，大概是16G，很显然是超过了1GB，这种方法就不需要考虑了。但是如果转换成比特存储，1个字节等于8比特，空间就小了很多。

1.2 位图（bitmap）存储

但是如果使用位存储，需要申请一个长度为 4294967295 的 bit 类型的数组 bitArr（就是boolean类型），8 个bit 为1B，所以长度为 4 294 967 295 的 bit 类型的数组占用 500MB 空间，bitArr 上的每个位置只可以表示 0 或1 状态。只要存在这个数据那么就将这个数据状态设置为1，表示重复了，最后只需要找到元素下标为0的数，就是不存在的数，最好的情况就是只有极个别的数据不存在或者没有数据不存在，查找的速度也就提升了。

1.3 10MB存储

上面bitmap里面需要500MB空间，而这里只给10MB，意味着至少需要50块空间，而一般是使用2的倍数进行分块，所以这里可以使用64块来存储。

每一块里面的数据大小都是67 108 864个，只要遍历一次，就能统计每个区间内的元素个数，里面肯定有一个小于67 108 864，然后再bitmap映射，找到不存在的那个数。

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

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

2.1 哈希存储

一般统计个数使用哈希比较多，词频统计，每一个key都对应一个整数，假设没有重复的数，key的大小就是4b，value的大小也是4b，那么一条记录占用8b，20亿占用16G，超过了题目要求。

2.2 分块

2亿条记录是占用1.6G，我只需要将这个20亿数据分割10块，就能保证每一块的数据内存不会超过2G，接下来就是分别统计每一块里面出现最多的元素，将所有的块的次数进行比较找出最多的一条数据。

3. 从100 亿个 URL中查找的问题

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

这一题的思路根据前面几个题目相比也是很明显，依然是采用哈希存储，然后将这个大的哈希分成若干个小的文件，分别统计每一块里面的元素出现的个数。但是这里需要明确一下这个空间占用是多少，才能进行相应的分片。