HyperLogLog算法是如何工作的?
最近我在业余时间学习了不同的算法，我发现了一个非常有趣的算法，叫做HyperLogLog算法——它可以估计一个列表中有多少个唯一的项目。
这对我来说特别有趣，因为它让我回到了我使用MySQL的日子，当时我看到了“基数”值(直到最近我一直认为它是计算出来的，而不是估计出来的)。
因此，我知道如何在O(n)中编写一个算法，该算法将计算数组中有多少唯一项。我用JavaScript写的:
function countUniqueAlgo1(arr) {
var Table = {};
var numUnique = 0;
var numDataPoints = arr.length;
for (var j = 0; j < numDataPoints; j++) {
var val = arr[j];
if (Table[val] != null) {
continue;
}
Table[val] = 1;
numUnique++;
}
return numUnique;
}
但问题是我的算法，虽然O(n)，使用大量的内存(存储值在Table)。
我一直在阅读这篇论文，了解如何在O(n)时间内使用最小内存计算列表中的重复项。
它解释说，通过哈希和计数位或其他东西，人们可以在一定的概率内估计(假设列表是均匀分布的)列表中唯一项的数量。
我看了报纸，但我似乎不懂。谁能给个更外行的解释?我知道哈希是什么，但我不明白它们是如何在这个HyperLogLog算法中使用的。
