http://content.research.neustar.biz/blog/hll.html
image.png
| 算法 | 算法简介 | 精准度 | 可删除 | 详细介绍 | 存储比较 |
|---|---|---|---|---|---|
| 布隆过滤 | Bloom Filter使用了k个哈希函数(源代码只用一个hash函数,见下文)，每个字符串跟k个bit对应。从而降低了冲突的概率 | 非精准，存在误判 | 删除困难 | https://www.jianshu.com/p/c427f797d003 | 空间相对较低 |
| HLL | Cardinality Estimation 基数估计算法 |
非精准估计,以下为register 的存储逻辑 1. 精确存储EXPLICIT，基于long 的hashset new LongOpenHashSet 2. SPARSE:稀疏类型，因为数据量不是很大时，大部分的桶为空，为节省空间，则只保存有值的桶new Int2ByteOpenHashMap 3.FULL:当大部分的桶有值时,用位向量来保存所有的桶的内容,以节省空间 new BitVector |
无法删除 | https://www.jianshu.com/p/27d9a7912fce | 非精准条件下较低 |
| 精确去重和Roaring BitMap | Roaring BitMap 以下简称 RBM,中文翻译为咆哮位图,它本质上是定义了一个很大的 bit 数组，每个元素对应到 bit 数组的其中一位，一个Integer是32-bit, 一共有Integer.MAX_VALUE = 2 ^ 32个值，32-bit的unsigned integer的集合(共2 ^ 32 = 42 9496 7296个) | 精准 1. short[] keys = null;//高16位数组 有序数组，方便二分查找 2. Container[] values = null;//低16位容器数组 2.1ArrayContainer 2.2BitmapContainer Array在4096后升级 2.3RunContainer |
可删除 | https://www.jianshu.com/p/b09bb3e7652e | 精准条件下最低 |
网友评论