Redis源码中hyperloglog结构的实现原理是啥( 九 )
在计算近似基数时，就分别计算每个桶中的值，带入到上文将的 DV 公式中，进行调和平均和结果修正，就能得到估算的基数值。
HyperLogLog 对象中的 registers 数组就是桶，它有两种存储结构，分别为密集存储结构和稀疏存储结构，两种结构只涉及存储和桶的表现形式，从中我们可以看到 Redis 对节省内存极致地追求。
我们先看相对简单的密集存储结构，它也是十分的简单明了，既然要有 2^14 个 6 bit的桶，那么我就真使用足够多的 uint8_t 字节去表示，只是此时会涉及到字节位置和桶的转换，因为字节有 8 位，而桶只需要 6 位。
所以我们需要将桶的序号转换成对应的字节偏移量 offsetbytes 和其内部的位数偏移量 offsetbits。需要注意的是小端字节序，高位在右侧，需要进行倒转。
当 offset_bits 小于等于2时，说明一个桶就在该字节内，只需要进行倒转就能得到桶的值。
如果 offset_bits 大于 2 ，则说明一个桶分布在两个字节内，此时需要将两个字节的内容都进行倒置，然后再进行拼接得到桶的值，如下图所示。
HyperLogLog 的稀疏存储结构是为了节约内存消耗，它不像密集存储模式一样，真正找了那么多个字节数组来表示2^14 个桶，而是使用特殊的字节结构来表达。
Redis 为了方便表达稀疏存储，它将上面三种字节表示形式分别赋予了一条指令。
ZERO : 一字节，表示连续多少个桶计数为0，前两位为标志00，后6位表示有多少个桶，最大为64。XZERO : 两个字节，表示连续多少个桶计数为0，前两位为标志01，后14位表示有多少个桶，最大为16384。VAL : 一字节，表示连续多少个桶的计数为多少，前一位为标志1，四位表示连桶内计数，所以最大表示桶的计数为32。后两位表示连续多少个桶。
所以，一个初始状态的 HyperLogLog 对象只需要2 字节，也就是一个 XZERO 来存储其数据，而不需要消耗12K 内存。当 HyperLogLog 插入了少数元素时，可以只使用少量的 XZERO、VAL 和 ZERO 进行表示，如下图所示。
Redis从稀疏存储转换到密集存储的条件是：
任意一个计数值从 32 变成 33，因为 VAL 指令已经无法容纳，它能表示的计数值最大为 32稀疏存储占用的总字节数超过 3000 字节，这个阈值可以通过 hllsparsemax_bytes 参数进行调整。具体 Redis 中的 HyperLogLog 源码由于涉及较多的位运算，这里就不多带大家学习了。大家对 HyperLogLog 有什么更好的理解或者问题都欢迎积极留言。
■网友
通俗来说，HLL做的就是统计一个表、序列或者其他可包含重复元素的结构中不同元素近似个数的方法，即approx_count(distinct xxx)。
推荐阅读
- microsoft redistributable为啥不做成一个带可选项的程序
- 网站完整源码能有途径获取吗
- cygwin下源码编译openssl出错
- redis中的hset怎样快速地找到最大key或最大value，有办法快速地知道一个hset中key的个数 或 value的个数吗
- 怎样借助 redis 进行内容的排序，并将关注的 feed 流推送进来，聚合在一起，显示出来
- 有关JDK源码中一些元素类型在方法实现方面的效率问题请大牛们指点迷津一下，谢谢！?
- wordpress首页文章摘要字数设置具体源码在文中！求大神！
- 开发一个网站的价格，做一个网站要多少钱，需要源码的呢
- 写一个类，让toString()输出这个类的源码
- 如果让一个程序随机的修改自己源码无限制的编译且复制自身，是否有一日会出现一个完善的人工智能