database - 具有单一哈希函数的 LogLog 算法如何工作

Question

我找到了数十种关于 LogLog 算法基本思想的解释，但它们都缺乏关于散列函数结果拆分如何工作的细节？我的意思是使用单个散列功能不精确，而使用许多功能太昂贵。 他们如何克服单一哈希函数的问题？

This answer是我找到的最好的解释，但对我来说仍然没有意义:

They used one hash but divided it into two parts. One is called a bucket (total number of buckets is 2^x) and another - is basically the same as our hash. It was hard for me to get what was going on, so I will give an example. Assume you have two elements and your hash function which gives values form 0 to 2^10 produced 2 values: 344 and 387. You decided to have 16 buckets. So you have:

0101 011000  bucket 5 will store 1
0110 000011  bucket 6 will store 4

你能解释一下上面的例子吗？你应该有 16 个桶，因为你有长度为 4 的标题，对吗？那么你怎么能有 16 个桶只有两个哈希值呢？我们只估计水桶，对吗？所以第一个桶的大小为 1，第二个桶的大小为 4，对吗？如何合并结果？

Answer 1

散列函数拆分:我们的目标是使用多个 hyperloglog 结构(例如，假设 16 个 hyperloglog 结构，每个结构使用 64 位散列函数)而不是一个，以减少估计误差。一种直观的方法可能是处理每个 hyperloglog 结构中的每个输入。然而，在那种情况下，我们需要确保 hyperloglogs 彼此独立，这意味着我们需要一组 16 个彼此独立的哈希函数 - 这很难找到!

所以我们使用另一种方法。我们将使用 16 个独立的 hyperloglog 结构，而不是使用一系列 64 位哈希函数，每个结构仅使用一个 60 位哈希函数。我们该怎么做？很简单，我们采用 64 位哈希函数并忽略前 4 位，生成一个 60 位哈希函数。我们如何处理前 4 位？我们使用它们来选择 16 个“桶”中的一个(每个“桶”只是一个 hyperloglog 结构。注意 2^4 位 = 16 个桶)。现在每个输入都被分配到 16 个桶中的一个，其中使用 60 位哈希函数计算 hyperloglog 值。所以我们有 16 个 hyperloglog 结构，每个结构使用一个 60 位哈希函数。假设我们选择了一个合适的散列函数(意味着前 4 位均匀分布，并且它们与其余 60 位不相关)，我们现在有 16 个独立的 hyperloglog 结构。我们对他们的 16 个估计值取一个调和平均值，以获得更不容易出错的基数估计值。

希望一切顺利!