假如我们使用Bitmap(或称BitSet)储存,定义一个很大的bitmap数组,每个元素对应Bitmap中的1位。
初始数组都是0,每个原始在数组中的index位置标识为1.
估算示例:
(1)若有10^9 个元素,即10亿,则占用的内存为120M 。(10^9/8/1024/1024=120M)
(2)所有2^32个元素,约43亿,则占用内存为512M 。 (2^32/8/1023/1024=512M)
注: Integer.Max_value=2^32;
场景分析:
某电商平台,要分析每个商品的UV,可能涉及到不同维度组合的商品UV统计,到底需要定义多少以及多大的BitMap去存储呢?
首先,商品有热们和冷门之分,热门的UV可能比较多,冷门的可能寥寥无几。另外时间维度可能有分/时/天/周/月等等,还有渠道维度等等,用户的需求可能基于多个维度组合统计。这个给计算带来很大的挑战,是否有一种动态的内存分配方案,更好的利用内存资源呢?
答案是: 使用RoaringBitmap 。
RoaringBitmap
RoaringBitmap 跟JDK1.8 currentHashMap的思路有点像,如当hash冲突时,如果链表节点个数>8个,则转化为红黑二叉树存储。如果<6则自动转化为普通链表存储。
它将一个32位的Integer 分为高16位和低16位,前者用于创建桶,总计 2^16 个桶 short[],没有则创建一个。(把它理解为index索引桶也行,后者作为value,放入该桶中。高16位相同的数据在同一个桶中values[] ;
即
> 将一个数值 k 划分为高 16 位(k % 2^16)和低 16 位(k mod 2^16),取高 16 位找到对应的桶,然后在低 16 位存放在相应的 Container 中;
在这里,RoaringBitmap 也会根据一个阈值4096,
若元素数量<4096则使用ArrrayContainer储存;
若元素数量>4096则使用BitmapContainer储存;
ArrrayContainer 和 BitmapContainer 区别
ArrayContainer :存储稀疏少量的数据。
BitmapContainer: 存储稠密的数据 (占用内存始终是8kb)
这里有个问题:上面假设存放的Integer类型,那非Integer类型如何存储?
答:需要建立一个非Integer类型到数值类型的映射关系表。
网友评论