Bitmap

简介

bitmap的核心思想是利用元素本身的值来保存其位置，一般要求元素不能重复。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数组中，此时数字保存完毕、并且此时数组中的数字都是有序的，操作完成。

代码实现：

package com.wangjun.test;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;

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, 3, 5, 9, 11, 12, 13, 14, 18, 19, 21, 24, 25, 26, 28]
10010100010111100011010011101

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

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

100000000 / 1024 / 1024 = 95.36M

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

100000000 * 32 / 1024 / 1024 = 3052M

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

参考：

https://www.jianshu.com/p/bf9dbbc147ed