什么是bitmap？
计算机中一个字节(byte) = 8位(bit), 这里的bit就是位，数据的最小表示单位；map一般是表示地图或者映射；加一起叫作【位图】？先这么理解把！
简单回顾一下二进制的一些知识：
1byte = 8bit
一个bit有2种状态，0 或者 1
所以1个byte可以表示0000 0000 -> 1111 1111, 也就是十进制的 0 到 255
其中十进制和二进制对应关系如下：
0 ---------> 0000 0000
1 ---------> 0000 0001
2 ---------> 0000 0010
3 ---------> 0000 0011
4 ---------> 0000 0100
5 ---------> 0000 0101
6 ---------> 0000 0110
7 ---------> 0000 0111
8 ---------> 0000 1000
9 ---------> 0000 1001
10 ---------> 0000 1010
11 ---------> 0000 1011
12 ---------> 0000 1100
13 ---------> 0000 1101
.......................
.......................
255 ---------> 1111 1111
在大部分编程语言里面，int类型一般的都是占4个byte，也是32位，甭管你这个数字是1 或者是 21亿你都得占32位，所以如果你现在有10亿数字需要存放在内存里面，需要多少内存呢？
1000 000 000 * 4 / 1024 / 1024 = 3800MB，大概需要3800MB内存
为了解决这个问题，bitmap采用了一种映射机制，举个例子，假如有 1，3, 7，2, 5 这5个数字需要存放，正常情况下你需要5*4=20byte，但bitmap只需要1byte，它是咋做到呢？
假设下面是1byte，首先将所有位置为0：
0 0 0 0 0 0 0 0
从第一个0开始数数，把对应数字的位置置为1，比如说第一个1那就是第2个位置置为1，第二个3就是把第4个位置置为1，依此论推…
1 => 0 1 0 0 0 0 0 0
3 => 0 0 0 1 0 0 0 0
7 => 0 0 0 0 0 0 0 1
2 => 0 0 1 0 0 0 0 0
5 => 0 0 0 0 0 1 0 0
叠加起来最终的串就是：
0 1 1 1 0 1 0 1
其实最终的数字和二进制没有什么关系，纯粹是数数，这个串就可以代表最大到7的数字，然后我们就开始数数，从0开始：
比如第1个位置是1，那就记个1
比如第2个位置是1，那就记个2
比如第3个位置是1，那就记个3
比如第5个位置是1，那就记个5
比如第7个位置是1，那就记个7
结果就是 1 2 3 5 7，不仅仅排序了，而且还去重了！如果按照这种转换机制，1个int类型，32位的话，可以表示0-31之间的数字！
如果你们要表示最大1万的数，那就需要1万个位的串，但是编程语言并没有这样的数据类型，但是可以用数组去模拟
举个例子：一个整型是32位，也就说我们大概需要314个数组元素来表示这个串
数组第1个元素 00 - 31
数组第2个元素 32 - 63
数组第3个元素 64 - 95
数组第4个元素 96 - 127
... ...
通过以上对bitmap原理的阐述，我们可以看到bit极大的节约了存储空间， 如果我们需要存储一个0～999 999 999 个唯一数字，每个存一条至少需要 3800MB；如果用bitmap存储后需要999 999 999 个bit位；只用大约120M就够了
这个算法的好处，最大的好处就是节省内存，节省了好几十倍，适合处理大量数据，除了快速排序，还可以做快速去重，快速查询是否存在，还有一个比较好听的应用 Bloom Filter(布隆过滤器):
Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一个元素x，第i个哈希函数映射的位置hi(x)就会被置为1（1≤i≤k）。注：如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。 Bloom Filter 在判断y是否属于这个集合时，对y应用k次哈希函数，若所有hi(y)的位置都是1（1≤i≤k），就认为y是集合中的元素，否则就认为y不是集合中的元素。
BitMap 也可以用来表述字符串类型的数据，但是需要有一层Hash映射
bitmap的优缺点
优点：
-
节省存储空间
-
可以快速去重，快速查询
-
可以利用位运算的高性能实现做交集和并集运算
缺点：
-
无法进行[非运算]（可以使用两个bitmap解决，一个存条件数据，一个存全量数据）
-
数据碰撞。比如将字符串映射到 BitMap 的时候会有碰撞的问题，那就可以考虑用 Bloom Filter 来解决 Bloom Filter 使用多个 Hash 函数来减少冲突的概率。
-
数据稀疏。又、比如要存入(10,13489, 78921736)这三个数据，我们需要按最大数（78921736）开辟存储空间， 但是实际上只存了3个数据，这时候就有很大的空间浪费，碰到这种问题的话，可以通过引入 Roaring BitMap 来解决。
[参考文档]