压缩位图

普通位图的大小是固定的，在面对稀疏存储时会浪费很多空间。，因此产生了压缩位图

布隆过滤器（判重）和hyperloglog（基数）都是近似算法，并且只支持增加，不支持删除。

¶roaring bit map

roaring bit map由一个roaring array组成，其包括三个成员：

• short[] keys
• Container[] values
• int size

一个插入的32位int会被分为高16位和低16位，高16位用于索引keys（保持有序，通过二分查找），低16位用于在Container中索引（类似地，64位会分为高32位和低32位）。

Container分为ArrayContainer（有序数组，数据量小于4096时使用）、BitMapContainer（未压缩的位图）和RunContainer（使用行程长度压缩算法，对连续数据有较好的压缩效果，如果连续性差，反而可能需要更多的空间）。

11,12,13,14,15,21,22会压缩为11,4,21,1。

ArrayContainer和RunContainer在索引时需要再二分一次。

显然，在数据少时选择ArrayContainer，之后选择BitMapContainer和RunContainer中更优的那个。