一、解决的问题
统计海量数据的基数，例如 UV（独立访客数）。
- 传统做法：
HashSet存所有 ID。 - 痛点：数据量大时内存爆炸（亿级用户需数百 MB）。
- HLL 方案：极低内存（约 12KB）估算基数，误差约 1%。
二、核心思想
不存数据本身，只记录“随机性特征”反推数量。
三、算法步骤
1. 哈希映射
将数据（如 user_id）映射为固定长度的二进制串。
user_id -> hash -> 001010101...2. 寻找特征（前导零）
统计二进制串开头连续 0 的个数。
1xxxx→ 0 个 001xxx→ 1 个 0001xx→ 2 个 0
3. 极值估算
只记录观察到的最大前导零个数。
- 原理：出现
k个前导零的概率为 。 - 结论：最大前导零越多，说明尝试次数（数据量）越多。
四、抛硬币类比
- 连续抛 10 次正面（对应 10 个前导零）极罕见。
- 若观察到此现象，推测肯定抛了无数次硬币（数据量大）。
五、精度优化：分桶
单次观测误差大，采用“分桶平均”法。
- 将数据分到 个桶（如 1024 个）。
- 每个桶独立记录最大前导零数。
- 最终通过调和平均数计算整体估算值。
六、内存优势
- 存储内容：仅需存储每个桶的“最大前导零计数值”。
- 空间占用：每个桶仅需几 bit，总共仅需 KB 级内存。
七、一句话总结
利用哈希值的“前导零”概率分布，以 KB 级内存估算亿级基数。 用前导0，是因为它： 1️⃣ 概率简单（1 / 2^n） 2️⃣ 容易计算（从左往右数） 3️⃣ 可逐步提高难度（n 越大越难） 4️⃣ 易验证（别人一眼就能检查）
哈希二进制 前面开头是一个0 1/2 两个0 1/4 … 这是一个指数分布
