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

题目

给40亿个不重复的 unsigned int 的整数，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？

分析

40亿个int型的整数，大约需要16G，很显然内存放不下，可以考虑一下位图法，用一个bit为来表示一个数是否存在，0表示不存在，1表示存在，40亿个字节型的数据大约需要4G，一个字节有8比特，如果用一个比特位表示一个数，大约需要512M，所以是可行的。

代码实现

class BitMap{ private long length; private int[] arr; /** * template[0]表示第1个二进制数存在 * template[1]表示第2个二进制数存在，以此类推 * * template[0] = 00000000 00000000 00000000 00000001 * template[1] = 00000000 00000000 00000000 00000010 * template[2] = 00000000 00000000 00000000 00000100 * ... * template[31] = 10000000 00000000 00000000 00000000 */ private int[] template=new int[32]; public BitMap(long length){ this.length=length; init(); } private void init(){ //判断一共需要多少个桶 arr=new int[(length>>>5)+(length&31)==0?0:1]; } public void setBit(long number){ //得到number在哪个桶中 int nthBuckct=(int)number>>>5; //每个桶有32个位置，得到在桶中的偏移量 int offsect=(int)number&31; //将该位置置为1 arr[nthBuckct]|=template[offsect]; } public boolean contains(long number){ //得到number在哪个桶中 int nthBuckct=(int)number>>>5; //每个桶有32个位置，得到在桶中的偏移量 int offsect=(int)number&31; //如果该位置不为0，则已经存在，不能用是否等于0来判断是否存在 return (arr[nthBuckct]&template[offsect])>0; } }