目录
四、bitmap的存储空间的优化之RoaringBitmap
一、什么是bitmap
bit即比特，是计算机系统里边数据的最小单位，8个bit即为一个Byte。一个bit的值，要么是0，要么是1。bitmap可以理解为通过一个bit数组来存储特定数据的一种数据结构；
二、bitmap原理
BitMap 的基本原理就是
用一个 bit 来标记某个元素对应的 Value，而 Key 即是该元素
。
举个例子：
假入你要存一个整数10，那么 在bitmap中存储的时候key 就是10，bitmap的value就是 第10个bit位的标记，1；如下图：
这是一个10bit的数组，从左往右数分别是0，1，2，…10代表10个位置。那刚才的数字来讲，存储在内存中就是这样的，第10个位置上标记1，代表数字 10存在这了，前面的9位是0 代表没有存。如下图：
三、bitmap
存储空间上的优势，劣势是什么？
结论：
bitmap在数据稠密的时候，非常节省空间，但是在数据稀疏的时候，会有极大的浪费
。
详解：
我们知道一个int型的整型数字存储在内存中是占4个字节（4byte），一个byte是8bit，还是拿上面的例子，存储一个数字 10，用一个int型数组 int[1] 表示的话 就是 1*4*8=32 bit，在内存中占 32bit位，如果是使用 bitmap存呢？32bit 可以存 32个数字，每一个bit位都可以代表一个数字（即可以存储从1，到32，共32个数字），看到了吗？这就是bitmap在存储空间上的优势。
同理这样也会有个劣势，假如bitmap就只是存一个很大的数字 10000， 那怎么表示呢，那就在第10000个bit位上置1其他的bit位还是默认的0，
那么bitmap这时候是占了 10000bit的，而10000这个数字用一个int类型的数组存的话，内存中还是 只占 32bit
。
四、bitmap的
存储空间的优化之RoaringBitmap
RoaringBitmap 于2016年由S. Chambi、D. Lemire、O. Kaser等人在论文
《Better bitmap performance with Roaring bitmaps》
与
《Consistently faster and smaller compressed bitmaps with Roaring》
中提出，官网
这里
。这里不详细解释，有兴趣的同学可以看下。
其主要思路是：将32位无符号整数按照高16位分桶，即最多可能有216=65536个桶，论文内称为container。存储数据时，按照数据的高16位找到container（找不到就会新建一个），再将低16位放入container中
图中示出了三个container：
- 高16位为0000H的container，存储有前1000个62的倍数。
- 高16位为0001H的container，存储有[216, 216+100)区间内的100个数。
- 高16位为0002H的container，存储有[2×216, 3×216)区间内的所有偶数，共215个。
-
ArrayContainer
当桶内数据的基数不大于4096时，会采用它来存储，其本质上是一个unsigned short类型的有序数组。数组初始长度为4，随着数据的增多会自动扩容（但最大长度就是4096）。另外还维护有一个计数器，用来实时记录基数。
-
BitmapContainer
当桶内数据的基数大于4096时，会采用它来存储，其本质就是上一节讲过的普通位图，用长度固定为1024的unsigned long型数组表示，亦即位图的大小固定为216位（8KB）。它同样有一个计数器。