BitMap(位圖)就是用一個bit位來標(biāo)記某個元素所對應(yīng)的value，而key即是該元素褥蚯，由于BitMap使用了bit位來存儲數(shù)據(jù)挚冤，因此可以大大節(jié)省存儲空間。BitMap解決海量數(shù)據(jù)尋找重復(fù)赞庶、判斷個別元素是否在海量數(shù)據(jù)當(dāng)中等問題
1.1 基本思路
假設(shè)我們要對0-7內(nèi)的5個元素(4,7,2,5,3)進(jìn)行排序(這里假設(shè)元素沒有重復(fù))训挡。我們可以使用BitMap算法達(dá)到排序目的。要表示8個數(shù)歧强，我們需要8個byte澜薄。
1. 首先我們開辟一個字節(jié)(8bit)的空間，將這些空間的所有的bit位都設(shè)置為0
2. 然后遍歷這5個元素摊册，第一個元素是4肤京，因為下邊從0開始，因此我們把第五個字節(jié)的值設(shè)置為1
3. 然后再處理剩下的四個元素茅特，最終一個字節(jié)的狀態(tài)如下圖
4. 現(xiàn)在我們遍歷一次byte區(qū)域忘分，把值為1的bit的位置輸出(2,3,4,5,7)，這樣便達(dá)到了排序的目的
從上面的例子我們可以看出白修，BitMap算法的思想還是比較簡單的妒峦，關(guān)鍵的問題是如何確定10進(jìn)制的數(shù)到2進(jìn)制的映射圖
1.2 MAP映射：
假設(shè)需要排序或則查找的數(shù)的總數(shù)N=100000000，BitMap中1bit代表一個數(shù)字熬荆，1個int = 4Bytes = 4*8bit = 32 bit,那么N個數(shù)需要N/32 int空間舟山。所以我們需要申請內(nèi)存空間的大小為int a[1 + N/32]，其中：a[0]在內(nèi)存中占32為可以對應(yīng)十進(jìn)制數(shù)0-31卤恳，依次類推：
a[0]-----------------------------> 0-31
a[1]------------------------------> 32-63
a[2]-------------------------------> 64-95
a[3]--------------------------------> 96-127
a[n]--------------------------------> n32 - n32+31
那么十進(jìn)制數(shù)如何轉(zhuǎn)換為對應(yīng)的bit位累盗，下面介紹用位移將十進(jìn)制數(shù)轉(zhuǎn)換為對應(yīng)的bit位:
1. 求十進(jìn)制數(shù)在對應(yīng)數(shù)組a中的下標(biāo)
十進(jìn)制數(shù)0-31，對應(yīng)在數(shù)組a[0]中突琳，32-63對應(yīng)在數(shù)組a[1]中若债，64-95對應(yīng)在數(shù)組a[2]中………，使用數(shù)學(xué)歸納分析得出結(jié)論：對于一個十進(jìn)制數(shù)n拆融，其在數(shù)組a中的下標(biāo)為：a[n/32]
2. 求出十進(jìn)制數(shù)在對應(yīng)數(shù)a[i]中的下標(biāo)
例如十進(jìn)制數(shù)1在a[0]的下標(biāo)為1蠢琳，十進(jìn)制數(shù)31在a[0]中下標(biāo)為31啊终，十進(jìn)制數(shù)32在a[1]中下標(biāo)為0。 在十進(jìn)制0-31就對應(yīng)0-31傲须，而32-63則對應(yīng)也是0-31蓝牲，即給定一個數(shù)n可以通過模32求得在對應(yīng)數(shù)組a[i]中的下標(biāo)。
3. 位移
對于一個十進(jìn)制數(shù)n,對應(yīng)在數(shù)組a[n/32][n%32]中泰讽，但數(shù)組a畢竟不是一個二維數(shù)組例衍，我們通過移位操作實現(xiàn)置1
a[n/32] |= 1 << n % 32
移位操作：a[n>>5] |= 1 << (n & 0x1F)
n & 0x1F 保留n的后五位 相當(dāng)于 n % 32 求十進(jìn)制數(shù)在數(shù)組a[i]中的下標(biāo)
1.3 代碼實現(xiàn)（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 //分區(qū) ， uint32 是4字節(jié)已卸，32位佛玄， 每一分區(qū)支持32個連續(xù)數(shù)據(jù)
length int //已存放個數(shù)
}
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 //取整除后得到分區(qū)號
bit := uint(num % 32) //取余，得到分區(qū)位置
for partition >= len(bitmap.partition) {
//分區(qū)號超出現(xiàn)有分區(qū)累澡，則新開分區(qū)
bitmap.partition = append(bitmap.partition, 0)
}
if bitmap.partition[partition]&(1<<bit) == 0 {
// 判斷分區(qū)中沒有則添加
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 適用于數(shù)據(jù)較為密集的時候梦抢，但是對于稀疏數(shù)據(jù)的話， bitmap 存在存儲空間的浪費愧哟，
舉個例子：若只存放0～40億中的第40億的數(shù)據(jù)奥吩，此時前面的存儲空間白白浪費了
為了解決位圖在稀疏數(shù)據(jù)下的問題，目前有多種壓縮方案以減少內(nèi)存提高效率：WAH翅雏、EWAH圈驼、CONCISE、RoaringBitmap等望几。前三種采用行程長度編碼（Run-length-encoding）進(jìn)行壓縮绩脆，RoaringBitmap則是在壓縮上更進(jìn)一步，并且兼顧了性能
2. RoaringBitmap
roaringbitmap 簡稱RBM橄抹，屬于是bitmap的一個進(jìn)化靴迫，即壓縮位圖，不過在roaringbitmap中不只包含bitmap這一種數(shù)據(jù)結(jié)構(gòu)楼誓，而是包涵了多種存儲的方式玉锌，以此來達(dá)到壓縮位圖的目的
2.1 工作原理
- 將 32bit int（無符號的）類型數(shù)據(jù) 劃分為 2^16 個桶（即使用數(shù)據(jù)的前16位二進(jìn)制作為桶的編號），每個桶有一個Container 來存放一個數(shù)值的低16位疟羹。
-
在存儲和查詢數(shù)值時主守，將數(shù)值 k 劃分為高 16 位和低 16 位，取高 16 位值找到對應(yīng)的桶榄融，然后在將低 16 位值存放在相應(yīng)的 Container (小桶)中参淫。
2.2 Container
在roaringbitmap中共有4種Container：arraycontainer(數(shù)組容器)，bitmapcontainer(位圖容器)愧杯，runcontainer(行程步長容器)涎才，sharedcontainer(共享容器)
-
arraycontainer(數(shù)組容器)
在創(chuàng)建一個新container時，如果只插入一個元素力九，RBM（roaringbitmap）默認(rèn)會用ArrayContainer來存儲耍铜。當(dāng)ArrayContainer（其中每一個元素的類型為 short int 占兩個字節(jié),且里面的元素都是按從大到小的順序排列的）的容量超過4096（這里是指4096個short int即8k）后邑闺，會自動轉(zhuǎn)成BitmapContainer(這個所占空間始終都是8k)存儲。4096這個閾值很聰明棕兼，低于它時ArrayContainer比較省空間陡舅，高于它時BitmapContainer比較省空間。也就是說ArrayContainer存儲稀疏數(shù)據(jù)伴挚，BitmapContainer存儲稠密數(shù)據(jù)蹭沛，可以最大限度地避免內(nèi)存浪費。下面這個圖可以很清楚的看懂這種關(guān)系
-
bitmapcontainer(位圖容器)
這個容器其實就是我們最開講的位圖章鲤，只不過這里位圖的位數(shù)為2^16（65536）個，也就是2 ^ 16個bit,計算下來起所占內(nèi)存就是8kb咆贬。然后每一位用0败徊，1表示這個數(shù)不存在或者存在
runcontainer(行程步長容器)
這是一種利用步長來壓縮空間的方法
比如連續(xù)的整數(shù)序列 11, 12, 13, 14, 15, 27, 28, 29 會被壓縮為兩個二元組 11, 4, 27, 2 表示：11后面緊跟著4個連續(xù)遞增的值，27后面跟著2個連續(xù)遞增的值掏缎，那么原先16個字節(jié)的空間皱蹦，現(xiàn)在只需要8個字節(jié)，是不是節(jié)省了很多空間呢眷蜈。不過這種容器不常用沪哺，所以在使用的時候需要我們自行調(diào)用相關(guān)的轉(zhuǎn)換函數(shù)來判斷是不是需要將arraycontiner，或bitmapcontainer轉(zhuǎn)換為runcontainer
-
sharedcontainer(共享容器)
這種容器它本身是不存儲數(shù)據(jù)的酌儒，只是用它來指向 arraycontainer,bitmapcontainer或runcontainer,就好比指針的作用一樣辜妓，這個指針可以被多個對象擁有，但是指針?biāo)羔樀膶嵸|(zhì)東西是被這多個對象所共享的忌怎。在我們進(jìn)行roaringbitmap之間的拷貝的時候籍滴，有時并不需要將一個container拷貝多份，那么我們就可以使用sharedcontainer來指向?qū)嶋H的container榴啸，然后把sharedcontainer賦給多個roaringbitmap對象持有孽惰，這個roaringbitmap對象就可以根據(jù)sharedcontainer找到真正存儲數(shù)據(jù)的container,這可以省去不必要的空間浪費
這些container之間的關(guān)系可以用下面這幅圖來表示：
參考：
https://www.cnblogs.com/senlinyang/p/7885685.html
https://blog.csdn.net/tonywu1992/article/details/104746214/
https://zhuanlan.zhihu.com/p/351365841
