先提一个问题，怎么在40亿个整数中找到那个唯一重复的数字?
第一想法就是Set的不可重复性，依次把每个数字放入HashSet中，当放不去进去的时候说明这就是重复的数字，输出这个数字。
if(hs.contains(x))
System.out.println("重复的数字是"+x);
else{
hs.add(x);
}
但是，
HashSet里contains()：
public boolean contains(Object o) {
return map.containsKey(o);
}
HashMap里containsKey()：
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
HashMap里getEntry():
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
} int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
但是怎么说呢，contains()方法消耗的时间，消耗的空间很大，毕竟有约40亿的数据，所以觉得HashSet是不可取的。
然后百度了，发现了BitSet这个神奇的东西。
源代码就不贴了，简述下为什么用BitSet能行。
BitSet就是位图，它的值只有1和0。内部是基于long[]实现的，long是8字节（64位），所以Bitset最小是64位，每次扩大一次扩大64位，即内部大小是64的倍数。每次BitSet新增加一个数字时，就将该位置为1。
也就是说BitSet并不直接存储每个数据，而是存储数字是否存在过（1表示存在，0表示不存在）。
|---------------|-----------|-------------|-------------|----------|
|
| 数字范围 [0,63] [64,127] [128,191] ......... |
|---------------|-----------|-------------|-------------|----------|
|
| long数组索引 0 1 2 ........ |
|---------------|-----------|-------------|-------------|----------|
若添加一个数字 10 ，那么将long[0]的二进制位中从左往右第十个数置为1，
若添加一个数字 64 ，那么将long[1]的二进制位中从左往右第一个数置为1，没有添加的数字所在位数是0，用此方法就可记录一个数字是否在BitSet中。
import java.util.*;
public class Main{
public static void main(String[] args) throws Exception{
BitSet bs = new BitSet();
int[] nums={1,2,3,4,5,6,7,8,9,10,10};
for (int num : nums) {
if(bs.get(num)){
System.out.println(num); //
break;
}else {
bs.set(num);
}
}
}
}
再提个问题，40亿个数中，给你一个数X，怎么判断X是否在40亿个数中呢？
二分查找 (理论上的想法，其实我也不知道能不能行..o(>﹏<)o)
先将数据转为二进制数（其实很多地方都可以转二进制计算，比如IP地址），31位二进制可表示约21亿，那么40亿需要32位二进制。将40亿数最高位按1、0分开，那么就分成了0-21亿，21-40亿两部分，然后次最高位按1、0分开.....
然后把需要查找的数字转为32位的二进制，只要从最高位依次往下比较即可。假如重复数字是在【A，B】间，B-A=100000（在我电脑上，进行100000次的for循环查找需要3ms，所以是能接受的），大概位数要比较二三十次，在计算机中比较二三十次的位数非常快。