Redis Hyperloglog限制

Question

我试图用Redis Hyperloglog以一种老生常谈的方式解决一个问题，但我试图理解的是Hyperloglog对数据或分布的限制和假设。

count-min和bloom filter有自己的一组限制，但google在提供有关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的量级，将会有许多哈希冲突，最终会导致很大的估计误差。然而，这种数量级的基数在实践中从未发生过。