在前段时间的工作中，我这边有用到 Redis 的 HyperLogLog 来统计一些 UGC 内容的曝光 UV。
HyperLogLog 是一种用于估计大规模数据集基数（即集合中不同元素的数量）的概率性算法。使用的过程中，我发现它非常非常神奇：
内存使用量极低：使用最多 12KB 左右的数据，可以记录(估算)上亿甚至上亿亿的 UV
计算复杂度低：插入、查询的算法复杂度都是 O(1)
支持多个数据集的并集：可以将多个 Key 的 UV 进行去重合并，复杂度是 O(1)
结果是估计值，但其估计误差也非常的小基数——唯一元素的计数
网站当日访问的去重 IP 数量，或者访问某个短视频的用户总数，就是所谓的“唯一元素的计数”。有个更专业的词表示这一概念：在数学集合论中，基数（cardinality，或翻译为势），即集合中包含的唯一元素的“个数”。
通常，这种计数需要记录截至当前遇到的所有唯一元素，以便在下一个元素到来时，判断是否是已经被计数过，仅当该元素以前从未出现过时才增加计数器。但是记录完整唯一元素的方法，在元素大到一定程度之后（比如短视频 APP 有1亿活跃用户，1亿条视频播放，要实时统计每条视频的UV），无论使用 Hash 表、搜索树、位图，其内存消耗会大到不能接受。
有一类随机算法，可以使用估算集合的基数。神奇的是这类算法只使用少量&固定的内存空间，且插入和统计的算法复杂度都是 O(1)。其中，HyperLogLog 算法就非常出色，使用非常少量的内存，同时可以很好地估算基数。HyperLogLog 之所以叫 HyperLogLog，是因为它在 LogLog 算法基础上做的改进，而之前还有Linear Counting算法。
在 Redis 中实现的 HyperLogLog，每个 key 仅使用 12kB + 16B 进行计数，标准误差为 0.81%（standard error 如何定义的），并且可以计数的项目数量几乎没有限制（除非基数接近 264 -> 18亿亿）。而且 HLL 还可以 O(1) 的算法复杂度 merge 两个计数器！
总结
处理 visited 数据增长问题的方法包括：
使用更高效的数据结构：如布隆过滤器或 HyperLogLog
定期清理策略：基于时间或大小清理旧状态
外部存储解决方案：使用数据库或 Redis 存储状态
状态压缩和序列化：减少每个状态的内存占用
算法优化：使用 IDDFS 或双向搜索减少需要存储的状态数量
选择哪种方法取决于你的具体需求：
如果状态空间不是特别大，使用定期清理策略可能足够
如果状态空间非常大，考虑使用外部存储或布隆过滤器
如果算法允许，使用 IDDFS 或双向搜索可以完全避免 visited 集合增长过大的问题
在实际应用中，你可能需要组合使用多种策略来平衡内存使用和算法性能。
