Java——位图
位图
概念
在之前的腾讯面试题中有这样的一道题：
给40亿个不重复的无符号整数，并且未排过序。如何判断一个数是否在这40亿个数中
这道题需要明白，40亿个无符号整数大约占16个G，而我们大多数电脑内存就是8个g，小部分的是16g，因此我们不能在内存中进行排序然后二分查找，而我们可以使用归并查找，那么时间复杂度大概是O（N*logN），空间复杂度还是O（N）
而如果我们要直接遍历查找，显然时间复杂度是O（N）
此时就要用到我们这篇博客所讲的——位图
位图的中心思想类似于哈希表，位图是使用二进制的比特位来表示一个数字在还是不在，在的话是1，不在的话是0。一个字节有八个比特位，因此一个字节就可以表示八个整数是否在还是不在。所以40亿个无符号整数只需要512mb左右就可以表示了
使用
在java.util包中有官方的位图实现
import java.util.BitSet;public class BitSetDemo {public static void main(String[] args) {int[] arr = {1,2,3,10,4,18,13};BitSet bitSet = new BitSet(18);for (int i = 0; i < arr.length; i++) {bitSet.set(arr[i]);}System.out.println(bitSet.get(10));}
}
我们只需要new一个BitSet对象，可以指定初始长度，不指定也可以，数据满了会自动扩容，然后用set方法传入一些值，用get方法就可以判断这些值在不在位图中了。
MyBitSet
初始化
我们也可以自己实现一个BitSet
使用字节数组来存储数据，用usedSize来记录存储了多少数据
默认初始话的字节数组为1字节，如果要指定使用多少位，那么应该用这个数除以8（因为一字节对应八个比特位），而除后这个数可能有余数，因此要再加一
private byte[] elem;
private int usedSize;public MyBitSet(){this.elem = new byte[1];
}/*** 初始化set* @param n 代表要使用多少位*/
public MyBitSet(int n){this.elem = new byte[n / 8 + 1];
}
set方法
先判断给定的val是否为负数，如果是负数，就抛出异常。
然后让给定的val除以8，得到的商就是在数组中的下标，而余数则是在数组中这个下标的对应左移的比特位
使用｜=（1 << bitIndex），可以保证如果之前插入过这个值，不会影响这个值还是1，也不会更改别的值
最后，让usedSize++
如果arrayIndex大于数组长度减一，那么说明数组不够用，那么需要扩容
/*** 将val转换为数组中的某一位，设置为1* @param val*/
public void set(int val) {if(val < 0){throw new IndexOutOfBoundsException();}int arrayIndex = val / 8;int bitIndex = val % 8;//扩容if(arrayIndex > elem.length - 1){elem = Arrays.copyOf(elem,arrayIndex + 1);}elem[arrayIndex] |= (1 << bitIndex);usedSize++;
}
get方法
同样的，先判断val是不是为负数，是负数就抛出异常
然后通过除8的余数和商得到在字节数组中的下标和左移的次数
然后用字节数组的这个下标对应的字节 & (1 << bitIndex)，如果是1，说明这一位是1，那么说明这个数是存在的，返回true，否则返回0
public boolean get(int val) {if(val < 0){throw new IndexOutOfBoundsException();}int arrayIndex = val / 8;int bitIndex = val % 8;if((elem[arrayIndex] & (1 << bitIndex)) != 0){return true;}return false;
}
reset方法
同样的，先判断val是不是为负数，是负数就抛出异常
然后通过除8的余数和商得到在字节数组中的下标和左移的次数
然后用字节数组的这个下标对应的字节 &= ~(1 << bitIndex)，这样的话别的位上的值不会改变，而不管之前目标位是0还是1，都会被置为0
/*** 将val的对应位置置为0* @param val*/
public void reset(int val){if(val < 0){throw new IndexOutOfBoundsException();}int arrayIndex = val / 8;int bitIndex = val % 8;elem[arrayIndex] &= ~(1 << bitIndex);usedSize--;
}
getUsedSize
/*** 当前位图记录的元素个数* @return*/
public int getUsedSize(){return usedSize;
}
测试
public class Test {public static void main(String[] args) {int[] arr = {1,2,3,10,4,18,13};MyBitSet myBitSet = new MyBitSet(18);for (int i = 0; i < arr.length; i++) {myBitSet.set(arr[i]);}System.out.println(myBitSet.get(10));System.out.println(myBitSet.getUsedSize());myBitSet.reset(10);System.out.println(myBitSet.get(10));}
}
使用位图排序
通过从前往后获取字节数组的每一个字节，然后从后往前寻找每一个为1的位，可以从小到大的输出数组中存储的数据
需要注意的是，这里的elem[i] & (1 << j)应该判断是否不为0，而不是是否等于1，因为这里是按位于而不是&&
public void sort(){for (int i = 0; i < elem.length; i++) {for (int j = 0; j < 8; j++) {if ((elem[i] & (1 << j)) != 0){System.out.print(i * 8 + j + " ");}}}
}