phi*_*urn 5 testing hash hashtable
我已经阅读了关于'Balls and Bins'问题的各种论文,似乎如果一个哈希函数正常工作(即它实际上是一个随机分布),那么如果我将n值哈希到一个哈希值,那么下面应该/必须为真带n槽(或箱)的桌子:
n的1/e.n/e.k球的概率是<= 1/ek!(校正的).<= ((e/k)**k)/e(校正的).这些看起来很容易检查.但是max-load通常会模糊地说明测试(具有高概率的最大碰撞次数).
大多数文本都声明任何bin中的最大碰撞数量O( ln(n) / ln(ln(n)) ).有人说是的3*ln(n) / ln(ln(n)).其他文件混合ln和log-通常没有定义它们,或者说国家log是数e为底,然后用ln在其他地方.
是ln立足日志e或者2是这个max-load公式的权利和应为多大n是运行试验？
这个讲座似乎是最好的,但我不是数学家.
http://pages.cs.wisc.edu/~shuchi/courses/787-F07/scribe-notes/lecture07.pdf
BTW,with high probability似乎意味着1 - 1/n.
这是一篇引人入胜的论文/讲座——让我希望我参加过一些正式的算法课程。
我将根据我刚刚读到的内容在这里尝试一些答案，并随意投票否决我。不过，我希望得到更正，而不仅仅是投反对票:)我也将在这里互换使用 n 和 N，这在某些圈子里是一个很大的禁忌，但因为我只是复制粘贴你的公式，希望你能原谅我。
首先，原木的基础。这些数字以大 O 表示法给出，而不是绝对公式。这意味着您正在寻找“按 ln(n) / ln(ln(n)) 的顺序”的东西，而不是期望绝对答案，而是随着 n 变大，n 与最大碰撞次数应遵循该公式。您可以绘制的实际曲线的细节会因实现而异（我对实际实现了解不够，无法告诉您什么是“好”曲线，除了它应该遵循大 O 关系）。您发布的这两个公式实际上在大 O 表示法中是等效的。第二个公式中的3只是一个常数，与具体的实现相关。效率较低的实施将具有较大的常数。
考虑到这一点，我会进行实证测试，因为我本质上是一名生物学家，并且我接受的训练是避免用硬性证据来表明世界实际上是如何运作的。从 N 作为某个数字（例如 100）开始，找到其中碰撞次数最多的 bin。这是您这次跑步的最大负荷。现在，您的示例应该尽可能接近您期望实际用户使用的内容，因此您可能想从字典或类似的内容中随机提取单词作为您的输入。
多次运行该测试，至少 30 或 40 次。由于您使用的是随机数，因此您需要确保获得的平均最大负载接近算法的理论“期望”。期望只是平均值，但您仍然需要找到它，并且您的标准偏差/标准误差对该平均值越严格，您就越可以说您的经验平均值与理论期望相符。一次运行是不够的，因为第二次运行（很可能）会给出不同的答案。
然后，增加 N，例如 1000、10000 等。以对数方式增加，因为您的公式是对数的。随着 N 的增加，最大负载应按 ln(n) / ln(ln(n)) 的顺序增加。如果它以 3*ln(n) / ln(ln(n)) 的速率增加，则意味着您正在遵循他们在那次讲座中提出的理论。
这种实证测试还将向您展示您的方法在哪里失败。您的算法可能在 N < 1000 万（或其他数字）时运行良好，但超过此值，它就会开始崩溃。为什么会这样呢？也许您的代码对 32 位有一些限制，但没有意识到（即使用“float”而不是“double”）或其他一些实现细节。这些细节让你知道你的代码在实践中哪些地方可以很好地工作，然后随着你的实际需求的变化，你可以修改你的算法。也许让算法适用于非常大的数据集会使它对于非常小的数据集变得非常低效，反之亦然，因此精确地指出这种权衡将帮助您进一步描述如何使您的算法适应特定情况。始终是一项有用的技能。
编辑：证明为什么 log 函数的基数与大 O 表示法无关：
log N = log_10 (N) = log_b (N)/log_b (10)= (1/log_b(10)) * log_b(N)
1/log_b(10) 是一个常量，在大 O 表示法中，常量被忽略。碱基更改是免费的，这就是您在论文中遇到这种变化的原因。