剛接觸編程那會(huì)記得用 Bitmap 的 0 和 1 位來(lái)標(biāo)識(shí)數(shù)據(jù)是否存在，主要用于排序；

后來(lái)發(fā)現(xiàn)只要判斷一個(gè)對(duì)象在大對(duì)象集合存在性，都可以考慮使用 Bitmap；

再后來(lái)，我知道了布隆這個(gè)人使用 Hash 算法結(jié)合 Bitmap 實(shí)現(xiàn)了 BoomFilter，用于海量數(shù)據(jù)處理場(chǎng)景，我覺(jué)得布隆過(guò)濾器在做數(shù)據(jù)過(guò)濾這方面天下無(wú)敵；

后來(lái)的后來(lái)，有人問(wèn)我，布隆過(guò)濾器雖然解決了數(shù)據(jù)過(guò)濾問(wèn)題，但是它不支持?jǐn)?shù)據(jù)修改和刪除，另外如果數(shù)據(jù)稀疏，只有最低位是 1，其它都是 0，還是會(huì)造成資源浪費(fèi)。又該怎么辦呢？

下面結(jié)合自己理解簡(jiǎn)單介紹下 RoaringBitmaps。

RoaringBitmaps

RoaringBitmaps簡(jiǎn)稱 RBM，主要是將 32 位無(wú)符號(hào)整數(shù)按照高 16 位分桶，即最多可能有 2^16=65536 個(gè)桶，論文內(nèi)稱為 container。存儲(chǔ)數(shù)據(jù)時(shí)，按照數(shù)據(jù)的高 16 位找到 container，如果找不到就會(huì)新建一個(gè)，再將低 16 位放入 container 中。也就是說(shuō)，一個(gè) RBM 就是很多 container 的集合。

設(shè)計(jì)思想

RBM 的主要思想并不復(fù)雜，總結(jié)來(lái)說(shuō)，有如下幾點(diǎn)：

• 將 32-bit 的范圍 ([0, n)) 劃分為 2^16 個(gè)桶，每一個(gè)桶有一個(gè) Container 來(lái)存放一個(gè)數(shù)值的低 16 位；

• 在存儲(chǔ)和查詢數(shù)值的時(shí)候，我們將一個(gè)數(shù)值 k 劃分為高 16 位(k % 2^16)和低 16 位(k mod 2^16)，取高 16 位找到對(duì)應(yīng)的桶，然后在低 16 位存放在相應(yīng)的 Container 中；

• 容器的話， RBM 使用三種容器結(jié)構(gòu)：Array Container和 Bitmap Container、RunContainer。Array Container 存放稀疏的數(shù)據(jù)，Bitmap Container 存放稠密的數(shù)據(jù)。即，若一個(gè) Container 里面的 Integer 數(shù)量小于 4096，就用 Short 類型的有序數(shù)組來(lái)存儲(chǔ)值。若大于 4096，就用 Bitmap 來(lái)存儲(chǔ)值；RunContainer 則用于存儲(chǔ)連續(xù)的數(shù)據(jù)。舉個(gè)例子，連續(xù)的整數(shù)序列 11, 12, 13, 14, 15, 27, 28, 29 會(huì)被 RLE 壓縮為兩個(gè)二元組 11, 4, 27, 2，表示 11 后面緊跟著 4 個(gè)連續(xù)遞增的值，27 后面跟著 2 個(gè)連續(xù)遞增的值。

舉例說(shuō)明

 

如上圖，就是官網(wǎng)給出的一個(gè)例子，三個(gè)容器分別代表了三個(gè)數(shù)據(jù)集：

• 第一個(gè) 1000 存儲(chǔ)的是 62 的倍數(shù)
• 第二個(gè)是 1-99 的數(shù)值
• 第三個(gè)存儲(chǔ)的是所有的偶數(shù)

上面這個(gè)例子只是說(shuō)明了通過(guò) RBM 可以對(duì)數(shù)據(jù)進(jìn)行靈活分類，其它的表示形式，你不用較真。另外可能看著上面說(shuō)的高 16 位存儲(chǔ)在數(shù)組中，低 16 位存儲(chǔ)在 Container 中，猛地一看比較迷瞪，我舉個(gè)例子你就明白了。

 

• 821697800 對(duì)應(yīng)的 16 進(jìn)制數(shù)為 30FA1D08， 其中高 16 位為 30FA， 低 16 位為 1D08。

• 先用二分查找從一級(jí)索引（即 Container Array）中找到數(shù)值為 30FA 的容器（如果該容器不存在，則新建一個(gè)），從圖中我們可以看到，該容器是一個(gè) Bitmap 容器。

• 找到了相應(yīng)的容器后，看一下低 16 位的數(shù)值 1D08，它相當(dāng)于是 7432，因此在 Bitmap 中找到相應(yīng)的位置，將其置為 1 即可。

看到這里，你可能仍然會(huì)有疑問(wèn) 一個(gè) Container 里面的 Integer 數(shù)量小于 4096，就用 Short 類型的有序數(shù)組來(lái)存儲(chǔ)值。若大于 4096，就用 Bitmap 來(lái)存儲(chǔ)值。這到底是什么用意呢？

這里之所以使用 4096 這個(gè)閾值，大概因?yàn)?int 的低 16 位是 2Bit， Arrary Container 中的話就是 2Byte * 4096 = 8KB；對(duì)于 Bitmap Container 來(lái)講，2^16 個(gè) bit 也相當(dāng)于是 8KB?；旧暇褪窍嗟靡嬲茫鄬?duì)的分割點(diǎn)。

用過(guò) jdk1.8 HashMap 的都知道在為了對(duì) HashMap 做進(jìn)一步優(yōu)化，引入了紅黑樹(shù)。而當(dāng)鏈表長(zhǎng)度太長(zhǎng)（默認(rèn)超過(guò) 8）時(shí)，鏈表就轉(zhuǎn)換為紅黑樹(shù)。我們可以利用紅黑樹(shù)快速增刪改查的特 點(diǎn)，提高 HashMap 的性能。當(dāng)紅黑樹(shù)結(jié)點(diǎn)個(gè)數(shù)少于 8 個(gè)的時(shí)候，又會(huì)將紅黑樹(shù)轉(zhuǎn)化為鏈 表。因?yàn)樵跀?shù)據(jù)量較小的情況下，紅黑樹(shù)要維護(hù)平衡，比起鏈表來(lái)，性能上的優(yōu)勢(shì)并不明顯。wcc 的，如果不糾結(jié)細(xì)節(jié)問(wèn)題，RPM 的實(shí)現(xiàn)竟然跟 HashMap 設(shè)計(jì)思路這么相似？

操作轉(zhuǎn)換過(guò)程

創(chuàng)建

在創(chuàng)建一個(gè)新container時(shí)，如果只插入一個(gè)元素，RBM默認(rèn)會(huì)用ArrayContainer來(lái)存儲(chǔ)。如果插入的是元素序列的話，則會(huì)先根據(jù)上面的方法計(jì)算ArrayContainer和RunContainer的空間占用大小，并選擇較小的那一種進(jìn)行存儲(chǔ)。

查找

在查找一個(gè)元素的時(shí)候，先二分算法查找高16位的ArrayContainer，如果存在且數(shù)據(jù)量低于4096，繼續(xù)二分查找特定定數(shù)據(jù)，否則使用位運(yùn)算。增刪改查的時(shí)間復(fù)雜度方面，BitmapContainer只涉及到位運(yùn)算，顯然為O(1)。而ArrayContainer和RunContainer都需要用二分查找在有序數(shù)組中定位元素，故為O(logN)。

轉(zhuǎn)換

仔細(xì)閱讀文章的話，你可能還有疑問(wèn)，剛開(kāi)始的時(shí)候只插入一個(gè)元素，那肯定是ArrayContainer，隨著后面數(shù)據(jù)量增多了，怎么又有了后面的BitMapContainer？那是因?yàn)檫@個(gè)算法本身支持轉(zhuǎn)換,具體請(qǐng)看下文解釋。

當(dāng)ArrayContainer的容量超過(guò)4096后，會(huì)自動(dòng)轉(zhuǎn)成BitmapContainer存儲(chǔ)。4096是一個(gè)閾值，低于它時(shí) ArrayContainer比較省空間，高于它時(shí)BitmapContainer也比較省空間。也就是說(shuō)ArrayContainer存儲(chǔ)稀疏數(shù)據(jù)，BitmapContainer存儲(chǔ)稠密數(shù)據(jù)，可以最大限度地避免內(nèi)存浪費(fèi)。

RBM可以通過(guò)調(diào)用特定的API（名為optimize）比較ArrayContainer/BitmapContainer與等價(jià)的 RunContainer的內(nèi)存占用情況，一旦RunContainer占用較小，就轉(zhuǎn)換。也就是說(shuō)，上圖例子中的第二個(gè)ArrayContainer 可以轉(zhuǎn)化為只有一個(gè)二元組0, 100的RunContainer，占用空間進(jìn)一步下降到10200字節(jié)。

當(dāng)然里面還涉及到多個(gè)Container之間的比較、合并等運(yùn)算，例如：兩個(gè)RBM做集合操作時(shí)，不同種類container之間位運(yùn)算的處理方式，如ArrayContainer AND BitmapContainer，BitmapContainer OR RunContainer等；32位有時(shí)會(huì)不夠用時(shí)需要對(duì)64位整數(shù)的支持；能夠?qū)BM數(shù)據(jù)寫(xiě)到堆外，即內(nèi)存映射；支持Kryo序列化等方式。這里面涉及到很多位移運(yùn)算，復(fù)雜的一批，我也沒(méi)搞明白。