无需登录 数据私有 本地保存

HyperLogLog 基数估计演示 - 去重计数概率算法

教育 算法 HyperLogLog 估计 基数 算法
27
0
0
0

HyperLogLog 基数估计演示

概率数据结构 · 去重计数 · 极低内存占用 · 约2%标准误差（m=214时）

0%
快速预设:
桶寄存器状态
64个桶
柱状图：每个桶记录的最大前导零+1值
统计对比
总处理元素数
0
实际去重计数 (Set)
0
HLL 估计值
0
估计误差
--
内存使用对比
HLL 48 B
精确Set 0 B
--
最近添加的元素将显示在这里...
常见问题与知识点
什么是HyperLogLog？
HyperLogLog（HLL）是一种概率数据结构，用于估计数据集中不同元素的数量（基数）。它由Philippe Flajolet等人于2007年提出，是LogLog算法的改进版本。HLL的核心优势在于：无论处理多少数据，它只使用固定且极小的内存（通常几KB），即可给出误差约2%的基数估计。这使得它在大数据场景（如UV统计、流数据处理）中非常实用。
HyperLogLog的典型应用场景有哪些？
典型应用包括：网站UV统计（独立访客数）、广告曝光去重、数据库查询优化（估算JOIN结果行数）、流数据处理（如Apache Flink/Spark中的基数估计）、网络流量分析（独立IP计数）、推荐系统（去重用户行为统计）。任何需要统计"有多少不同项"且无法承受全量存储的场景都适合使用HLL。
HyperLogLog的误差率是多少？如何选择精度？
HLL的标准误差约为1.04 / √m，其中m是桶的数量（m=2p）。例如：p=6（64桶）→误差约13%；p=8（256桶）→误差约6.5%；p=10（1024桶）→误差约3.25%；p=14（16384桶）→误差约0.81%。内存占用为m×6位。选择精度时需权衡：更高精度需要更多内存，但误差更小。对于大多数Web应用，p=14（约12KB内存，<1%误差）是很好的默认选择。
HyperLogLog和Bloom Filter有什么区别？
两者都是概率数据结构，但目的不同：HyperLogLog用于基数估计（"有多少不同的元素？"），它不能回答"某个元素是否出现过"；Bloom Filter用于成员查询（"这个元素可能存在吗？"），它不能告诉你总共有多少不同元素。两者可以互补使用：Bloom Filter判断元素是否见过，HLL统计总数。
HLL如何做到用这么少的内存？
HLL不存储元素本身，而是观察每个元素哈希值的位模式。它将哈希值分成两部分：前p位确定桶索引（共m=2p个桶），剩余位用于计算前导零的数量。每个桶只记录观察到的最大"前导零+1"值。由于前导零的分布与基数有数学关系（大约每2k个元素会出现一个前导零为k的哈希），通过所有桶的调和平均数可以反推基数。整个过程只需m×6位内存。
HLL可以合并吗？合并后还准确吗？
可以合并，且合并是无损的。HLL的一个重要特性是可合并性：将两个HLL结构对应桶的值取最大值，即可得到并集的基数估计。这使得HLL非常适合分布式场景——每个节点维护自己的HLL，最后汇总合并。合并后的误差与直接使用相同内存的HLL一致，不会累积额外误差。这一特性被广泛应用于分布式UV统计等场景。
🔧 相关工具