高效查找秘密武器一：位图

有这样的一个问题：

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数 中。

那么我们一般会想到这样做的

1.遍历，时间复杂度O(n)

2.排序（N*logN），然后二分查找

那么此时此刻，我们再次细想一下，这些方法一般放在内存中进行的，那么40亿个不重复的无符号整数，有多大容量呢？

首先，10亿个字节大概是1个G

那么10亿个整数大约是4个G

然后呢40亿个整数大约是16个G

所以，如若这么大容量放到电脑内存上跑，恰好此时电脑内存也是16个G，那么不是刚刚好？

其实不然，电脑上不单单只是跑这个程序，后面还有很多，比如微信啊，爱奇艺什么的，所以一般来说，这么大容量放到16G的电脑内存是不太现实的。

那么还有什么解决办法呢？

那就请出今天的主角之一：位图

位图

那么什么又是位图呢？
这里说的位图指的是数据结构当中的，不是那个指图像那个位图哦！

位图：所谓的位图，就是用每一位来存放某种状态的。

适用于海量数据，整数，数据无重复的场景。通常用来判定某个数据存不存在的。

那么举个例子来看看

我这里，假设有了一个字节数组，然后有三个字节，那么一个字节呢，又对应8个比特位

一个比特位呢，又可以代表0/1两种状态。

所以数组arr中，每个数字可以通过某个算式来确定某个位置，然后将某个位置的比特位设置为1，说明，此数字存在。

比如，就11来说

11/8=1

那么我们就放到这个1下标

11%8=3

那么我们就在数组1下标下的第三个比特位设置为1，

然后可以说明数字是存在过的

这里值得注意下，为什么比特位标明的数字从右到左呢？

这里是为了方便，自己也是可以左到右的。

那么回过头细想一下，一个字节有8个比特位，且8个比特位都可以表示状态。

那么10亿个字节大概是0.9G，接近1G

10亿个比特位大概是119兆，看作128兆

那么40亿个比特位，那么就是可以看作512兆。

所以内存量一下子大大缩小了。

那么你看这个位图是不是很强大呢！

ok，那么接下来讲讲如何实现它吧。

由上述刚刚的例子可以看得出，底层还是一个数组来的，而且还是一个字节数组。

然后呢，我们创建它的时候，默认给定一个容量。

但是，有时候，需要用户指定它需要范围是多大，那么可以这样写。

  //位图底层还是一个数组public byte [] elem;//记录存放数据多少public int Usize;public MyBitMap(){//默认给定的数组大小是1个字节this.elem=new byte[1];}public MyBitMap(int n){this.elem=new byte[n/8+1];}

在给定参数的构造方法中，假设我们给定数字范围是10个，那么10/8=1，但是还余下两个，9 10

所以我们直接给多一个字节是可以的。set

那么接着讲讲set吧

set：

思路：

当然这是核心思路，然后代码实现方面还是需要考虑一些细节

比如，我们set方法，参数传入一个数字的话，如若数字给到的是<0的数字，那么此时是不符合我们位图的

再者如果是给定的数字，如若在找数组下标时超出数组范围，这时候也是需要处理的，比如扩容操作。

那么代码如下：

 public void set(int val){if(val<0){//需要抛出异常，因为会导致数组越界throw new IndexOutOfBoundsException();}//放到字节数组哪个位置int arrIndex=val/8;if(arrIndex>elem.length){//超出数组范围，进行扩容elem= Arrays.copyOf(elem,arrIndex+1);}//放到字节数组位置的哪个比特位int bitIndex=val%8;elem[arrIndex] |=(1<<bitIndex);Usize++;}

这个找哪个比特位进行修改，其实最开始时讲过了

即val/8=字节数组哪个下标，

val%8=下标内哪个比特位。

所以这里我们就可以找到，哪个字节哪个比特位要进行修改状态，比如举的例子，设置5这个数字

5/8=0，即在数组0下标

5%8=5，即在比特位第六个位置

get：

这个get方法是返回这个数字是否是存在过的。

所以呢，我们还得是找到这个数字在哪先，然后判断下这个数字的比特位是否是1

举例：

代码：
 

public boolean get(int val){if(val<0){throw new IndexOutOfBoundsException();}int arrIndex=val/8;int bitIndex=val%8;if((elem[arrIndex]&(1<<bitIndex))!=0){return true;}return false;}

reset：

reset方法呢，是把传入参数，对应的比特重新置为0

举例说明：

代码：

 public void reset(int val){if(val<0){throw new IndexOutOfBoundsException();}int arrIndex=val/8;int bitIndex=val%8;elem[arrIndex] &= ~(1<<bitIndex);Usize--;}public int getSize(){return Usize;}

值得注意的是，进行set的时候，Usize++了

所以写一个方法方法来返回当前设置的个数。

那么位图一些基本方法写完了，这里还差最后一个方法：排序

排序

其实我们位图是可以排序的

拿这里来说：

只要我们从右边开始，遍历当前比特位是1的就可以输出当前的值

那么判断当前位是不是为1，是get方法里的思路是一致的，用上&

那么如何输出当前的数字呢？

比如我要输出的是5，那么此时我们可以这样val=i*8+j

当前的i=0，因为我们输出的数字是5，在字节数组的0下标，当j从下标开始遍历，j=5时，就可以输出这个数字5了

代码：
 

 public static void main(String[] args) {int [] arr=new int[]{3,10,9,5,7,24,18};MyBitMap myBitMap=new MyBitMap(24);//先把数据放进字节数组中for(int i=0;i<arr.length;i++){myBitMap.set(arr[i]);}//排序for(int i=0;i< myBitMap.elem.length;i++){for(int j=0;j<8;j++){if((myBitMap.elem[i]&(1<<j))!=0){System.out.print(i*8+j+" ");}}}}

ok，那么位图这里，小编分享的差不多了。

顺带提一句，一开始给的那道题是腾讯曾经的面试题来的。

源码：

public class MyBitMap {//位图底层还是一个数组public byte [] elem;//记录存放数据多少public int Usize;public MyBitMap(){//默认给定的数组大小是1个字节this.elem=new byte[1];}public MyBitMap(int n){this.elem=new byte[n/8+1];}/*** set操作，对添加进来的数据置为1，即为存在的意思* @param val*/public void set(int val){if(val<0){//需要抛出异常，因为会导致数组越界throw new IndexOutOfBoundsException();}//放到字节数组哪个位置int arrIndex=val/8;if(arrIndex>elem.length){//超出数组范围，进行扩容elem= Arrays.copyOf(elem,arrIndex+1);}//放到字节数组位置的哪个比特位int bitIndex=val%8;elem[arrIndex] |=(1<<bitIndex);Usize++;}/*** get方法返回比特位是否设置过1* @param val* @return*/public boolean get(int val){if(val<0){throw new IndexOutOfBoundsException();}int arrIndex=val/8;int bitIndex=val%8;if((elem[arrIndex]&(1<<bitIndex))!=0){return true;}return false;}public void reset(int val){if(val<0){throw new IndexOutOfBoundsException();}int arrIndex=val/8;int bitIndex=val%8;elem[arrIndex] &= ~(1<<bitIndex);Usize--;}public int getSize(){return Usize;}public static void main(String[] args) {int [] arr=new int[]{3,10,9,5,7,24,18};MyBitMap myBitMap=new MyBitMap(24);//先把数据放进字节数组中for(int i=0;i<arr.length;i++){myBitMap.set(arr[i]);}//排序for(int i=0;i< myBitMap.elem.length;i++){for(int j=0;j<8;j++){if((myBitMap.elem[i]&(1<<j))!=0){System.out.print(i*8+j+" ");}}}}
}