💡 什么是基数（Cardinality）？
基数（Cardinality）是指集合中不重复元素的数量，也称为集合的"势"或"大小"。
📝 简单例子：
- 集合 A = {1, 2, 3, 4, 5}，基数 = 5（有5个不同的元素）
- 集合 B = {1, 2, 2, 3, 3, 3}，基数 = 3（虽然有6个元素，但只有3个不同的元素：1, 2, 3）
- 集合 C = {"apple", "banana", "apple", "orange"}，基数 = 3（3个不同的水果）
🎯 实际应用场景：
| 场景 | 集合元素 | 基数含义 |
|---|---|---|
| 网站访问统计 | 用户ID列表 | 独立访客数（UV） |
| 数据库查询 | 订单表中的用户ID | 唯一用户数 |
| 日志分析 | IP地址列表 | 唯一IP数 |
| 社交网络 | 用户关注列表 | 粉丝数（去重后） |
⚠️ 基数 vs 总数：
- 总数（Count）：集合中所有元素的数量，包括重复的
例如：{1, 2, 2, 3} 的总数 = 4 - 基数（Cardinality）：集合中不重复元素的数量
例如：{1, 2, 2, 3} 的基数 = 3
💭 理解：如果有一个用户访问了网站10次，在统计总数时算10次，但在统计基数（独立访客数）时只算1次。
🔢 数学表示：
对于集合 S，基数表示为 |S| 或 card(S)
\[ |S| = \text{集合 S 中不同元素的数量} \]
例如：S = {a, b, a, c, b}，则 |S| = 3（因为只有 a, b, c 三个不同的元素）
🎯 为什么需要估计基数？
- 精确计算成本高：对于大数据集，精确计算基数需要存储所有元素，内存占用巨大
- 近似值足够：在很多场景下，我们只需要知道大概有多少个不同的元素，不需要精确值
- 实时性要求：在流式处理中，需要实时统计，无法等待所有数据到达
- 分布式场景：在分布式系统中，精确统计需要大量网络传输，近似估计更高效
📚 什么是 HyperLogLog？
HyperLogLog是一种用于估计集合基数（cardinality）的概率数据结构，由 Philippe Flajolet 等人在 2007 年提出。
核心特点：
- 极低内存占用：通常只需要几KB到几十KB的内存
- 高精度估计：标准误差率约为 0.81% / √m（m为寄存器数量）
- 可合并性：多个 HyperLogLog 结构可以合并，用于分布式计算
- 流式处理：支持逐个添加元素，无需预先知道集合大小
应用场景：统计网站独立访客数（UV）、数据库去重计数、大数据流处理等需要统计不重复元素数量的场景。
🧮 数学原理
1. 哈希函数：将元素映射为二进制串
\[ h(x) \rightarrow \text{二进制串} \]
2. 前导零计数：统计哈希值二进制表示中前导零的个数
\[ \rho(h(x)) = \text{前导零个数} + 1 \]
3. 寄存器更新：每个元素根据哈希值的前 b 位确定寄存器索引，更新该寄存器的最大值
\[ M[j] = \max(M[j], \rho(h(x))) \]
其中 j 是哈希值的前 b 位（寄存器索引）
4. 基数估计：
\[ E = \alpha_m \cdot m^2 \cdot \left( \sum_{j=0}^{m-1} 2^{-M[j]} \right)^{-1} \]
其中 \( \alpha_m \) 是修正因子，m 是寄存器数量
关键参数：
- m（寄存器数量）：通常为 2 的幂次，如 2^4=16, 2^8=256, 2^14=16384
- b（索引位数）：log₂(m)，用于确定寄存器索引
- 精度：标准误差 ≈ 1.04 / √m
🎛️ 交互控制面板
标准误差 ≈ 1.04 / √m
📊 精确计数（Set）
🔢 HyperLogLog 估计
寄存器状态可视化
计数对比趋势图
💡 使用场景
1. 网站独立访客统计（UV）
统计一天内访问网站的唯一用户数。使用 HyperLogLog 可以在几KB内存内统计百万级用户的UV，而精确计数需要存储所有用户ID。
优势：内存占用极小，可以实时统计，支持多天数据合并。
2. 数据库去重计数
统计数据库中某个字段的不重复值数量，如统计订单表中的唯一用户数、日志中的唯一IP数等。
优势：避免全表扫描，在分布式数据库中可以并行计算后合并。
3. 大数据流处理
在实时数据流中统计不重复元素数量，如统计实时日志中的唯一错误类型、统计API调用中的唯一用户等。
优势：支持流式处理，内存占用固定，可以处理无限大的数据流。
4. 分布式系统去重
在分布式系统中，多个节点各自维护 HyperLogLog 结构，最后合并得到全局的唯一元素数量。
优势：支持高效的合并操作，适合分布式计算场景。
5. A/B 测试中的用户统计
在A/B测试中统计不同实验组的唯一用户数，判断实验组之间的用户重叠情况。
优势：可以快速估算交集和并集的基数，支持集合运算。
⚙️ 技术细节
- 哈希函数：使用 MurmurHash3 或类似的高质量哈希函数，确保均匀分布
- 寄存器数量选择：
- m = 16：误差约 26%，内存约 16 字节
- m = 256：误差约 6.5%，内存约 256 字节
- m = 4096：误差约 1.6%，内存约 4 KB
- m = 65536：误差约 0.4%，内存约 64 KB
- 修正因子：对于小基数情况，使用线性计数法进行修正，提高精度
- 合并操作：多个 HyperLogLog 结构可以通过取每个寄存器最大值的方式合并
⚠️ 注意事项
- HyperLogLog 只能估计基数，不能获取具体的元素列表
- 对于非常小的集合（< 5 × m），误差可能较大，需要使用修正算法
- 哈希函数的质量直接影响估计精度，应使用高质量的哈希函数
- 标准误差是统计意义上的，实际误差可能因数据分布而有所不同