高效查找秘密武器一：位图
有这样的一个问题：
给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+" ");
}
}
}
}
}
