一、位图

1.1. 概念

在数据结构中，位图（也称为位数组、位向量或位集）是一种紧凑的方式来表示一组布尔值（真/假、1/0）。它本质上是一个数组，其中每个元素代表一个位，该位的位置通常对应于一个标识符或索引。适用于海量数据，整数，数据无重复的场景。

1.2. 面试题

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

解法：

遍历，时间复杂度 $O(n)$ 。
排序+二分查找，时间复杂度 $O(nlogn)+O(logn)$ 。10亿个byte大约是1G，10亿个整数大约是4G，40亿个整数大约就是16G，很明显内存不够

这时我们就可以使用位图来解决上述问题。我们知道一个整数是32个比特位，那么每一个比特位就可以存储不同的数字，0代表没出现过，1代表出现过。那我们就可以根据一组数据的某种关系映射到里面。

如下图所示，我们就可以以8个比特位为一组，每个数据进行/8的操作，然后将其储存在比特位的下标里面。

这样的话40亿个整数只需大约476MB就可以解决。

1.3. 位图的实现

在Java的集合框架中，也有BitSet类。

import java.util.BitSet;public class Test {public static void main(String[] args) {BitSet bitSet = new BitSet();// 设置位bitSet.set(0);bitSet.set(2);bitSet.set(4);// 获取BitSet的大小System.out.println(bitSet.size());// 查询位的状态System.out.println(bitSet.get(0));System.out.println(bitSet.get(1));System.out.println(bitSet.get(2));// 清除位bitSet.clear(2);System.out.println(bitSet.get(2));}
}

public class MyBitSet {public byte[] elem;public int usedSize;public MyBitSet(byte[] elem) {this.elem = new byte[1];}/*** 有可能多给一个字节，但是无所谓* @param n 多少位*/public MyBitSet(int n) {this.elem = new byte[n / 8 + 1];}/*** 设置某一位为1，证明数据出现过* @param val 查找的数据*/public void set(int val) {}/**** @param val 输入的数据* @return 判断当前位是不是1*/public boolean get(int val) {return false;}/*** 将对应位置置为0* @param val 输入的位数*/public void reSet(int val) {}// 获取当前已经使用的位数public int getUsedSize() {return usedSize;}
}

我们先来看设置位方法。如果输入的数据小于0，需要抛出下标越界的异常。对于输入的数据，我们既要计算出需要对应在字节数组中的哪个字节，还要计算出在字节中的哪个bit位。之后我们还需要进行将对应的比特位下标置为1，并且不能改变其它位置的值。比如，我们要设置2位置为1，先将1左移2位，再进行按位或操作。

public void set(int val) {if (val < 0) {throw new IndexOutOfBoundsException();}int arrayIndex = val / 8;int bitIndex = val % 8;elem[arrayIndex] |= (1 << bitIndex);usedSize++;
}

对于get()方法，我们先左移对应的比特位，然后进行按位与的操作，如果结果不是0，说明该位置为1。

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

对于reSet()方法，我们先假设原来这个地方为0，一进行按位与操作，就会将其变成1，所以我们先左移然后按位取反再进行安=按位与。

public void reSet(int val) {if (val < 0) {throw new IndexOutOfBoundsException();}int arrayIndex = val / 8;int bitIndex = val % 8;elem[arrayIndex] &= ~(1 << bitIndex);usedSize--;
}

测试结果

public static void main(String[] args) {int[] array = {1, 3, 7, 4, 12, 16, 19, 13, 22, 18};MyBitSet bitSet = new MyBitSet(22);for (int i = 0; i < array.length; i++) {bitSet.set(array[i]);}System.out.println(bitSet.get(7));System.out.println(bitSet.get(5));System.out.println(bitSet.get(50));
}

出现异常正是因为没有进行扩容，50 / 8结果是6，就会产生越界异常。

完整代码实现：

import java.util.Arrays;public class MyBitSet {public byte[] elem;public int usedSize;public MyBitSet(byte[] elem) {this.elem = new byte[1];}/*** 有可能多给一个字节，但是无所谓* @param n 多少位*/public MyBitSet(int n) {this.elem = new byte[n / 8 + 1];}/*** 设置某一位为1，证明数据出现过* @param val 查找的数据*/public void set(int val) {if (val < 0) {throw new IndexOutOfBoundsException();}int arrayIndex = val / 8;// 扩容if (arrayIndex > elem.length - 1) {elem = Arrays.copyOf(elem, arrayIndex + 1);}int bitIndex = val % 8;elem[arrayIndex] |= (1 << bitIndex);usedSize++;}/**** @param val 输入的数据* @return 判断当前位是不是1*/public boolean get(int val) {if (val < 0) {throw new IndexOutOfBoundsException();}int arrayIndex = val / 8;int bitIndex = val % 8;if (arrayIndex >= elem.length) {return false;}return (elem[arrayIndex] & (1 << bitIndex)) != 0;}/*** 将对应位置置为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--;}// 获取当前已经使用的位数public int getUsedSize() {return usedSize;}public static void main(String[] args) {int[] array = {1, 3, 7, 4, 12, 16, 19, 13, 22, 18};MyBitSet bitSet = new MyBitSet(22);for (int i = 0; i < array.length; i++) {bitSet.set(array[i]);}System.out.println(bitSet.get(7));System.out.println(bitSet.get(5));System.out.println(bitSet.get(50));}
}