RoaringBitmaps的設(shè)計(jì)原理是什么

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

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

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

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

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

RoaringBitmaps

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

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

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

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

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

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

舉例說明

 

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

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

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

 

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

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

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

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

這里之所以使用 4096 這個閾值，大概因?yàn)?int 的低 16 位是 2Bit， Arrary Container 中的話就是 2Byte * 4096 = 8KB；對于 Bitmap Container 來講，2^16 個 bit 也相當(dāng)于是 8KB。基本上就是相得益彰，相對的分割點(diǎn)。

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

操作轉(zhuǎn)換過程

創(chuàng)建

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

查找

在查找一個元素的時(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ì)閱讀文章的話，你可能還有疑問，剛開始的時(shí)候只插入一個元素，那肯定是ArrayContainer，隨著后面數(shù)據(jù)量增多了，怎么又有了后面的BitMapContainer？那是因?yàn)檫@個算法本身支持轉(zhuǎn)換,具體請看下文解釋。

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

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

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