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 对内存的节省还是相当夸张的。