Bitmap 的基本原理

Bitmap 是一种使用 二进制位 来存储数据的算法。由于一个二进制位只能是 0 or 1，所以可以用 0 表示数据不存在，1 表示数据存在。

假设有 1 byte 的内存空间，可以存储 0~7 这 8 个数据，一开始它们都不存在（表现出来的十进制数就是 0）。因为二进制的左侧是高位，右侧是低位，所以第一个位置（最高位）对应的数据是 7。

插入数据

现在要插入数据 2，对应的二进制位修改为 1 ，此时表现出的十进制数就是 4。

再分别插入 3,6，得到的结果如下：

删除数据

如果要删除某个数据，先找到该数据的位置，然后将对应的二进制位修改为 0 即可。

查找

查找某个数据是否存在，只需要判断对应的二进制位是否为 1 即可。除了查找单个数据，还可以实现一些复杂的集合操作。

求交集

假设有两个 Bitmap，记为 map1,map2，它们的存储如下

通过 按位与(&) 求这两个的 bitmap 的交集，得到一个新的 Bitmap；其中第 2 位为 1，也就是说 2 是这两个位图的交集。

  01001100 
& 00110101
= 00000100
复制代码

求并集

通过 按位或(|) 可以求两个 bitmap 的并集，得到一个新的 Bitmap；交集为 [0,2,3,4,5,6]

  01001100 
| 00110101
= 01111101
复制代码

如何修改数据

对于一个包含 8 个比特的 Bitmap，无论是插入还是删除，都涉及到要修改某一个二进制位的数据。给定一个二进制位索引（操作的数据）bitIndex，

如果要修改为 1，使用如下公式，

bitmap |= (1 << bitIndex)
复制代码

1 << bitIndex 得到一个二进制数，它的第 bitIndex 位为 1，其他位都是 0，通过按位或可以保证，无论原来位图中第 bitIndex 位的取值，最终第 bitIndex 位都是 1，而其他位的值保持不变。

例如 bitIndex = 4，bitmap = [01001100]，得到的结果为 [01011100]。

同样的道理，如果要修改为 0，我们使用如下公式，

bitmap &= ~(1 << bitIndex)
复制代码

总结

在实际应用中，位图所存储的数据可以是大量的整数数据，也可以表示用户的 ID 等。

Bitmap 适用于在大量数据的场景下，实现快速 去重，查找 等功能，并且能最大限度的节约存储空间。

实际上，我们无法直接创建 bit 数组，因为内存的分配最少是以 1 byte 为单位的，Java 中可以使用 byte[],int[],long[] 等来作为 Bitmap 的存储结构。Java 同时也提供了 Bitmap 的具体实现：java.util.BitSet。

关于 BitSet 的源码原理和说明，以后再详细讨论。