RoaringBitmaps的设计原理是什么

蜗牛vps互联网技术资讯2021-12-032680

RoaringBitmaps的设计原理是什么，相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。

刚接触编程那会记得用 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序列化等方式。这里面涉及到很多位移运算，复杂的一批，我也没搞明白。

看完上述内容，你们掌握RoaringBitmaps的设计原理是什么的方法了吗？如果还想学到更多技能或想了解更多相关内容，欢迎关注蜗牛博客行业资讯频道，感谢各位的阅读！

免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：niceseo99@gmail.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。