Redis高级数据结构之HyperLogLog

淩亂°似流年 2023-10-12 10:18 20阅读 0赞

### HyperLogLog的介绍 ###

*  这并不是一种全新的数据结构、实际类型是一种字符串类型。
 *  通过一种基数（不重复的元素数量就是基数）算法，便可以使用很小的内存空间完成独立总数的统计。
 *  数据集可以是IP、Email、ID等
 *  官方给出的统计误差是0.81%，能满足市面上绝大多数的UV统计需求。

### HyperLogLog的常用操作命令 ###

> 操作命令中的pf为了纪念这个算法的提出者 **Philippe Flajolet**  
> ![在这里插入图片描述][fb2897479639401ca1bc1507b881aa95.png]

*  向HyperLogLog添加元素、添加成功返回1
 *  pfadd key element \[element …\]  
    ![在这里插入图片描述][89f55dcf2a7f40988fa4de61eb099424.png]
 *  计算一个或者多个HyperLogLog的独立总数  
    ![在这里插入图片描述][278ded5280ed4f3ebd2facb2d282c64d.png]
 *  重复向HyperLogLog中插入元素，统计值会存在误差、存在误差的概率  
    ![在这里插入图片描述][e7323e8b473a462d8c2017f3bfb88a2e.png]
 *  求多个HyperLogLog的并集
 *  pfmerge destkey sourcekey \[sourcekey … \]
 *  求出的结果放到 sourcekey  
    ![在这里插入图片描述][eef96857df814e9398fa9be6d56660f3.png]

### 原理概述 ###

> 基本原理便是HyperLogLog基于概率论中的伯努利试验并结合了极大的似然估算方法，做了分桶优化。  
> redis中的HyperLogLog在传统的分桶优化基础之上，还采用调和平均数过滤掉不健康的统计值。

### Redis中的原理分析 ###

*  通过hash函数将传入的数据转化为64位的二进制比特串，并根据比特串的位数求出转化为1的最大位置k\_max来求出存入了多少数据
 *  根据转化为的64位比特串的后14位作为分桶的依据，也就是2的14次方，一共分16384个桶。达到降低误判的作用
 *  然后比特串的前50位则依据从左往右第一个出现1的位数分别进入不同的桶中。所以每个桶中最大就存储50，总共是6位二进制比特串。110010

### 计算一个HyperLogLog的key占用的存储空间 ###

一个key占用16384个桶x6位/8=12288b/1024=12KB

[fb2897479639401ca1bc1507b881aa95.png]: https://img-blog.csdnimg.cn/fb2897479639401ca1bc1507b881aa95.png
[89f55dcf2a7f40988fa4de61eb099424.png]: https://img-blog.csdnimg.cn/89f55dcf2a7f40988fa4de61eb099424.png
[278ded5280ed4f3ebd2facb2d282c64d.png]: https://img-blog.csdnimg.cn/278ded5280ed4f3ebd2facb2d282c64d.png
[e7323e8b473a462d8c2017f3bfb88a2e.png]: https://img-blog.csdnimg.cn/e7323e8b473a462d8c2017f3bfb88a2e.png
[eef96857df814e9398fa9be6d56660f3.png]: https://img-blog.csdnimg.cn/eef96857df814e9398fa9be6d56660f3.png