hyperloglog java_yolo算法原理详解[通俗易懂]

本文已收录于专栏

❤️《Redis之大厂必备技能包》❤️

欢迎各位关注、三连博主的文章及专栏，全套Redis学习资料，大厂必备技能！

目录

一、简介

二、命令

2.1 PFADD key element [element …]

2.2 PFCOUNT key [key …]

2.3 PFMERGE destkey sourcekey [sourcekey …]

三、原理

3.1 伯努利试验

3.2 估值优化

3.3 HyperLogLog的实现

3.4 代码实现-BernoulliExperiment（伯努利试验）

3.5 代码实现-HyperLogLog

一、简介

首先抛出一个业务问题：
假设产品经理让你设计一个模块，来统计PV（Page View页面的访问量），那么你会怎么做？
我想很多人对于PV（Page View页面的访问量）的统计会很快的想到使用Redis的incr、incrby指令，给每个网页配置一个独立Redis计数器就可以了，把这个技术区的key后缀加上当它的日期，这样一个请求过来，就可以通过执行incr、incrby指令统计所有PV。
​

此时当你完成这个需求后，产品经理又让你设计一个模块，统计UV（Unique Visitor，独立访客），那么你又会怎么做呢？
UV与PV不一样，UV需要根据用户ID去重，如果用户没有ID我们可能需要考虑使用用户访问的IP或者其他前端穿过了的唯一标志来区分，此时你可能会想到使用如下的方案来统计UV。

1. 存储在MySQL数据库表中，使用distinct count计算不重复的个数
2. 使用Redis的set、hash、bitmaps等数据结构来存储，比如使用set，我们可以使用用户ID，通过sadd加入set集合即可

但是上面的两张方案都存在两个比较大的问题：

1. 随着数据量的增加，存储数据的空间占用越来越大，对于非常大的页面的UV统计，基本不合实际
2. 统计的性能比较慢，虽然可以通过异步方式统计，但是性能并不理想

因此针对UV的统计，我们将会考虑使用Redis的新数据类型HyperLogLog.
HyperLogLog是用来做基数统计的算法，它提供不精确的去重计数方案（这个不精确并不是非常不精确），标准误差是0.81%，对于UV这种统计来说这样的误差范围是被允许的。HyperLogLog的优点在于，输入元素的数量或者体积非常大时，基数计算的存储空间是固定的。在Redis中，每个HyperLogLog键只需要花费12KB内存，就可以计算接近2^64个不同的基数。
但是：HyperLogLog只能统计基数的大小（也就是数据集的大小，集合的个数），他不能存储元素的本身，不能向set集合那样存储元素本身，也就是说无法返回元素。

HyperLogLog指令都是pf(PF)开头，这是因为HyperLogLog的发明人是Philippe Flajolet，pf是他的名字的首字母缩写。
​

二、命令

2.1 PFADD key element [element …]

将任意数量的元素添加到指定的 HyperLogLog 里面，当PFADD key element [element …]指令执行时，如果HyperLogLog的估计近似基数在命令执行之后出现了变化，那么命令返

今天的文章hyperloglog java_yolo算法原理详解[通俗易懂]分享到此就结束了，感谢您的阅读。