BitMap(位图)就是用一个bit位来标记某个元素所对应的value，而key即是该元素，由于BitMap使用了bit位来存储数据，因此可以大大节省存储空间。BitMap解决海量数据寻找重复、判断个别元素是否在海量数据当中等问题
1.1 基本思路
假设我们要对0-7内的5个元素(4,7,2,5,3)进行排序(这里假设元素没有重复)。我们可以使用BitMap算法达到排序目的。要表示8个数，我们需要8个byte。
1. 首先我们开辟一个字节(8bit)的空间，将这些空间的所有的bit位都设置为0
2. 然后遍历这5个元素，第一个元素是4，因为下边从0开始，因此我们把第五个字节的值设置为1
3. 然后再处理剩下的四个元素，最终一个字节的状态如下图
4. 现在我们遍历一次byte区域，把值为1的bit的位置输出(2,3,4,5,7)，这样便达到了排序的目的
从上面的例子我们可以看出，BitMap算法的思想还是比较简单的，关键的问题是如何确定10进制的数到2进制的映射图
1.2 MAP映射：
假设需要排序或则查找的数的总数N=100000000，BitMap中1bit代表一个数字，1个int = 4Bytes = 4*8bit = 32 bit,那么N个数需要N/32 int空间。所以我们需要申请内存空间的大小为int a[1 + N/32]，其中：a[0]在内存中占32为可以对应十进制数0-31，依次类推：
a[0]-----------------------------> 0-31
a[1]------------------------------> 32-63
a[2]-------------------------------> 64-95
a[3]--------------------------------> 96-127
a[n]--------------------------------> n32 - n32+31
那么十进制数如何转换为对应的bit位，下面介绍用位移将十进制数转换为对应的bit位:
1. 求十进制数在对应数组a中的下标
十进制数0-31，对应在数组a[0]中，32-63对应在数组a[1]中，64-95对应在数组a[2]中………，使用数学归纳分析得出结论：对于一个十进制数n，其在数组a中的下标为：a[n/32]
2. 求出十进制数在对应数a[i]中的下标
例如十进制数1在a[0]的下标为1，十进制数31在a[0]中下标为31，十进制数32在a[1]中下标为0。 在十进制0-31就对应0-31，而32-63则对应也是0-31，即给定一个数n可以通过模32求得在对应数组a[i]中的下标。
3. 位移
对于一个十进制数n,对应在数组a[n/32][n%32]中，但数组a毕竟不是一个二维数组，我们通过移位操作实现置1
a[n/32] |= 1 << n % 32
移位操作：a[n>>5] |= 1 << (n & 0x1F)
n & 0x1F 保留n的后五位 相当于 n % 32 求十进制数在数组a[i]中的下标
1.3 代码实现（golang）：
package main
import "fmt"
func main() {
m := NewBmap()
m.Add(1)
m.Add(32)
fmt.Println(m.Has(1))
m.Print()
}
type Bitmap struct {
partition []uint32 //分区 ， uint32 是4字节，32位， 每一分区支持32个连续数据
length int //已存放个数
}
func NewBmap() *Bitmap {
return &Bitmap{}
}
func (bitmap *Bitmap) Has(num int) bool {
word, bit := num/64, uint(num%32)
return word < len(bitmap.partition) && (bitmap.partition[word]&(1<<bit)) != 0
}
func (bitmap *Bitmap) Add(num int) {
partition := num / 32 //取整除后得到分区号
bit := uint(num % 32) //取余，得到分区位置
for partition >= len(bitmap.partition) {
//分区号超出现有分区，则新开分区
bitmap.partition = append(bitmap.partition, 0)
}
if bitmap.partition[partition]&(1<<bit) == 0 {
// 判断分区中没有则添加
bitmap.partition[partition] |= 1 << bit
bitmap.length++
}
}
func (bitmap *Bitmap) Len() int {
return bitmap.length
}
func (bitmap *Bitmap) Print() {
for i, v := range bitmap.partition {
fmt.Printf("%d-----------%d ", i*32, i*32+31)
for j := 0; j < 32; j++ {
fmt.Print((v & (1 << j)) >> j)
}
fmt.Println()
}
}
1.4 局限性
bitmap 适用于数据较为密集的时候，但是对于稀疏数据的话， bitmap 存在存储空间的浪费，
举个例子：若只存放0～40亿中的第40亿的数据，此时前面的存储空间白白浪费了
为了解决位图在稀疏数据下的问题，目前有多种压缩方案以减少内存提高效率：WAH、EWAH、CONCISE、RoaringBitmap等。前三种采用行程长度编码（Run-length-encoding）进行压缩，RoaringBitmap则是在压缩上更进一步，并且兼顾了性能
2. RoaringBitmap
roaringbitmap 简称RBM，属于是bitmap的一个进化，即压缩位图，不过在roaringbitmap中不只包含bitmap这一种数据结构，而是包涵了多种存储的方式，以此来达到压缩位图的目的
2.1 工作原理
- 将 32bit int（无符号的）类型数据 划分为 2^16 个桶（即使用数据的前16位二进制作为桶的编号），每个桶有一个Container 来存放一个数值的低16位。
-
在存储和查询数值时，将数值 k 划分为高 16 位和低 16 位，取高 16 位值找到对应的桶，然后在将低 16 位值存放在相应的 Container (小桶)中。
2.2 Container
在roaringbitmap中共有4种Container：arraycontainer(数组容器)，bitmapcontainer(位图容器)，runcontainer(行程步长容器)，sharedcontainer(共享容器)
-
arraycontainer(数组容器)
在创建一个新container时，如果只插入一个元素，RBM（roaringbitmap）默认会用ArrayContainer来存储。当ArrayContainer（其中每一个元素的类型为 short int 占两个字节,且里面的元素都是按从大到小的顺序排列的）的容量超过4096（这里是指4096个short int即8k）后，会自动转成BitmapContainer(这个所占空间始终都是8k)存储。4096这个阈值很聪明，低于它时ArrayContainer比较省空间，高于它时BitmapContainer比较省空间。也就是说ArrayContainer存储稀疏数据，BitmapContainer存储稠密数据，可以最大限度地避免内存浪费。下面这个图可以很清楚的看懂这种关系
-
bitmapcontainer(位图容器)
这个容器其实就是我们最开讲的位图，只不过这里位图的位数为2^16（65536）个，也就是2 ^ 16个bit,计算下来起所占内存就是8kb。然后每一位用0，1表示这个数不存在或者存在
-
runcontainer(行程步长容器)
这是一种利用步长来压缩空间的方法
比如连续的整数序列 11, 12, 13, 14, 15, 27, 28, 29 会被压缩为两个二元组 11, 4, 27, 2 表示：11后面紧跟着4个连续递增的值，27后面跟着2个连续递增的值，那么原先16个字节的空间，现在只需要8个字节，是不是节省了很多空间呢。不过这种容器不常用，所以在使用的时候需要我们自行调用相关的转换函数来判断是不是需要将arraycontiner，或bitmapcontainer转换为runcontainer
-
sharedcontainer(共享容器)
这种容器它本身是不存储数据的，只是用它来指向 arraycontainer,bitmapcontainer或runcontainer,就好比指针的作用一样，这个指针可以被多个对象拥有，但是指针所指针的实质东西是被这多个对象所共享的。在我们进行roaringbitmap之间的拷贝的时候，有时并不需要将一个container拷贝多份，那么我们就可以使用sharedcontainer来指向实际的container，然后把sharedcontainer赋给多个roaringbitmap对象持有，这个roaringbitmap对象就可以根据sharedcontainer找到真正存储数据的container,这可以省去不必要的空间浪费
这些container之间的关系可以用下面这幅图来表示：
参考：
https://www.cnblogs.com/senlinyang/p/7885685.html
https://blog.csdn.net/tonywu1992/article/details/104746214/
https://zhuanlan.zhihu.com/p/351365841
网友评论