十年网站开发经验 + 多家企业客户 + 靠谱的建站团队
量身定制 + 运营维护+专业推广+无忧售后,网站问题一站解决
RoaringBitmaps的设计原理是什么,相信很多没有经验的人对此束手无策,为此本文总结了问题出现的原因和解决方法,通过这篇文章希望你能解决这个问题。
创新互联公司为您提适合企业的网站设计 让您的网站在搜索引擎具有高度排名,让您的网站具备超强的网络竞争力!结合企业自身,进行网站设计及把握,最后结合企业文化和具体宗旨等,才能创作出一份性化解决方案。从网站策划到成都网站建设、网站设计, 我们的网页设计师为您提供的解决方案。
刚接触编程那会记得用 Bitmap 的 0 和 1 位来标识数据是否存在,主要用于排序;
后来发现只要判断一个对象在大对象集合存在性,都可以考虑使用 Bitmap;
再后来,我知道了布隆这个人使用 Hash 算法结合 Bitmap 实现了 BoomFilter,用于海量数据处理场景,我觉得布隆过滤器在做数据过滤这方面天下无敌;
后来的后来,有人问我,布隆过滤器虽然解决了数据过滤问题,但是它不支持数据修改和删除,另外如果数据稀疏,只有最低位是 1,其它都是 0,还是会造成资源浪费。又该怎么办呢?
下面结合自己理解简单介绍下 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 个连续递增的值。
如上图,就是官网给出的一个例子,三个容器分别代表了三个数据集:
上面这个例子只是说明了通过 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的设计原理是什么的方法了吗?如果还想学到更多技能或想了解更多相关内容,欢迎关注创新互联行业资讯频道,感谢各位的阅读!