基数统计-原理和应用场景
基数统计-原理和应用场景
基数统计概述
基数（Cardinality）是指一个集合中不同元素的数量，或者说统计一个集合中不重复元素的个数。
简单来说：基数（Cardinality）就是去除重复后的数的个数
例如，对于一个包含重复元素的集合{1, 2, 2, 3, 4, 4, 4}，其基数为4，即不同元素的个数。
在Redis中，HashSet / HyperLogLog数据结构都能提供高效的基数统计，而HyperLogLog算法可以在不保存原始数据的情况下快速计算出一个集合的基数。
基数统计的2大类型
类型 1：精确计算
对于较小规模的数据集，可使用数据结构如哈希集合（HashSet）来实现基数统计。
哈希集合的工作原理：
哈希集合利用哈希函数将元素映射到存储位置，其内部会自动处理元素的插入和冲突问题。
当插入一个元素时，哈希集合会根据元素的哈希值确定存储位置，若该位置没有元素，则直接插入；若已存在元素（哈希冲突），则通过一定的冲突解决策略（如链表法或开放寻址法）来处理。
通过计算哈希集合中的元素数量，即可得到集合的基数。
类型 2：近似计算原理（以 HyperLogLog 为例）
HyperLogLog 是一种基于概率的数据结构，用于估算大数据集的基数。
基本原理：
- 将元素哈希为二进制串
- 通过统计哈希值的前导零的最大长度来估算基数
- 每个不同的元素经过哈希后，其哈希值的前导零长度呈现一定的概率分布
- HyperLogLog 通过维护多个寄存器来记录这些最大长度，然后根据这些寄存器的值和一定的数学公式来估算集合中的不同元素数量
特点：
- 以牺牲一定的准确性为代价，换取了对内存的高效利用
- 能够在有限的内存空间内处理大规模数据集
- HyperLogLog不存储数据，只记录不重复数的个数
- HyperLogLog有误差，在0.8125%
基数统计的应用场景和案例
基数统计场景1：网站流量分析
互联网公司中，用于统计网站的独立访客数量，为市场部门评估网站的用户覆盖范围和广告效果提供重要数据。
例如，像百度这样的大型搜索引擎网站，每天有海量的访问请求。通过基数统计，可以了解有多少不同的用户访问了网站，而不需要记录每个用户的详细访问信息。
使用 HyperLogLog 算法，在内存占用较小的情况下，就能快速估算出 UV/PV/ 注册IP数/ 每日访问IP数/统计在线人数：
统计网站注册IP数：使用HyperLogLog可以高效地统计网站注册用户的独立IP数量，为网站运营者提供有价值的数据支持。
统计每日访问IP数：通过对用户访问日志进行处理，使用HyperLogLog可以快速统计出每日的独立访问IP数，有助于分析网站流量和用户行为。
统计页面实时UV PV数：在实时监控系统中，使用HyperLogLog可以估算出页面的实时访问用户数（UV）和页面访问量（PV），为网站运营者提供实时反馈。
统计在线人数：在实时在线人数统计系统中，HyperLogLog可以用于估算当前在线用户的数量，为系统性能优化和用户体验改进提供数据支持。
APP活跃用户数：统计一个APP的日活(日活跃用户数量)、月活数(月活跃用户数量)，即每天或每月有多少不同的用户活跃
常见名词解释：
- UV(Unique Visitor)：独立访客，一般为客户端IP，要去重
- PV(Page View)：页面浏览量，不用去重
- DAU(Daily Active User)：日活跃用户量，当天登录或者使用某个产品的用户数，要去掉重复登录的用户，多次登录只记录一次
- MAU(Monthly Active User)：月活跃用户
基数统计场景2：数据库去重
在数据库管理中，用于统计一个表中某列的不同值的数量。
例如，在电商数据库中，统计产品表中不同品牌的数量，有助于了解产品的品牌多样性和市场分布。
- 若数据量小，通过使用哈希集合可以精确计算基数
- 若数据量庞大，HyperLogLog 则是一种更合适的近似计算方法
技术实现要点
精确计算的实现方法
哈希集合实现：
- 使用哈希函数映射元素到存储位置
- 处理哈希冲突（链表法或开放寻址法）
- 维护元素数量计数器
适用场景：
- 数据量较小（百万级以下）
- 需要精确结果
- 内存充足
近似计算的实现方法
HyperLogLog算法：
- 使用多个寄存器记录哈希值前导零的最大长度
- 通过数学公式估算基数
- 误差率约为0.8125%
适用场景：
- 数据量巨大（亿级以上）
- 可以接受一定误差
- 内存受限环境
性能对比
| 特性 | 精确计算（HashSet） | 近似计算（HyperLogLog） |
|---|---|---|
| 内存占用 | O(n) | O(log log n) |
| 计算精度 | 100%准确 | 约99.2%准确 |
| 误差率 | 0% | 约0.8125% |
| 适用数据量 | 小到中等 | 大到极大 |
| 查询速度 | O(1) | O(1) |
总结
基数统计是处理去重问题的核心统计方法，根据数据规模和精度要求选择合适的实现方式：
- 小规模数据：使用精确计算，保证结果准确性
- 大规模数据：使用近似计算，在有限内存下获得可接受的精度
- 实时统计：HyperLogLog提供了高效的实时基数统计能力
- 业务指标：UV、DAU、MAU等关键业务指标都依赖于基数统计技术