算法简介
HyperLogLog是一种概率性数据结构，用于在极小内存空间内估计大规模数据集中不同元素的数量（即基数，Cardinality）。仅需几KB内存即可精确估计数十亿级别数据的去重计数，误差率可控制在2%以内。该算法被广泛应用于大数据实时统计、网络流量分析、数据库去重计数等场景。
核心思想
HyperLogLog的核心思想基于概率统计：
- 哈希映射：将所有元素通过哈希函数映射为均匀分布的比特串
- 前导零统计：观察哈希值中从最高位开始的连续0的个数。直观上，看到更多前导零的概率随元素数量增加而增大
- 分桶平均：使用多个寄存器（桶）分别统计，通过调和均值消除极端值影响，提高估计精度
- 偏差修正：对小基数和大基数场景分别进行修正，确保全范围精度
算法的关键洞察：如果看到最长前导零长度为 $k$，则估计基数约为 $2^k$。多个桶的统计结果通过调和均值合并，得到更稳定的估计。
Java实现
import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.BitSet;
/**
* HyperLogLog基数估计算法实现
*
* @author AlgorithmDaily
*/
public class HyperLogLog {
// 寄存器数量参数 p，总寄存器数 m = 2^p
private final int p;
private final int m;
// 寄存器数组，每个元素存储该桶观察到的最大前导零长度
private final byte[] registers;
// 哈希函数
private final HashFunction hashFunction;
// 偏差修正常数 alpha_m
private final double alphaMM;
/**
* 哈希函数接口
*/
interface HashFunction {
long hash(String input);
}
/**
* 构造HyperLogLog计数器
* @param p 精度参数，寄存器数量为 2^p，通常取4-16
*/
public HyperLogLog(int p) {
if (p < 4 || p > 16) {
throw new IllegalArgumentException("p must be between 4 and 16");
}
this.p = p;
this.m = 1 << p; // 2^p
this.registers = new byte[m];
this.hashFunction = new MurmurHash3();
this.alphaMM = computeAlphaMM(m);
}
/**
* 计算偏差修正常数
*/
private double computeAlphaMM(int m) {
switch (m) {
case 16: return 0.673;
case 32: return 0.697;
case 64: return 0.709;
default: return 0.7213 / (1 + 1.079 / m);
}
}
/**
* 添加一个元素到HyperLogLog
* @param element 待统计的元素
*/
public void add(String element) {
long hash = hashFunction.hash(element);
// 取前p位作为桶索引
int bucketIndex = (int) (hash >>> (64 - p));
// 剩余位用于计算前导零数量
long remainingBits = hash & ((1L << (64 - p)) - 1);
// 计算前导零数量（从最高位开始连续0的个数）
int leadingZeros = countLeadingZeros(remainingBits, 64 - p);
// 更新寄存器：保留最大值
if (leadingZeros > registers[bucketIndex]) {
registers[bucketIndex] = (byte) leadingZeros;
}
}
/**
* 计算long值的前导零数量
* @param value 待计算的数值
* @param bits 有效位数
* @return 前导零数量（从最高位开始连续0的个数，至少为1）
*/
private int countLeadingZeros(long value, int bits) {
if (value == 0) return bits + 1; // 全为0的特殊处理
int zeros = 1;
long mask = 1L << (bits - 1);
while ((value & mask) == 0 && zeros <= bits) {
zeros++;
mask >>>= 1;
}
return zeros;
}
/**
* 估计当前集合的基数（去重后的元素数量）
* @return 基数估计值
*/
public long count() {
// 计算调和均值
double sumInverse = 0.0;
int zeroRegisters = 0;
for (byte reg : registers) {
sumInverse += 1.0 / (1L << reg); // 2^(-register)
if (reg == 0) zeroRegisters++;
}
double harmonicMean = m / sumInverse;
double estimate = alphaMM * m * harmonicMean;
// 小范围修正：当估计值小于 2.5*m 且存在空寄存器时
if (estimate <= 2.5 * m && zeroRegisters > 0) {
estimate = m * Math.log((double) m / zeroRegisters);
}
// 大范围修正：当估计值超过 2^32/30 时（64位哈希）
else if (estimate > (1L << 32) / 30.0) {
double correction = -Math.pow(2, 32) * Math.log(1 - estimate / Math.pow(2, 32));
if (!Double.isNaN(correction)) {
estimate = correction;
}
}
return (long) estimate;
}
/**
* 合并另一个HyperLogLog（必须具有相同的p参数）
*/
public void merge(HyperLogLog other) {
if (this.p != other.p) {
throw new IllegalArgumentException("Cannot merge HLLs with different precision");
}
for (int i = 0; i < m; i++) {
if (other.registers[i] > this.registers[i]) {
this.registers[i] = other.registers[i];
}
}
}
/**
* 获取当前内存使用量（字节）
*/
public int getMemoryUsage() {
return registers.length;
}
/**
* MurmurHash3 64位哈希函数实现
*/
static class MurmurHash3 implements HashFunction {
private static final long C1 = 0x87c37b91114253d5L;
private static final long C2 = 0x4cf5ad432745937fL;
@Override
public long hash(String input) {
byte[] data = input.getBytes(StandardCharsets.UTF_8);
int length = data.length;
long h1 = 0;
long seed = 0x9747b28c;
int roundedEnd = (length & ~0x7);
for (int i = 0; i < roundedEnd; i += 8) {
long k1 = ((long) data[i] & 0xff)
| (((long) data[i + 1] & 0xff) << 8)
| (((long) data[i + 2] & 0xff) << 16)
| (((long) data[i + 3] & 0xff) << 24)
| (((long) data[i + 4] & 0xff) << 32)
| (((long) data[i + 5] & 0xff) << 40)
| (((long) data[i + 6] & 0xff) << 48)
| (((long) data[i + 7] & 0xff) << 56);
k1 *= C1;
k1 = Long.rotateLeft(k1, 31);
k1 *= C2;
h1 ^= k1;
h1 = Long.rotateLeft(h1, 27);
h1 = h1 * 5 + 0x52dce729;
}
long k1 = 0;
switch (length & 0x7) {
case 7: k1 ^= ((long) data[roundedEnd + 6] & 0xff) << 48;
case 6: k1 ^= ((long) data[roundedEnd + 5] & 0xff) << 40;
case 5: k1 ^= ((long) data[roundedEnd + 4] & 0xff) << 32;
case 4: k1 ^= ((long) data[roundedEnd + 3] & 0xff) << 24;
case 3: k1 ^= ((long) data[roundedEnd + 2] & 0xff) << 16;
case 2: k1 ^= ((long) data[roundedEnd + 1] & 0xff) << 8;
case 1: k1 ^= ((long) data[roundedEnd] & 0xff);
k1 *= C1;
k1 = Long.rotateLeft(k1, 31);
k1 *= C2;
h1 ^= k1;
}
h1 ^= length;
h1 ^= h1 >>> 33;
h1 *= 0xff51afd7ed558ccdL;
h1 ^= h1 >>> 33;
h1 *= 0xc4ceb9fe1a85ec53L;
h1 ^= h1 >>> 33;
return h1;
}
}
/**
* 主程序：演示HyperLogLog基数估计
*/
public static void main(String[] args) {
// 创建精度为14的HyperLogLog（16384个寄存器，约16KB内存）
HyperLogLog hll = new HyperLogLog(14);
// 测试场景1：精确已知基数
int actualCardinality = 1_000_000;
System.out.println("=== HyperLogLog基数估计测试 ===");
System.out.println("实际去重基数: " + actualCardinality);
// 添加100万个不同的元素
for (int i = 0; i < actualCardinality; i++) {
hll.add("user_" + i);
}
// 添加一些重复元素（不应影响计数）
for (int i = 0; i < 500_000; i++) {
hll.add("user_" + (i % actualCardinality));
}
long estimate = hll.count();
double errorRate = Math.abs(estimate - actualCardinality) * 100.0 / actualCardinality;
System.out.println("估计基数: " + estimate);
System.out.printf("误差率: %.4f%%%n", errorRate);
System.out.println("内存使用: " + hll.getMemoryUsage() + " 字节");
// 测试场景2：合并两个HyperLogLog
HyperLogLog hll1 = new HyperLogLog(14);
HyperLogLog hll2 = new HyperLogLog(14);
for (int i = 0; i < 500_000; i++) hll1.add("item_" + i);
for (int i = 250_000; i < 750_000; i++) hll2.add("item_" + i);
hll1.merge(hll2);
System.out.println("\n合并后估计基数: " + hll1.count() + " (期望约500000)");
}
}
复杂度分析
- 时间复杂度：$O(1)$，每次添加元素只需一次哈希计算和常数时间的寄存器更新
- 空间复杂度：$O(2^p)$，使用 $2^p$ 个字节的寄存器数组。例如 $p=14$ 时仅需16KB内存即可估计数十亿级基数
- 查询复杂度：$O(2^p)$，需要遍历所有寄存器计算调和均值
算法特点与适用场景
优点：
– 极低的内存占用，几KB即可处理海量数据
– 支持合并操作，天然适合分布式场景
– 添加和查询均为常数时间复杂度
缺点：
– 概率性算法，存在一定估计误差（标准误差约1.04/√m）
– 无法获取具体的去重元素列表
– 对小基数的估计需要额外修正
适用场景：网站UV统计、数据库去重计数、网络流量分析、日志分析中的唯一IP统计、大规模数据集基数估计等。
