database - HyperLogLog算法说明

Question

首先让我先说我读过这个问题。

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

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

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

Answer 1

HyperLogLog 最酷的地方在于，您不必存储您看到的整个数组O(n)，甚至不必存储唯一值。你需要存储的东西O(log(log(n))要低得多。

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

这个事实也允许简单的并行性 - 您可以划分人口，并分别计算最大值，稍后通过计算单独最大值的最大值将它们组合起来。