前面几篇文章，我们分别讲解了：
本章将继续分析和比较他们之间的区别，以及分别在什么场景下选择什么算法。
1. Set（集合）
Set是常见数据结构，代表确定且无重复元素的集合。
- 核心原理：直接存储元素本身或完整哈希值，常见实现有哈希集合（HashSet）和树集合（TreeSet）。
- 精确性：100%精确，能准确判断元素是否在集合中。
- 空间效率：低，空间复杂度O(n)，元素大时内存消耗可观。
- 时间效率：哈希集合插入/查询平均O(1)，合并/求交集需遍历。
- 典型应用场景：数据库、缓存的成员关系判断；不大的黑名单/白名单列表；编程语言日常去重。
- 优点：精确无误，功能全面可取出所有元素。
- 缺点：内存消耗大，无法处理海量数据。
2. Bitmap（位图）
Bitmap通过bit数组表征集合，数组位对应特定元素。
- 核心原理：全集U中元素有唯一整数索引，若元素存在，对应下标bit设为1，否则为0。
- 精确性：100%精确。
- 空间效率：高，但取决于全集大小，若全集[0, n)，只需n / 8字节。
- 时间效率：插入/查询O(1)，合并/求交集可通过位运算高效操作。
- 典型应用场景：用户签到、在线状态统计；标签系统人群筛选；数据库快速查询索引。
- 优点：全集已知且不大时，时空效率极高，精确且支持快速集合运算。
- 缺点：依赖元素密集整数映射，元素ID稀疏会浪费空间；无法处理非数值型数据，需先哈希映射。
3. 布隆过滤器
布隆过滤器是概率型数据结构，判断元素是否一定不存在或可能存在。
- 核心原理：长度为m的bit数组，k个哈希函数。添加元素时，经k个哈希函数映射位置并置1；查询时，k个位置都为1则可能存在，有一个为0则一定不存在。
- 精确性：概率性，有误判率但不会漏判，可调整m和k控制误判率。
- 空间效率：极高，只需固定大小bit数组，空间复杂度O(m)。
- 时间效率：插入/查询O(k)，通常为O(1)。
- 典型应用场景：缓存穿透解决；爬虫URL去重；垃圾邮件过滤。
- 优点：空间和查询效率远超一般算法，安全不漏报。
- 缺点：有误判率，无法删除元素（计数布隆过滤器可删但需更多空间）。
4. HyperLogLog
HyperLogLog是估算大数据集基数的概率算法，回答集合大概有多少不重复元素。
- 核心原理：基于统计比特串前缀连续0的最大数目估算基数，元素经哈希函数转化为比特串，观察连续0个数，用分桶平滑极端值。
- 精确性：估算，有标准误差，约0.81%。
- 空间效率：极致，通常只需12KB或更少内存。
- 时间效率：添加元素O(1)，合并效率高。
- 典型应用场景：网站独立访客（UV）统计；数据库COUNT(DISTINCT …)近似计算；大规模日志分析统计独立事件数。
- 优点：计算巨大数据集基数时，空间复杂度优势大，合并操作方便。
- 缺点：结果为近似值，只能用于基数估算，无法判断单个元素是否存在。
5. 总结对比表格
| 特性 | Set | Bitmap | 布隆过滤器 | HyperLogLog |
|---|---|---|---|---|
| 核心问题 | 精确成员查询 | 精确成员查询 | 可能存在 / 一定不存在 | 大概有多少不重复元素 |
| 精确性 | 100%精确 | 100%精确 | 概率性（有误判） | 近似（有误差） |
| 空间效率 | 低 O(n) | 高（依赖全集密度） | 极高 O(m) | 极致 O(log log n) |
| 关键优势 | 精确，功能全 | 精确，集合运算快 | 空间效率极高，安全（不漏报） | 海量数据基数估算 |
| 致命弱点 | 内存消耗大 | 1. 一般只支持整数类型； 2. 稀疏数据下空间浪费 |
有误判率，无法删除 | 只能计数，不能查询成员 |
| 典型应用 | 通用去重，小规模数据 | 标签系统，状态统计 | 缓存穿透，爬虫去重 | 网站UV统计 |
6. 如何选择？
选择取决于业务需求：
- 需100%精确判断元素是否存在：
- 数据量不大用Set。
- 元素是密集整数用Bitmap。
- 数据量巨大且可接受小概率误判：判断存在性用布隆过滤器。
- 只需知道大概不重复元素数量：统计基数用HyperLogLog。
- 组合使用案例：大型网站统计系统，布隆过滤器防缓存穿透，HyperLogLog统计日活，Bitmap用于用户画像圈选，Set存储后台管理员列表。
