内容来自：
https://zhuanlan.zhihu.com/p/379713260

概念

BitMap的核心思想：用一个bit位来记录0和1两种状态，将具体数据映射到比特数组的具体某一位上，这个bit位设置为0表示该数不存在，设置为1表示该数存在。
BitMap的用途：可以用来处理大量数据的排序、查询以及去重等，BitMap在用户群做交集和并集运算的时候也有极大的便利。
在数据量越大的情况下，BitMap节省空间的效果就越显著。所以BitMap很适合用来进行大量数据的排序、去重、查找，包括在线活跃用户的统计，用户签到等。

10进制到2进制映射。
可以用int(32bit)或者long(64bit)来进行映射。如果使用int进行映射，假设要排序的数有N个，那么需要申请的内存空间大小就是int[(N - 1) / 32 + 1]，映射关系如下：
a[0]：0 ~ 31
a[1]：32 ~ 63
a[2]：64 ~ 95
…
可知，给定一个数num在对应数组a[i]中的下标为 num % 32。

一个数num存放在a[num / 32]的num % 32下标上。可以通过移位操作将对应位置1
a[n >> 5] |= 1 << (n & 0x1F)
n & 0x1F 保留n的后五位，相当于 n % 32。

代码

用java实现一个简单的BitMap：

import java.util.Arrays;

public class BitSet {
    private int[] bits;

    private final static int ADDRESS_BITS_PER_WORD = 5;
    private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;

    /**
     * 无参构造器
     * 默认构造容量为32bit的数组，即数组长度为1
     */
    public BitSet() {
        bits = new int[(BITS_PER_WORD - 1) >> ADDRESS_BITS_PER_WORD + 1];
    }

    /**
     * 有参构造器
     * @param nbits 数字的个数
     */
    public BitSet(int nbits) {
        bits = new int[(nbits - 1) >> ADDRESS_BITS_PER_WORD + 1];
    }

    public int[] getBits() {
        return bits;
    }

    /**
     * 把num映射到bits数组中
     * @param num
     */
    public void set(int num) {
        // num在数组中的下标
        int index = num >> ADDRESS_BITS_PER_WORD;
        // TODO：要检查数组是否需要扩容
        bits[index] |= 1 << (num & 0x1F);
    }

    /**
     * 判断bits数组中对应位的值
     * @param bitIndex
     * @return
     */
    public boolean get(int bitIndex) throws Exception {
        if (bitIndex < 0) {
            throw new Exception();
        }
        // 把输入的下标进行转换，对应数组某个值的某个位置
        int index = bitIndex >> ADDRESS_BITS_PER_WORD;
        return (bitIndex < bits.length) && ((bits[index] & (1 << (bitIndex & 0x1F))) != 0);
    }

    public static void main(String[] args) throws Exception {
        // 5亿个数
        BitSet bitSet = new BitSet(1_0000_0000);
        // 目标数组
        int[] arr = {2, 98, 76, 56, 100, 762, 16, 95};
        Arrays.stream(arr).forEach(num -> {
            bitSet.set(num);
        });

        // 判断某个数在数组中是否存在
        System.out.println(bitSet.get(100));  // true
        System.out.println(bitSet.get(200));  // false
        System.out.println(bitSet.get(762));  // true

        // 输出排序后的数组
        int[] res = bitSet.getBits();
        int count = 0;
        for (int i = 0; i < res.length; i++) {
            // 按位输出
            for (int j = 0; j < 32; j++) {
                // 为1表示该数存在
                if (((res[i] >> j) & 1) == 1) {
                    arr[count++] = i * 32 + j;
                }
            }
        }
        // 2 16 56 76 95 98 100 762
        Arrays.stream(arr).forEach(System.out::println);
    }
}

bits[0][0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
bits[1][0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
bits[2][0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
bits[3][0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
bits[4][0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    ......

一些位图算法对应的开源实现：
JDK的BitSet和Google的EWAHCompressedBitmap，Redis里也提供了类似的一些命令，主要有以下几个：SETBIT， GETBIT， BITCOUNT， BITOP， BITPOS，BITFIELD。

优缺点

优点：
（1）运算效率高。
（2）占用内存少。

缺点：
（1）对重复数据无法进行排序。
（2）数据碰撞。比如将字符串映射到 BitMap 的时候会有碰撞的问题，那就可以考虑用 Bloom Filter 来解决，Bloom Filter 使用多个 Hash 函数来减少冲突的概率。
（3）数据稀疏时浪费空间。可以通过引入 Roaring BitMap 来解决。