判断一个数是否在40亿个整数中。
1、我有40亿个整数，再给一个新的整数，我需要判断新的整数是否在40亿个整数中，怎么做呢？假设机器只有2G内存，但是需要尽可能快地得出答案，需要怎么做?
如果用一个set存储，新来的数判断是否在set中。
假设整数是32位的，set需要占的空间大约是16GB(一个整数4个字节，40亿个的话，应该是160亿个字节，大概是16GB)。需要的开销太大。如果分八次加载数据的话，占用的时间太长，不可取。
从磁盘加载数据是磁盘IO操作，是非常慢的，比内存中的操作要慢数百倍。每次都要加载这么大的数据，还要8次，找一个数的时间可以达到分钟甚至小时级。
可取做法一：
可以使用分布式算法，把数据分散在8台机器上，当再来一个新的数据时，8台机器一起找，最后的结果汇总出来就可以。这样时间应该可以达到秒级。
可取做法二：
32位int的范围是42亿，40亿整数中肯定有一些是连续的，可以先对数据进行一个外部排序，然后用一个初始的数和一个长度构成一个数据结构，来表示一段连续的数，举个例子:
如果数据是1、2、3、4、6、7……这种的，那么可以用(1, 4)和(6, 2)来表示。1后面连续4个数，6后面连续2个数。这样一来，所有连续的数都可以用两个数来表示，当有新数进来时候，再采用二分法进行判断。如此最差的情况就是2亿多的断点，也就是2亿多的结构体，每个结构体8个字节，大概16亿字节，1.6GB，这样内存中就可以放下！
正确做法：
判断一个数存不存在，其实只有两个状态，可以用一个位来代表。32位int的范围，总共就是2的32次方，大概42亿多点。所以可以申请2的32次方个位。
把整个整数范围都覆盖，1代表第一个位，2代表第二个位，2的32次方代表最后一个位。40亿个数中，如果它存在相应的位置，就是1，不存在就是0。
新来一个数就去找相应的位，比如来了一个1234，就找一下第1234位，如果是1就存在，是0就不存在。2的32次方个位，相当于2的29次方个字节，大概500MB。因为原来32位的整数，转化成了1位的布尔，所以数据空间就是原来的32分之一。这就是bitmap算法(位图法)！用位来表示状态，可以节省空间。
