Bitmap的核心思想是用元素的值的本身来保存其位置,所以一般要求元素的值不能重复。与之相对应的是一般排序算法没有以上要求,并且一般排序算法使用的是比较排序的策略。

例如我们有list [0, 2, 3, 4, 8, 10, 13, 14, 15, 16, 17, 19, 20, 22, 23],那么我们只需要24个bit就可以存储这些元素,策略如下:

  1. 构建一个长度为24个bit的数组
  2. 对所有数字做遍历,把bit 1插入到bit数组中下标与该数字值相等的位置;例如,数字5就应该向bit数组的第5个位置中插入1,插入后结果是 100000
  3. 重复上面的操作,直到把所有的数字都插入到bit数组中,此时数字保存完毕、并且此时数组中的数字都是有序的,操作完成

下面我们有一个简单的例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.*;

public class BitMap {

public static void main(String[] args) {
List<Integer> list = getList();
System.out.println(list);
int s = 0;
for (int i : list) {
// 把1左移i位的值等于2的i次方
// 之后把该值与s并上等于把该值上所有的1都插入s的对应位置上
s = s | 1 << i;
}

StringBuilder sb = new StringBuilder(Integer.toBinaryString(s));
System.out.println(sb.reverse()); // 对二进制做反转操作以方便观察🕵
}

/**
* 生成随机的list
*/

private static List<Integer> getList() {
Set<Integer> set = new HashSet<>();
while (set.size() < 15) {
int i = new Random().nextInt();
if (i < 0)
i = -i;
i = i % 30;
set.add(i);
}
List<Integer> list = new ArrayList<>();
list.addAll(set);
return list;
}

}

我们执行上面的例子得到以下结果

[0, 1, 3, 4, 5, 8, 12, 13, 15, 18, 19, 20, 22, 23, 24]
1101110010001101001110111

第一行是原始的值,第二行是用位图保存的值。我们发现位图的第0位、第1位、第3位、第4位 … 第23位、第24位上的值都为1,对应了这些下标所对应的值的存在,可见我们已经成功的把数字保存到了位图之中。

通过仔细的观察我们发现,在上面的例子中我们用一个int类型的值就可以保存15位大小在0~30之间的数字了,事实上一个int类型的值最多可以保存 4 * 8 = 32 个连续而不重复的数字,按照这样来算即使是1亿个连续而不重复的数字也只需要

100000000 / 32 * 32 / 1024 / 1024 = 94M

即只需要不到95M的内存我们就可以存下这些数字。如果我们不使用位图来保存则需要

100000000 * 4 * 8 / 1024 / 1024 = 3052M

差不多是3个G左右的内存,可见Bitmap对内存的节省还是相当夸张的。