Redis超级日志限制

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，则会有很多散列冲突，最终导致大的估计错误。然而，实践中从未出现过这个数量级的基数。