BitMap

传统BitMap

1. 传统的bitmap是用一个二进制位（bit）来表示一个值，0表示不存在，1表示存在，这样存储所有32位长度的数据只需要512M存储空间。
2. 但是有个问题：这种bitmap比较固定，即使只表示个位数个数字也需要512M的空间，大部分位都是0，比较浪费空间。
   

Roaring BitMaps

• roaring bitmaps通过将固定的二进制位进行分层，不用位置有不同的应用。从而达到灵活存储，最大限度的高效利用空间的目的。
  • 主要思想：将32bit划分为高16bit和低16bit，高16bit确定桶，对应container存储低16bit。
  • 实现思想：划分2^16个桶，container类型有三种：
    • Array Container
    • Bitmap Container
    • Run Container
      

Array Container

• 用于存储稀疏数据，short数组（低16bit）。
• 数组有序，方便查找。
• 4~4096（4096=8k=bitmap container 占用空间），数组初始容量为4，最大容量为4096。
• 动态扩容。举例： 0xFFFF0000 和 0xFFFF0001，原bitmap占512M，现在占 2+4=6 个Byte，key 占 2 Bytes，两个 value 占 4 Bytes。
  

Bitmap Container

• 原理：与传统bitmap相同。
• 占用固定空间：8K。
• 当array container容量超过4096后，自动转化为bitmapcontainer，不会存在超过4096的array container。
• 实际为long类型数组，long有64bit，所以数组固定容量为1024=2^ 16/2^6
• Bitmap和bitset为同一个东西
  

Run Container

• 适合存放连续数据
• 压缩后存储，”Run”指行程长度压缩算法（Run Length Encoding）
• 原理：对于连续出现的数字，只记录数字和后续数量
  • 最好情况（容量最小）：2short（只存一个数字或一串连续数字，只会存2个short）
  • 最坏情况（容量最大）：128k（所有都是奇数或偶数，需要存65536个short）
    

空间占用情况