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，則會有很多散列衝突，最終導致大的估計錯誤。然而，實踐中從未出現過這個數量級的基數。