关于HyperLogLog算法的说明

Question

首先，让我先说我读过this question.

所以当我在互联网上闲逛的时候，我偶然发现了这个算法，我想知道它是如何工作的。在读到它之后，我确实理解了它是如何通过散列和使用位来计算视图的。

我还不太明白的是，如何确保避免再次计算相同的视图。我们是否存储我们遇到的每个散列值，并在递增计数之前检查它是否已经存在于我们的数组中或其他什么地方？

如果我们有1000k+项目，这不是会大大降低效率吗？

Answer 1

关于HyperLogLog最酷的一点是，您不必存储您所看到的整个数组(即O(n) )，甚至不需要存储唯一的值。你需要存储的是更低的O(log(log(n))。

基本上，如果两个对象具有相同的值，那么它们的散列将是相同的。这意味着前导比特也将是相同的。因此，拥有多个具有相同值的对象根本不会影响计算。

这一事实也允许简单的并行性-你可以划分你的群体，并单独计算最大值，稍后通过计算单独的最大值来合并它们。