Java实现，给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？
Java
知行合一1的其他提问
类似问题
一道笔试题--求二进制数1的个数
335 阅读
java 位运算问题
288 阅读
输出一个数的质因数，java新手虚心求教
490 阅读
昨天京东面试，谈的时候问的几个问题
17037 阅读
Notification小例子
711 阅读
10亿个数，从其中找出相同的两个数
124 阅读
（求大神）指定范围的伪随机数！
175 阅读
新鲜出炉，2019最新大厂面试题总汇
0 阅读
乐观锁的实现，避免多线程丢失更新
3021 阅读
java 对 jar内的某个txt文件进行读 写
3403 阅读
总结一下自己关于学习java集合的一些知识
766 阅读
JAVA内存的“防水补漏”解决方案
829 阅读
一个计算Java问题，求解
351 阅读
java 私塾第六、七章笔记整理
105 阅读
方案1：oo，申请512M的内存，一个bit位代表一个unsigned int值。读入40亿个数，设置相应的bit位，读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。
dizengrong：
方案2：这个问题在《编程珠玑》里有很好的描述，大家可以参考下面的思路，探讨一下：
又因为2^32为40亿多，所以给定一个数可能在，也可能不在其中；
这里我们把40亿个数中的每一个用32位的二进制来表示
假设这40亿个数开始放在一个文件中。
然后将这40亿个数分成两类:
1.最高位为0
2.最高位为1
并将这两类分别写入到两个文件中，其中一个文件中数的个数<=20亿，而另一个>=20亿（这相当于折半了）；
与要查找的数的最高位比较并接着进入相应的文件再查找
再然后把这个文件为又分成两类:
1.次最高位为0
2.次最高位为1
并将这两类分别写入到两个文件中，其中一个文件中数的个数<=10亿，而另一个>=10亿（这相当于折半了）；
与要查找的数的次最高位比较并接着进入相应的文件再查找。
…….
以此类推，就可以找到了,而且时间复杂度为O(logn)，方案2完。
如果是以"4,3,1,2,"的形式存储在文件num.txt,直接grep即可:
php > echo (shell_exec('grep "3," ./num.txt')) ? '存在' : '不存在';
存在
如果从算法层面考虑，布隆过滤器，有一定的误报率，调整的好，可以做到极低，40亿的数据也就会出现一两个误报。商数过滤器，新一代精确的过滤器，不会有错误率问题，但空间要求比前者大多了。如果数据重复率高，hash也能搞定这个问题；如果要求不高，从系统层面解决，用ElasticSearch或者solor，优化的好，可以达到亚毫秒级
引用来自“呼啦_小呆”的评论
方案1：oo，申请512M的内存，一个bit位代表一个unsigned int值。读入40亿个数，设置相应的bit位，读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。
dizengrong：
方案2：这个问题在《编程珠玑》里有很好的描述，大家可以参考下面的思路，探讨一下：
又因为2^32为40亿多，所以给定一个数可能在，也可能不在其中；
这里我们把40亿个数中的每一个用32位的二进制来表示
假设这40亿个数开始放在一个文件中。
然后将这40亿个数分成两类:
1.最高位为0
2.最高位为1
并将这两类分别写入到两个文件中，其中一个文件中数的个数<=20亿，而另一个>=20亿（这相当于折半了）；
与要查找的数的最高位比较并接着进入相应的文件再查找
再然后把这个文件为又分成两类:
1.次最高位为0
2.次最高位为1
并将这两类分别写入到两个文件中，其中一个文件中数的个数<=10亿，而另一个>=10亿（这相当于折半了）；
与要查找的数的次最高位比较并接着进入相应的文件再查找。
…….
以此类推，就可以找到了,而且时间复杂度为O(logn)，方案2完。
这个方案1是可行的.
但有一个要求就是这40亿个数中每个数都要在2^64以内.
这样才好标记每个数所在的位置.判断 一个新的数时才能o(1)判断出来.
方案2无非就是一个二分法,在40亿这么大的数据中,性能是低效的,不建议.
1.如果内存充足，可以一次放到Set中，时间复杂O(1);不知道你尝试过没
2.int 最大值2^32 = 4294967296 减去 4000000000 = 294967296 如果内存不够可以尝试找出不在40亿内的2900多万放到Set中，反向判断。
没有专门去读这方面的资料，不行就当我随口瞎掰。。