当前位置：首页 > ai >正文

【2025最新redis数据结构之Hypeloglog介绍】关于Hypeloglog

ai 2025/7/22 8:58:26

HyperLogLog (HLL) 算法深度解析

一、HLL 基本概念

HyperLogLog 是一种用于基数统计（distinct counting）的概率算法，能够在极小内存占用下（通常只需几KB）估算巨大数据集的基数（不重复元素数量），标准误差约为 0.81%。

核心特点

极低内存消耗：统计 10^9 个不重复元素仅需约 1.5KB 内存
固定大小结构：内存占用与基数大小无关
可合并性：多个 HLL 结构可以合并计算总基数

二、算法实现原理

1. 基本思想

HLL 基于以下观察：在一个随机均匀分布的比特流中，连续出现 "0" 的最大数量 k 与数据集中不重复元素的数量 N 存在关系：N ≈ 2^k

2. 核心组件

哈希函数：
- 将输入元素映射为足够长的比特串（通常 64 位）
- 要求：均匀分布、确定性
分桶（Register）：
- 使用前 m 个比特确定桶索引（m 通常取 12-16）
- 剩余比特用于计算连续前导零的数量
调和平均数：
- 用于合并各桶的估算值，减少误差

3. 算法步骤

初始化：

m = 2^b # b 通常取 4-16 registers = [0] * m

添加元素：

def add(element):hash = sha1(element).hexdigest()  # 生成哈希值index = int(hash[:b], 16) % m    # 前b位作为桶索引value = hash[b:]                 # 剩余部分计算前导零leading_zeros = count_leading_zeros(value) + 1registers[index] = max(registers[index], leading_zeros)

估算基数：

def estimate():harmonic_mean = sum(2 ** -r for r in registers) ** -1return alpha * m * m * harmonic_mean  # alpha 为修正因子

三、Redis 中的实现（为什么redis中只占用了12kb的大小）

Redis 实现的 HyperLogLog 使用 16384 (2^14) 个桶，每个桶占 6 bits，总内存占用：

12 KB = 16384 * 6 / 8 / 1024

内存布局

+---------+---------+-----+---------+
| 11000000 | 00011100 | ... | 00101100 |  # 每个桶6位
+---------+---------+-----+---------+

关键命令

PFADD key element [element ...]  # 添加元素
PFCOUNT key [key ...]           # 获取基数估算
PFMERGE destkey sourcekey [sourcekey ...] # 合并多个HLL

四、数学原理深度解析

1. 概率基础

对于均匀分布的哈希值，连续出现 k 个前导零的概率：

P = 1 / 2^(k+1)

2. 估算公式

原始 LogLog 估算：

E = α * m * 2^(1/m * Σρ)

改进的 HyperLogLog 估算：

E = α * m * m / (Σ2^(-ρ))

其中：

m = 桶数量
ρ = 各桶的最大前导零数
α = 修正因子（m=16:0.673, m=32:0.697, m=64:0.709, m≥128:0.7213/(1+1.079/m))

3. 误差修正

对小范围基数进行线性修正：

当 E < 2.5m：使用线性计数
当检测到空桶：调整估算公式

五、性能优化技术

稀疏表示：
- 对小基数使用显式存储
- 当基数较小时直接存储元素而非寄存器值
偏差校正：
- 对小范围基数使用预先计算的校正表
- 消除系统偏差
寄存器压缩：
- 使用变长编码压缩寄存器数组
- 在合并时解压缩处理

六、应用场景

网站UV统计：

# 统计日UV
PFADD daily:uv:20230501 user1 user2 user3
PFCOUNT daily:uv:20230501

跨日统计：

PFMERGE weekly:uv daily:uv:20230501 daily:uv:20230502 ... daily:uv:20230507

A/B测试：

# 统计不同方案的独立用户数
PFADD variant:A user1 user3 user5
PFADD variant:B user2 user3 user6

七、与其他基数统计方案对比

算法	内存占用	误差率	是否精确	合并能力
HashSet	O(N)	0%	是	否
Linear Counting	O(N)	可变	否	是
LogLog	O(log(logN))	1.3/√m	否	是
HyperLogLog	O(log(logN))	0.81/√m	否	是
HyperLogLog++	O(log(logN))	0.81/√m	否	是