redis - Redis Hyperloglog 限制

Question

我正在尝试使用 Redis Hyperloglog 以一种骇人听闻的方式解决问题，但我想了解的是 Hyperloglog 对数据或分布的限制和假设。

count-min 和bloom 过滤器有自己的一组限制，但谷歌在提供有关Hyperloglog 应用程序和限制的大量信息方面没有帮助。

我正在使用 Redis Hyperloglog，正如Antirez所描述的那样there are no practical limits to the cardinality of the sets we can count.但是从理论的角度来看，Hyperloglog 是否对数据或分布做出任何假设/约束？

Answer 1

HyperLogLog 算法假设使用了一个强大的通用散列函数。Redis 使用 MurmurHash64A 从实用的角度来看应该足够好。Redis HyperLogLog 实现每个寄存器使用 6 位，这允许表示 64 位哈希值内的任何位运行长度。因此，我看到的唯一限制是 64 位哈希值本身。如果基数在 2^64 的数量级，将会有很多哈希冲突，最终会导致较大的估计误差。然而，这种数量级的基数在实践中从未发生过。