算法面试题：概率数据结构

1. 什么是概率数据结构？

• 允许用较少空间完成近似计算。
• 结果可能存在一定概率误差。
• 常用于大数据与流式计算。

2. 常见概率数据结构有哪些？

• 布隆过滤器（Bloom Filter）。
• 计数最小值 Sketch（Count-Min Sketch）。
• HyperLogLog。

3. 布隆过滤器的基本原理是什么？

• 使用多个哈希函数。
• 维护位数组。
• 支持快速判断“可能存在”或“肯定不存在”。

4. 计数最小值 Sketch 适合解决哪些问题？

• 频率估计。
• 数据流热点统计。
• 近似计数。

5. HyperLogLog 的主要用途是什么？

• 估算不同元素的基数。
• 在大规模数据中节省空间。

6. 面试常问的概率数据结构限制有哪些？

• 可能出现假阳性。
• 不能删除元素（部分实现例外）。
• 精度与空间消耗需要权衡。