单哈希函数LogLog算法的工作原理
对于LogLog算法的基本思想，我已经找到了几十种解释，但是它们都缺乏关于散列函数如何分割的细节，的意思是使用单个哈希函数是不精确的，而使用多个函数的代价太高。他们如何克服单哈希函数的问题？
这个答案是我找到的最好的解释，但对我来说还是没有意义：
他们用了一个散列，但把它分成两部分。一个称为桶(桶的总数为2^x)，另一个与我们的散列基本相同。我很难理解发生了什么事，所以我举一个例子。假设您有两个元素，您的散列函数给出了从0到2^10的值，产生了2个值: 344和387。你决定要16个桶。所以你有： 0101 011000桶5将储存1 0110 000011桶6将储存4
请你解释一下上面的例子好吗？你应该有16个桶，因为你有长度为4的头，对吗？那么你怎么能用两个哈希就有16个桶呢？我们只估计水桶，对吧？第一桶是1码，第二桶是4码，对吗？如何合并结果？
回答 2
Stack Overflow用户
发布于 2016-10-24 03:39:06
散列函数分裂:我们的目标是使用许多超逻辑日志结构(例如，假设16个超逻辑日志结构，每个结构使用64位哈希函数)，以减少估计误差。一种直观的方法可能是处理每个超逻辑日志结构中的每个输入。但是，在这种情况下，我们需要确保超日志是相互独立的，这意味着我们需要一组相互独立的16个散列函数--这是很难找到的！
所以我们采用了另一种方法。我们不使用64位哈希函数家族，而是使用16种不同的超级日志结构，每个结构只使用一个60位哈希函数。我们该怎么做？简单来说，我们采用64位哈希函数，忽略前4位，生成60位哈希函数。我们该怎么处理前4位？我们使用它们来选择16个“桶”中的一个(每个“桶”只是一个超逻辑日志结构。注意，2^4 bits=16桶)。现在，每个输入都分配给16个桶中的一个，其中一个60位的哈希函数用于计算超级日志值。因此，我们有16个超级日志结构，每个结构使用一个60位的哈希函数。假设我们选择了一个不错的散列函数(这意味着前4位是均匀分布的，并且它们与其余的60位没有关联)，那么现在我们有了16种独立的超级日志结构。我们取他们16个估计的调和平均值，得到一个更容易出错的基数估计。
希望这能把它弄清楚！
Stack Overflow用户
发布于 2016-11-01 10:45:54
由原始HyperLogLog纸提出的OronNavon是相当理论性的。如果您在不需要复杂分析的情况下寻找基数估计量的解释，您可以查看我目前正在研究的论文：http://oertl.github.io/hyperloglog-sketch-estimation-paper。它还介绍了对小基数或大基数不需要任何特殊处理的原始估计量的推广。
https://stackoverflow.com/questions/40202559
复制相似问题
腾讯云开发者
