Java 中的 HyperLogLog 算法指南

1. 概述

HyperLogLog (HLL) 是一种概率数据结构，用于估算数据集的基数（即不同元素的数量）。

假设我们拥有数百万用户，需要计算网页的独立访客数。最直观的实现是：将每个用户ID存入集合，集合大小即为基数。但当数据量极大时，这种做法会消耗大量内存，效率低下。

如果我们能接受误差在几个百分点内（而非精确值），HLL 就是理想选择——它专为估算百万甚至十亿级不同值的场景设计。

2. Maven 依赖

首先添加 hll 库的 Maven 依赖：

<dependency>
    <groupId>net.agkn</groupId>
    <artifactId>hll</artifactId>
    <version>1.6.0</version>
</dependency>

3. 使用 HLL 估算基数

HLL 构造函数有两个关键参数，需根据需求调整：

log2m（以2为底的对数）：HLL 内部使用的寄存器数量（注意：这里指定的是 m）
regwidth：每个寄存器占用的位数

✅ 精度与内存的权衡：

更高精度 → 更大参数值 → 更多内存占用
更低精度 → 更小参数值 → 更少内存占用

以估算 1 亿条数据集的基数为例，我们设置 log2m=14、regwidth=5（此规模下的合理配置）：

HashFunction hashFunction = Hashing.murmur3_128();
long numberOfElements = 100_000_000;
long toleratedDifference = 1_000_000; // 允许误差
HLL hll = new HLL(14, 5);

此配置能将误差率控制在 1% 以内（100万元素）。接下来插入 1 亿条数据：

LongStream.range(0, numberOfElements).forEach(element -> {
    long hashedValue = hashFunction.newHasher()
        .putLong(element)
        .hash()
        .asLong();
    hll.addRaw(hashedValue);
});

最后验证 HLL 返回的基数是否在误差范围内：

long cardinality = hll.cardinality();
assertThat(cardinality)
  .isCloseTo(numberOfElements, Offset.offset(toleratedDifference));

4. HLL 的内存占用

HLL 内存占用公式：numberOfBits = 2^log2m * regwidth。

以我们的配置为例：2^14 * 5 ≈ 81000 位（约 8100 字节）。也就是说，估算 1 亿条数据的基数仅需 8100 字节内存。

对比传统实现：

使用 Set<Long> 存储 1 亿个 Long 值：100,000,000 * 8 = 800,000,000 字节（约 800 MB）
HLL 仅需 8100 字节，内存占用仅为传统方案的 0.001%

⚠️ 数据规模越大，HLL 的内存优势越显著。

5. 两个 HLL 的合并操作

HLL 的合并（Union）操作有重要特性：合并两个独立数据集的 HLL 后，其基数估算误差与直接合并所有元素的单个 HLL 相同。

❗ 注意：合并的两个 HLL 必须具有相同的 log2m 和 regwidth 参数。

以下示例验证该特性：

创建两个 HLL：
- firstHll：存储 0 到 1 亿的值
- secondHLL：存储 1 亿到 2 亿的值

HashFunction hashFunction = Hashing.murmur3_128();
long numberOfElements = 100_000_000;
long toleratedDifference = 1_000_000;
HLL firstHll = new HLL(15, 5); // log2m 从 14 增至 15（因合并后数据量翻倍）
HLL secondHLL = new HLL(15, 5);

// 填充第一个 HLL
LongStream.range(0, numberOfElements).forEach(element -> {
    long hashedValue = hashFunction.newHasher()
        .putLong(element)
        .hash()
        .asLong();
    firstHll.addRaw(hashedValue);
});

// 填充第二个 HLL
LongStream.range(numberOfElements, numberOfElements * 2).forEach(element -> {
    long hashedValue = hashFunction.newHasher()
        .putLong(element)
        .hash()
        .asLong();
    secondHLL.addRaw(hashedValue);
});

合并两个 HLL 并验证基数：

firstHll.union(secondHLL); // 合并操作
long cardinality = firstHll.cardinality();
assertThat(cardinality)
  .isCloseTo(numberOfElements * 2, Offset.offset(toleratedDifference * 2));

6. 总结

本文介绍了 HyperLogLog 算法的核心应用：

✅ 使用 HLL 估算数据集基数
✅ 对比传统方案，HLL 内存效率极高（百万级数据仅需 KB 级内存）
✅ HLL 的合并操作保持误差一致性

所有示例代码可在 GitHub 项目中获取（Maven 项目，可直接导入运行）。

Persistence

REST