如何判断一个数是否在40亿个整数中？
如何判断一个数是否在40亿个整数中？
一个整数int，在java中占4个字节，那么40亿个整数就是160亿字节。
160亿字节 约等于 1600万KB
1600万KB 约等于 16000M
16000M 约等于 16G
方案一：redis
方案二：大数据思想bitmap
byte的取值范围为-128~127，占用1个字节（-2的7次方到2的7次方-1）
short的取值范围为-32768~32767，占用2个字节（-2的15次方到2的15次方-1）
int的取值范围为（-2147483648~2147483647），占用4个字节（-2的31次方到2的31次方-1）
long的取值范围为（-9223372036854774808~9223372036854774807），占用8个字节（-2的63次方到2的63次方-1）
我们知道，整数int在java中占4个字节，范围从-2147483648~2147483647，一共包含40多亿个整数，满足我们的需求，因为我们只需要40亿个位就够了。
我先说一下实现的思路：
1，首先new一个byte数组，这个数组的长度为5亿，因为一个byte有8个位。
private byte[] arr = new byte[500000000];
2，然后就是新增元素的方法。
index代表byte数组的下标。
position代表n在arr[index]的位置。
方法实现代码如下：
public void addBit(int n){
// 一个byte等于8个bit 用位运算效率高
int index = n >> 3;
// n对8取余，即n%8，用位运算表示
int position = n & 0x07;
arr[index] |= 1 << position;
}
3，接下来我们定义一下查找操作，判断给定整数，是否在这40亿的数中。
public boolean findBit(int n){
int index = n >> 3;
int position = n & 0x07;
return (arr[index] & (1 << position)) != 0
}
OK，这样基本上就完成了bitmap算法的主要功能，接下来，我进行一下测试，我的电脑是8G内存，首先我new一个长度为20亿的byte数组，然后，查找123456这个整数是否在这个数组中。
这个执行速度很快，基本上可以在几秒钟完成。
BitMap 的基本原理就是用一个 bit 来标记某个元素对应的 Value，而 Key 即是该元素。由于采用一 个bit 来存储一个数据，因此可以大大的节省空间。
BitMap处理字符串
BitMap 也可以用来表述字符串类型的数据，但是需要有一层Hash映射，如下图，通过一层映射关系，可以表述字符串是否存在。
当然这种方式会有数据碰撞的问题，但可以通过 Bloom Filter 做一些优化。Bloom Filter指的是布隆过滤器。
BitMap的使用场景
BitMap 的使用场景很广泛，比如说 Oracle、Redis 中都有用到 BitMap。当然更多的系统会有比 BitMap 稍微复杂一些的算法，比如 Bloom Filter、Counting Bloom Filter，这些会在后面逐一展开。
下面举一个在算法中用到 BitMap 来解决问题的例子。
已知某个文件内包含一些电话号码，每个号码为8位数字，统计号码的个数。
8 位的整数，相当于是范围在(0,99999999)，也就是说 99999999 个 bit，也就是 12M 左右的内存，比起用类似 HashMap 的方式的话能节省很大的空间。 可以理解为从0 到 99999999 的数字，每个数字对应一个 Bit位，所以只需要 12M 左右的内存表示了所有的 8 位数的电话。
public boolean countBit(byte[] arr){
int index = 0;
int position = 0;
int count = 0;
for (int i = 0; i < arr.length; i++) {
index = n >> 3;
position = n & 0x07;
if ((arr[index] & (1 << position)) != 0) {
count++;
}
}
return count;
}
四，总结
BitMap 的思想在面试的时候还是可以用来解决不少问题的，然后在很多系统中也都会用到，算是一种不错的解决问题的思路。
但是 BitMap 也有一些局限，因此会有其它一些基于 BitMap 的算法出现来解决这些问题。
数据碰撞。比如将字符串映射到 BitMap 的时候会有碰撞的问题，那就可以考虑用 Bloom Filter 来解决，Bloom Filter 使用多个 Hash 函数来减少冲突的概率。
数据稀疏。又比如要存入(10,8887983,93452134)这三个数据，我们需要建立一个 99999999 长度的 BitMap ，但是实际上只存了3个数据，这时候就有很大的空间浪费，碰到这种问题的话，可以通过引入 Roaring BitMap 来解决。
方案三：分布式实时计算
把数据分散在8台机器上，然后来一个新的数据，8台机器一起找，最后再汇总结果就行了。
如何判断一个数是否在40亿个整数中？
