如何判断一个数是否在40亿个整数中

需求描述

有40亿个整数，再给一个新的整数，需要判断新的整数是否在40亿个整数中，你会怎么做？

解决方案

• 不假思索的解决方案–40亿个数放在Set当中，然后看是否存在

思考：整数32位，这个存储整数的Set需要多大？

一个整数4个字节，40亿个整数160亿字节，将近16G的内存

问题是，如果我只有2G的内存，该怎么办呢？

分8次加载？那样的话会很慢的，从磁盘加载数据是磁盘io操作，是非常慢的，每次都要加载这么大的数据，还要8次，估计找一个数的时间可以达到分钟甚至小时级了。

• 稍好一点的解决方案，分批放在8台机器上，按分布式的思路解决这个问题

8台机器分别计算，最终汇总结果，一次性读入数据，查找很快。

这样做的话，因为每台机器都可以一次性把数据读入内存，在比较的时候不用来回加载数据了，所以可以节省加载数据的开销。

• 毫秒级的解决方案–bitmap

32位int的范围，总共就是2的32次方，大概42亿多点。所以可以申请2的32次方个位。把整个整数范围都覆盖了。

1代表第一个位，2代表第二个位，2的32次方代表最后一个位。40亿个数中，存在的数就在相应的位置1，其他位就是0。

比如来了一个新的数1234，就找一下第1234位，如果是1就存在，是0就不存在。

这样的话，需要多大内存呢？

2的32次方个位，相当于2的29次方个字节，500多MB，节省了不少内存。

• 另外一张优秀的解决方案–自创数据结构存储

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

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

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

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