一、什么是 HyperLogLog ？什么用途？什么特点？
- HyperLogLog 本质上是
一种算法，它提供了不精确（大概0.81%错误）的去重计数方法。 - 用途：
计数，比如统计网页的UV (unique visitor)； - 特点：能够在
不保存数据的情况下进行去重计数，最多耗费12K的内存便可以对大量数据进行计数。
举个例子来说明为什么要使用 HyperLogLog 算法进行计数：
假如需要去统计某网页的 UV:UV 的 全称是unique visitor，指访问用户去重数，一天内同一个用户多次访问只能算一次，通常和 PV (page view，页面访问次数) 一起来表示一个网站的日活程度。
传统的解决方案：基于集合Set 不包含重复元素的特性，使用 Set 来保存用户 id，然后统计 Set 中的元素数量来获取页面 UV。由于 Set 需要放在内存中，因此这种方案只能承载少量用户，一旦用户数量大起来就需要消耗大量的内存用来存储用户 id。但是实际上我们的目的是要统计用户数量而不是保存用户本身，因此这是个吃力不讨好的方案！
HyperLogLog 方案：该方案最多需要 12K 的内存就可以统计大量的用户数，大概 0.81% 的错误率对于 UV 统计来说是可以忽略不计的。
因此 HyperLogLog 算法非常适合
二、HyperLogLog 原理
2.1 基数
基数是指不重复元素的个数，比如一个 列表 {1,2,3,4,5,6,7,6,8} 的基数是8。
2.2 HyperLogLog 原理
HyperLogLog 可以仅仅使用12K的内存便可用来不精确（大概0.81%误差）计算 2^64 个元素的基数，这个优势远胜于 Set 方法。
关于原理，可以参考博客：https://blog.csdn.net/tannuowaqin169/article/details/79732862。
2.3 HyperLogLog 算法与 Redis 去重计数的关联
- 当使用
PFADD命令添加一个计数元素后，该元素会被散列某个桶（bucket）中，就像是 HyperLogLog 中的随机数，可以通过PFCOUNT命令去获取基数； - HyperLogLog 分配12K内存方式：算法实现过程中用到了
2^14 个桶，每个桶占6 bit，因此占据字节数为2^14*6/8=2^11*6=12K； - 事实上，HyperLogLog 算法并非时刻占据12K内存，当数据量较小时，为减少内存占用采用稀疏矩阵，只有当数据量到达阈值后变成 12K。
三、测试
启动 redis-server 和 redis-client 进程之后，使用命令添加计数元素，然后查询计数情况。
- pfadd 命令： 添加计数元素；
- pfcount：获取对所有元素的基数。
127.0.0.1:6379> pfadd pf1 redis
(integer) 1
127.0.0.1:6379> pfadd pf1 mongodb
(integer) 1
127.0.0.1:6379>
127.0.0.1:6379> pfadd pf1 oracle
(integer) 1
127.0.0.1:6379> pfcount pf1
(integer) 3
127.0.0.1:6379>
笔者水平有限，如有错误，敬请指正！
网友评论