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

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

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

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

下面結合自己理解簡單介紹下 RoaringBitmaps。

RoaringBitmaps

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

設計思想

RBM 的主要思想并不復雜，總結來說，有如下幾點：

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

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

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

舉例說明

 

如上圖，就是官網給出的一個例子，三個容器分別代表了三個數據集：

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

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

 

• 821697800 對應的 16 進制數為 30FA1D08， 其中高 16 位為 30FA， 低 16 位為 1D08。

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

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

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

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

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

操作轉換過程

創建

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

查找

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

轉換

仔細閱讀文章的話，你可能還有疑問，剛開始的時候只插入一個元素，那肯定是ArrayContainer，隨著后面數據量增多了，怎么又有了后面的BitMapContainer？那是因為這個算法本身支持轉換,具體請看下文解釋。

當ArrayContainer的容量超過4096后，會自動轉成BitmapContainer存儲。4096是一個閾值，低于它時 ArrayContainer比較省空間，高于它時BitmapContainer也比較省空間。也就是說ArrayContainer存儲稀疏數據，BitmapContainer存儲稠密數據，可以最大限度地避免內存浪費。

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

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