HyperLogLog（关于基数统计）

写在前面

今天在复习Redis的一种在Redis 2.8.9 版本更新的结构的时候，知道了这个数据结构是基于一种优秀的算法HyperLogLog，基数统计算法（简单来说就是统计集合中的元素数量，但是对比set有了很大的优化），就去了解了一下这种算法的精妙之处。

HyperLogLog

这种数据结构在Redis这种NoSQL型数据库中可以非常省内存的去统计各种计数，比如注册 IP 数、每日访问 IP 数、页面实时UV、在线用户数，共同好友数等。这个是应用场景。

127.0.0.1:6379[1]> PFADD k1 a b c d 1 2 3 4 1 2 3 4 5
(integer) 1
127.0.0.1:6379[1]> PFCOUNT k1
(integer) 9
127.0.0.1:6379[1]> PFADD k2 a b c d 1 2 3 
(integer) 1
127.0.0.1:6379[1]> PFMERGE k1 k2
OK
127.0.0.1:6379[1]> PFCOUNT k1
(integer) 9
127.0.0.1:6379[1]> PFADD k2 a b c 5 6 1 2 3 4
(integer) 1
127.0.0.1:6379[1]> PFCOUNT k2
(integer) 10
127.0.0.1:6379[1]> keys *
1) "k2"
2) "k1"
127.0.0.1:6379[1]> PFCOUNT k2
(integer) 10
127.0.0.1:6379[1]> PFCOUNT k1
(integer) 9
127.0.0.1:6379[1]> PFMERGE k1 k2 
OK
127.0.0.1:6379[1]> PFCOUNT k1
(integer) 10

从上面的示例可以看出，有三个操作：PFADD、PFCOUNT、PFMERGE。

优点

1、使用少量内存就可以统计大量的数据，比如在Redis 中一个键为12K，就可以统计2^64的数据量。

2、统计存在一定的误差，误差率整体较低，标准误差为 0.81%（但是对于一些有一定容错率的业务场景，如IP统计、在线用户数等，这种误差是可以忽略不计的）；

3、误差可以被设置辅助计算因子进行降低。

原理：来自于一篇论文http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf

参考

关于基数统计 - 知乎

Redis入门 - 数据类型：3种特殊类型详解 | Java 全栈知识体系

11. 优秀的基数统计算法--HyperLogLog - 古明地盆 - 博客园