BitMap
Bit-map的基本思想就是用一个bit位来标记某个元素对应的Value，而Key即是该元素。由于采用了Bit为单位来存储数据，可以很大力度的节省空间，常用于对大量整数做去重和查询操作。位图（bitmap）的方式存储了[0, 2^32 - 1]区间上的数据，需要耗费512MB的存储空间。
如果我们想快速排序{6,8,2,5,4},根据位图我们应该
BitMap常见应用场景
快速排序 快速去重 快速查找
BitMap不足点：
1、数据碰撞。比如将字符串映射到 BitMap 的时候会有碰撞的问题，那就可以考虑用 Bloom Filter 来解决，Bloom Filter 使用多个 Hash 函数来减少冲突的概率。
2、数据稀疏。又比如要存入(10,8887983,93452134)这三个数据，我们需要建立一个 99999999 长度的 BitMap ，但是实际上只存了3个数据，这时候就有很大的空间浪费，碰到这种问题的话，可以通过引入 Roaring BitMap 来解决。
RoaringBitmap
1: 将 32bit 划分为 2^16 个桶，每个桶有一个 Container 来存放一个数值的低16位
2: 在存储和查询数值时，将数值 k 划分为高 16 位(k % 2^16) 和低 16 位(k mod 2^16)，取高 16 位找到对应的桶，然后在低 16 位存放在相应的 Container 中
3: RBM 常用两种容器结构：ArrayContainer 和 BitmapContainer
ArrayContainer 存放稀疏的数据，BitmapContainer 存放稠密的数据，即：
若一个 Container 中的 Integer 数量小于 4096，就用 char 数组(ArrayContainer)来存储值
若大于 4096，就用 BitmapContainer 来存储值
Integer 的低 16 位是 2Byte，因此对应到 ArraryContainer 就是 2Byte * 4096 = 8KB；同样，BitmapContainer 的 2^16 个 bit 也相当于是 8KB
short[] content始终保持有序，方便使用二分查找，且不会存储重复数值。
示例讲解：
将 821697800 这个 32 bit 的整数插入 RBM 中，整个算法流程如下：
821697800 对应的 16 进制数为 30FA1D08， 其中高 16 位为 30FA， 低16位为 1D08 先用二分查找从一级索引(即 ArrayContainer)中找到数值为 30FA 的容器(若容器不存在，则新建一个) 从图中我们可以看到，该容器是一个 Bitmap 容器 找到容器后，其低 16 位的数值 1D08，即 7432，因此在 Bitmap 中找到相应位置，将其置为 1 即可
RBM处理的是32位的数字，如果我们想处理Long类型的数字怎么办呢？这个时候可以使用Roaring64NavigableMap。Roaring64NavigableMap也是使用拆分模式，将一个long类型数据，拆分为高32位与低32位，高32位代表索引，低32位存储到对应RoaringBitmap中，其内部是一个TreeMap类型的结构，会按照signed或者unsigned进行排序，key代表高32位，value代表对应的RoaringBitmap。
Container分类：
ArrayContainer:当桶内数据的基数不大于 4096 时，会采用它来存储.
BitmapContainer:当桶内数据的基数大于 4096 时，会采用它来存储.
RunContainer：使用Run-Length Encoding方式压缩存储的元素，对连续数据的压缩效果特别好，但如果数据比较散列，反而会更占用空间，长度没有限制；这种压缩算法的性能和数据的连续性（紧凑性）关系极为密切。
sharedcontainer：它本身是不存储数据的，只是用它来指向arraycontainer,bitmapcontainer或runcontainer,就好比指针的作用一样。这个指针（sharedcontainer）可以被多个对象拥有，但是指针所指针的实质东西是被这多个对象所共享的。
ArrayContainer存储稀疏数据，BitmapContainer存储稠密数据，可以最大限度地避免内存浪费。
Container性能总结:
读取时间
只有BitmapContainer可根据下标直接寻址，复杂度为O(1)，ArrayContainer和RunContainer都需要二分查找，复杂度O(log n)
内存占用
ArrayContainer一直线性增长，在达到4096后就完全比不上BitmapContainer了,适合小数据量的存储
BitmapContainer是一条横线，始终占用8kb，当大于4096会自动会转为 BitmapContainer
RunContainer比较奇葩，因为和数据的连续性关系太大，因此只能画出一个上下限范围。不管数据量多少，下限始终是4字节；上限在最极端的情况下可以达到128kb。
空间占用对比
1、连续数据
2、稀疏数据
我们向位图中插入1和999w两个偏移量位的元素，再次对比BitMap和RoaringBitMap所占用空间大小。
roaringbitmap相较于BitMap的优势？
内存上：
bitmap比较适用于数据分布比较稠密的存储场景中，对于原始的Bitmap来说，若要存储uint32类型数据，这就需要2 ^ 32长度的bit数组 通过计算可以发现(2 ^ 32 / 8 bytes = 512MB), 一个普通的Bitmap需要耗费512MB的存储空间。如果我们只存储几个数据的话依然需要占用521M空间，这就有些浪费空间了，因此我们可以采用对位图进行压缩的RoaringBitMap,以此减少内存和提高效率。
性能上：
roaringbitmap除了比bitmap占用内存少之外，其并集和交集操作的速度也要比bitmap的快。原因归结为以下几点：
- 计算上的优化
对于roaringbitmap本质上是将大块的bitmap分成各个小块，其中每个小块在需要存储数据的时候才会存在。所以当进行交集或并集运算的时候，roaringbitmap只需要去计算存在的一些块而不需要像bitmap那样对整个大的块进行计算。如果块内非常稀疏，那么只需要对这些小整数列表进行集合的 AND、OR 运算，这样的话计算量还能继续减轻。这里既不是用空间换时间，也没有用时间换空间，而是用逻辑的复杂度同时换取了空间和时间。
同时在roaringbitmap中32位长的数据，被分割成高 16 位和低 16 位，高 16 位表示块偏移，低16位表示块内位置，单个块可以表达 64k 的位长，也就是 8K 字节。这样可以保证单个块都可以全部放入 L1 Cache，可以显著提升性能。
2. 程序逻辑上的优化
1、roaringbitmap维护了排好序的一级索引，以及有序的arraycontainer当进行交集操作的时候，只需要根据一级索引中对应的值来获取需要合并的容器，而不需要合并的容器则不需要对其进行操作直接过滤掉。
2、当进行合并的arraycontainer中数据个数相差过大的时候采用基于二分查找的方法对arraycontainer求交集,避免不必要的线性合并花费的时间开销。
3、roaingbitmap在做并集的时候同样根据一级索引只对相同的索引的容器进行合并操作，而索引不同的直接添加到新的roaringbitmap上即可，不需要遍历容器。
4、roaringbitmap在合并容器的时候会先预测结果，生成对应的容器，避免不必要的容器转换操作。
StarRocks 的 Bitmap 去重是基于 Roaring Bitmap 实现的，roaring bitmap 只能对 TINYINT，SMALLINT，INT 和 BIGINT 类型的数据去重。如想要使用 Roaring Bitmap 对其他类型的数据去重，则需要构建全局字典。
如列基数较低，值大量重复，例如 ENUM 类型的列，使用 Bitmap 索引能够减少查询的响应时间。
如列基数较高，推荐使用 Bloom filter 索引。
Bitmap index 和 Bitmap 去重二者虽然都使用 Bitmap 技术，但引入原因和解决的问题完全不同。前者用于低基数的枚举型列的等值条件过滤，后者则用于计算一组数据行的指标列的不重复元素的个数。
Bloom filter
布隆过滤器的原理是，当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。
Bloom filter本质就是：K个hash函数+BitMap
(3). 判断是否存在
向布隆过滤器查询某个key是否存在时,先把这个key通过多个hash函数进行运算,查看对应的位置是否都为1,只要有一个位为0,那么说明布隆过滤器中这个key不存在
如果这几个位置全都是1,那么说明极有可能存在。
记住结论：不存在的一定不存在，存在的不一定存在
BlomFilter只能保证过滤掉不包含的元素，而不能保证误判包含。
Bloom filter使用场景：
1. 解决缓存穿透的问题 2. 海量数据下垃圾邮件解决方案（垃圾短信、黑名单建验） 3. 海量去重（爬虫URL去重和分库分表注册手机号唯一性解决方案） 4.SPIN 模型检测器也使用布隆过滤器在大规模验证问题时跟踪可达状态空间。
Bloom filter优缺点：
优点 占用空间小，查询速度快，空间效率和查询时间都远远超过一般的算法 缺点 有一定的误识别率，有一定的误识别率，即某个元素可能存在，但实际上并不存在。 可以添加元素但删除元素困难，因为无法确定某个位置是由哪个元素映射而来的。因为删掉元素会导致误判率增加。
BloomFilter参数取值
假设BloomFilter中元素总bit数量为m（即bit array大小）,插入的元素个数为n，hash函数的个数为k，误判率为p
如果最小化误判率，则k的取值：
而p的取值又和m,n有如下关系：
将m的计算公式带入上式，可得给定n和p，k的取值应为：
如何解决布隆过滤器不支持删除的问题？
Counting Bloom Filter将标准 Bloom Filter位数组的每一位扩展为一个小的计数器（counter），在插入元素时给对应的k（k为哈希函数个数）个Counter的值分别加1，删除元素时给对应的k个Counter的值分别减1。Counting Bloom Filter通过多占用几倍的存储空间的代价，给Bloom Filter增加了删除操作。
