☕【难点攻克技术系列】「海量数据计算系列」如何使用 BitMap 在海量数据中对相应的进行去重、查找和排序

BitMap（位图）的介绍

BitMap 从字面的意思，很多人认为是位图，其实准确的来说，翻译成基于位的映射，其中数据库中有一种索引就叫做位图索引。

在具有性能优化的数据结构中，大家使用最多的就是 hash 表，是的，在具有定位查找上具有 O(1)的常量时间，多么的简洁优美。但是数据量大了，内存就不够了。此外，可以使用类似外排序来解决问题的，由于要走 IO 所以时间上又不行。

所谓的 Bit-map 就是用一个 bit 位来标记某个元素对应的 Value， 而 Key 即是该元素。由于采用了 Bit 为单位来存储数据，因此在存储空间方面，可以节省。

BitMap（位图）的应用

• 1）可进行数据的快速查找，判重，删除，一般来说数据范围是 int 的 10 倍以下。

• 2）去重数据而达到压缩数据

BitMap（位图）的原理

上面说了 BitMap 的基本思想就是用一个 bit 位来标记某个元素对应的 Value，而 Key 即是该元素。由于采用了 Bit 为单位来存储数据。

BitMap（位图）的案例

假设有这样一个需求：在 20 亿个随机整数中找出某个数 m 是否存在其中，并假设 32 位操作系统，4G 内存

在 Java 中，int 占 4 字节，1 字节=8 位（1 byte = 8 bit）

• 如果每个数字用 int 存储，那就是 20 亿个 int，因而占用的空间约为 (2000000000*4/1024/1024/1024)≈7.45G
  

• 如果按位存储就不一样了，20 亿个数就是 20 亿位，占用空间约为 (2000000000/8/1024/1024/1024)≈0.233G
  

如何表示一个数呢

每一位表示一个数，0 表示不存在，1 表示存在，这正符合二进制

这样可以很容易表示{1,2,4,6}这几个数：

计算机内存分配的最小单位是字节，也就是 8 位，那如果要表示{12,13,15}怎么办呢？当然是在另一个 8 位上表示了：

这样的话，好像变成一个二维数组了

1 个 int 占 32 位，那么我们只需要申请一个 int 数组长度为 int tmp[1+N/32] 即可存储，其中 N 表示要存储的这些数中的最大值，于是乎：

• tmp[0]：可以表示 0~31

• tmp[1]：可以表示 32~63

• tmp[2]：可以表示 64~95

如此一来，给定任意整数 M，那么 M/32 就得到下标，M%32 就知道它在此下标的哪个位置。

添加

怎么把一个数放进去呢？例如，想把 5 这个数字放进去，怎么做呢？

首先，5/32=0，5%32=5，也是说它应该在 tmp[0]的第 5 个位置，那我们把 1 向左移动 5 位，然后按位或

换成二进制就是

这就相当于 86 | 32 = 118

86 | (1<<5) = 118b[0] = b[0] | (1<<5)

要想插入一个数，将 1 左移带代表该数字的那一位，然后与原数进行按位或操作

简化一下，就是 86 + (5/8) | (1<<(5%8))

因此，公式可以概括为：p + (i/8)|(1<<(i%8)) 其中，p 表示现在的值，i 表示待插入的数

清除

如果要清除该怎么做呢？

还是上面的例子，假设我们要 6 移除，该怎么做呢？

从图上看，只需将该数所在的位置为 0 即可

1 左移 6 位，就到达 6 这个数字所代表的位，然后按位取反，最后与原数按位与，这样就把该位置为 0 了

b[0] = b[0] & (~(1<<6))

b[0] = b[0] & (~(1<<(i%8)))

查找

每一位代表一个数字，1 表示有（或者说存在），0 表示无（或者说不存在）。通过把该为置为 1 或者 0 来达到添加和清除的效果，那么判断一个数存不存在就是判断该数所在的位是 0 还是 1

假设，我们想知道 3 在不在，那么只需判断 b[0] & (1<<3) 如果这个值是 0，则不存在，如果是 1，就表示存在。

Bitmap 快速排序

假设我们要对 0-7 内的 5 个元素(4,7,2,5,3)排序（这里假设这些元素没有重复）,我们就可以采用 Bit-map 的方法来达到排序的目的。要表示 8 个数，我们就只需要 8 个 Bit（1Bytes），首先我们开辟 1Byte 的空间，将这些空间的所有 Bit 位都置为 0，然后将对应位置为 1。最后，遍历一遍 Bit 区域，将该位是一的位的编号输出（2，3，4，5，7），这样就达到了排序的目的，时间复杂度 O(n)。

优点：

• 运算效率高，不需要进行比较和移位；

• 占用内存少，比如 N=10000000；只需占用内存为 N/8=1250000Byte=1.25M

缺点：

• 所有的数据不能重复。即不可对重复的数据进行排序和查找。

• 只有当数据比较密集时才有优势

Bitmap 快速去重

• 20 亿个整数中找出不重复的整数的个数，内存不足以容纳这 20 亿个整数。

• 首先，根据“内存空间不足以容纳这 05 亿个整数”我们可以快速的联想到 Bit-map。下边关键的问题就是怎么设计我们的 Bit-map 来表示这 20 亿个数字的状态了。其实这个问题很简单，一个数字的状态只有三种，分别为不存在，只有一个，有重复。因此，只需要 2bits 就可以对一个数字的状态进行存储了，假设我们设定一个数字不存在为 00，存在一次 01，存在两次及其以上为 11。那我们大概需要存储空间 2G 左右。

• 接下来的任务就是把这 20 亿个数字放进去（存储），如果对应的状态位为 00，则将其变为 01，表示存在一次；如果对应的状态位为 01，则将其变为 11，表示已经有一个了，即出现多次；如果为 11，则对应的状态位保持不变，仍表示出现多次。

• 最后，统计状态位为 01 的个数，就得到了不重复的数字个数，时间复杂度为 O(n)。

快速查找

int 数组中的一个元素是 4 字节占 32 位，那么除以 32 就知道元素的下标，对 32 求余数（%32）就知道它在哪一位，如果该位是 1，则表示存在.

Bitmap 的场景总结

• Bitmap 主要用于快速检索关键字状态，通常要求关键字是一个连续的序列（或者关键字是一个连续序列中的大部分）， 最基本的情况，使用 1bit 表示一个关键字的状态（可标示两种状态），但根据需要也可以使用 2bit（表示 4 种状态），3bit（表示 8 种状态）。

• Bitmap 的主要应用场合：表示连续（或接近连续，即大部分会出现）的关键字序列的状态（状态数/关键字个数 越小越好）。

• 32 位机器上，对于一个整型数，比如 int a=1 在内存中占 32bit 位，这是为了方便计算机的运算。但是对于某些应用场景而言，这属于一种巨大的浪费，因为我们可以用对应的 32bit 位对应存储十进制的 0-31 个数，而这就是 Bit-map 的基本思想。Bit-map 算法利用这种思想处理大量数据的排序、查询以及去重。

参考资料

https://blog.csdn.net/qq_41369135/article/details/116938671