数据结构-RoaringBitmap概要

1.Bitmap

Bitmap索引在数据库和搜索引擎里使用的很广泛，
BitMap使用bit位，来标记元素对应的Value， 而Key即是该元素
 Bitmap索引一般用来存储整数。整数的范围是0～2^32-1
 bitmap算法- 精确去重算法主要通过BitMap来实现，它本质上是定义了一个很大的 bit 数组，每个元素对应到 bit 数组的其中一位

2.RoaringBitmap

RoaringBitmap中，32位整数被分成了2^16个块。
      任何一个32位整数的
         前16位决定放在哪个块里
         后16位就是放在这个块里的内容
对于非Integer类型的数据(比如String类型)，可以通过数据字典映射成Integer

3.开源的源代码

org.roaringbitmap.RoaringBitmap;
RoaringArray highLowContainer;  
//RoaringBitmap中都包含一个 RoaringArray 名字叫 highLowContainer 。 
//highLowContainer 存储了 RoaringBitmap 中的全部数据

short[] keys;      //高16位会被作为key存储到, //keys数组永远保持有序，方便二分查找，且不会存储重复数值
Container[] values;//低16位则被看做value
int size;          //size则标示了当前包含的key-value pair的数量，即keys和values中有效数据的数量

02. Roaring bitmap共有三种不同类型的Container, 分别是Array Container, Bitmap Container, Run Container.
   ArrayContainer   <= 4096 elements:
      数组的初始长度为DEFAULT_INIT_SIZE = 4，扩容的规则
      不会分配超过DEFAULT_MAX_SIZE = 4096大小的capacity
   BitmapContainer  >= 61140 elements:
   RunContainer      others
03.主要的操作
    主要使用 add remove
          and or xor 
         serialize deserialize 等操作

4.使用示例

01.maven依赖
  <!-- https://mvnrepository.com/artifact/org.roaringbitmap/RoaringBitmap -->
 <dependency>
     <groupId>org.roaringbitmap</groupId>
     <artifactId>RoaringBitmap</artifactId>
     <version>0.8.6</version>
 </dependency>

02.代码
import org.roaringbitmap.RoaringBitmap;

public class ResBitMap {
public static void main(String[] args){
    //向rr中添加1、2、3、1000四个数字
    RoaringBitmap rr = RoaringBitmap.bitmapOf(1,2,3,1000);
    //创建RoaringBitmap rr2
    RoaringBitmap rr2 = new RoaringBitmap();
    //向rr2中添加10000-12000共2000个数字
    rr2.add(10000L,12000L);
    //返回第3个数字是1000，第0个数字是1，第1个数字是2，则第3个数字是1000
    System.out.println(rr.select(3));
    //返回value = 2 时的索引为 1。value = 1 时，索引是 0 ，value=3的索引为2
    System.out.println( rr.rank(2));
    //判断是否包含1000
    System.out.println( rr.contains(1000));
    //判断是否包含7 // will return false
    System.out.println( rr.contains(7));

    //两个RoaringBitmap进行or操作，数值进行合并，合并后产生新的RoaringBitmap叫rror
    RoaringBitmap rror = RoaringBitmap.or(rr, rr2);
    //rr与rr2进行位运算，并将值赋值给rr
    rr.or(rr2);
    //判断rror与rr是否相等，显然是相等的
    boolean equals = rror.equals(rr);
    if(!equals) {throw new RuntimeException("bug");}
    // 查看rr中存储了多少个值，1,2,3,1000和10000-12000，共2004个数字
    long cardinality = rr.getLongCardinality();
    System.out.println(cardinality);
    //遍历rr中的value
    for(int i : rr) {
        System.out.println(i);
    }
  }
}

其他

01.BitMap 运营分析-任意两天的重叠活跃用户
 对不同日期活跃用户ID进行bitmap编码和计算的
 获取过去1天的日活跃用户bitmap和今天的bitmap,对它们做并集(Union)，and等操作
Bitmap和布隆过滤器(Bloom Filter)两个算法，对于空间的利用到达了一种极致
02.布隆过滤器就是引入了k(k>1) k(k>1)k(k>1)个相互独立的哈希函数，保证在给定的空间、误判率下，完成元素判重的过程，适合与比Bitmap更多量的数据 .stat()
 DataFrameStatFunctions
   bloomFilter    布隆过滤器
   countMinSketch   算法Count-Min Sketch
   corr ： 计算the Pearson Correlation Coefficient of two columns of a DataFrame.
 03. HyperLogLog算法经常在数据库中被用来统计某一字段的Distinct Value -- 在需要对数据进行去重计数的场景里
 JavaRDDLike  countApproxDistinct
  def countApproxDistinct(relativeSD: Double): Long = rdd.countApproxDistinct(relativeSD)。
 It must be greater than 0.000017.
 统计是一个大约的统计，参数relativeSD控制统计的精确度。relativeSD越小，结果越准确
 APPROX_COUNT_DISTINCT

5.参考：

 BitMap、RoaringBitmap与JavaEWAH https://www.cnblogs.com/fonxian/p/10937882.html
 精确去重和Roaring BitMap https://blog.csdn.net/hfcenter/article/details/95458754
 Filter 过滤 http://muziyuchen.com/spark-ii-14/
 http://dyingbleed.com/ 李震的个人博客
 BitMap与RoaringBitmap、JavaEWAH https://blog.csdn.net/weixin_42142408/article/details/89426499

blogroll

social