如何测试哈希函数在最大负载方面是否良好?

这是一篇引人入胜的论文/讲座--让我希望我上过一些正式的算法课。

根据我刚刚读到的内容,我将在这里尝试一些答案,并随时投票否决我。不过,我希望你能更正一下,而不是仅仅投反对票:)我也要在这里交替使用n和n,这在某些圈子里是一个很大的“不”字,但既然我只是复制粘贴你的公式,我希望你能原谅我。

首先,日志的基础。这些数字以big-O表示法给出,而不是绝对公式。这意味着你在寻找“在ln(n)/ln(ln(n))的顺序上”的东西,不是期望得到一个绝对答案,而是随着n变大,n与最大碰撞次数的关系应该遵循这个公式。您可以绘制的实际曲线的细节将因实现而异(我对实际实现的了解还不足以告诉您什么是“好”曲线,只是它应该遵循big-O关系)。你发布的这两个公式实际上在big-O表示法中是等价的。第二个公式中的3只是一个常量,与特定的实现有关。效率较低的实现会有更大的常量。

考虑到这一点,我会进行经验测试,因为我的内心是一个生物学家,我受过训练,避免将硬性和快速的证据作为世界实际运行的指示。从N开始算起,比如说100,然后找到碰撞次数最多的箱子。这是你跑步的最大负荷。现在,您的示例应该尽可能接近您期望实际用户使用的内容,所以您可能希望随机从字典或类似于您输入的内容中提取单词。

多次运行该测试,至少30或40次。由于您使用的是随机数,因此您需要确保获得的平均最大负载接近算法的理论“期望值”。期望值只是平均值,但你仍然需要找到它,而且你的标准偏差/标准偏差越接近这个平均值,你就越能说你的经验平均值与理论期望值匹配。一次跑是不够的,因为第二次跑(很可能)会给出不同的答案。

然后,增加N,也就是说,1000,10000,等等,按对数增加,因为你的公式是对数的。当你的N增加时,你的最大负载应该以ln(N)/ln(ln(N))的顺序增加。如果它以3*ln(n)/ln(ln(n))的速率增加,那就意味着你遵循了他们在那堂课中提出的理论。

这种经验测试也会告诉你你的方法哪里出了问题。可能您的算法对N<1000万(或其他数字),但超过这个数字,它开始崩溃。为什么会这样?也许您的代码中有32位的限制而没有实现它(即使用“float”而不是“double”),或者其他一些实现细节。这些细节可以让您知道代码在实践中的哪些地方可以很好地工作,然后随着实际需求的变化,您可以修改算法。也许让算法在非常大的数据集上运行会使它在非常小的数据集上非常低效,反之亦然,所以精确地指出这种权衡将帮助您进一步描述如何使算法适应特定的情况。总是一种有用的技能。

log N = log_10 (N) = log_b (N)/log_b (10)= (1/log_b(10)) * log_b(N)

这里是一个粗略的开始,以解决这个问题涉及均匀分布和最大负荷。

将使用人员(p)和门(d)作为名称,而不是箱子、球、骨灰盒、盒子、桶或m和n。

给定一定数量的人,每个门都有一个精确的期望值。例如,有5个人和5扇门,预期的最大门正好比平均值(p/d)高1.2864{(1429-625)/625},最小门正好比平均值低-0.9616{(24-625)/625}。最高的门与平均值的距离的绝对值比最小的门稍大一点,因为所有的人都可以通过一扇门,但不小于零的人可以通过其中一扇门。人数众多(p/d>3000),则最高门距平均值的绝对值与最低门距的绝对值之差可以忽略不计。

对于奇数个门,中心门基本上为零,不可缩放,但所有其他门都可以从表示p=d的特定值缩放。d=5的四舍五入值为:

-1.163 -0.495 0* 0.495 1.163 *从-0.12慢慢接近零

根据这些值,您可以计算通过5个门(包括最大门)的任何人数的预期人数。除中间顺序的门外,与平均值的差异可通过sqrt(p/d)进行扩展。

预计通过最大门的人数,可以是5个门中的任何一个,=1.163*sqrt(p/d)+p/d。 =1.163*sqrt(10000)+10000=10116.3平方米 对于p/d<3000,这个等式的结果必须稍微增加。

-1.272 -0.643 -0.202 0.202 0.643 1.272

对于1000扇门,近似值为: -3.25, -2.95, -2.79 2.79, 2.95, 3.25

对于任何d和p,每个订购的门都有一个精确的期望值。希望是一个很好的近似值(有一个相对误差<1%)存在。某个地方的教授或数学家一定知道。

为了测试均匀分布,您将需要一个平均有序会话数(750-1000工作良好),而不是更多的人。不管怎样,有效会话之间的差异都很大。这就是随机性的本质。碰撞是不可避免的*

5门和6门的期望值是通过使用640位整数的纯暴力计算得到的,并对相应的相对门的绝对值的收敛性进行平均。 对于d=5和p=170: -5.19024 -2.7711 -0.973979 0.734434 2.66716 5.53372 (12.80976 15.2289 17.026021 18.734434 20.66716 23.53372)

我希望你能平均分配你的数据。

经过更多的研究和尝试和错误,我想我可以提供一些部分的方式来回答。

1. 首先, ln 和 log

2. max-load 可以定义为任何你喜欢的概率。使用的典型公式是

   1-1/n**c

1-1/n

举个例子可能最简单。

1000 你想要散列吗 1000 东西。说你也想知道 概率为 1-1/1000 或 0.999 .

这个 是最终相同的哈希值的最大数目-即冲突(假设哈希函数良好)。

用概率公式计算 k

Pr[ exactly k ] = ((e/k)**k)/e

然后通过累积 0..k 0.999 是 最大载荷 .

如。

Pr[0] = 0.37
Pr[1] = 0.37
Pr[2] = 0.18
Pr[3] = 0.061
Pr[4] = 0.015
Pr[5] = 0.003     // here, the cumulative total is 0.999
Pr[6] = 0.0005
Pr[7] = 0.00007

所以,在这种情况下 最大载荷 5 .

因此,如果我的哈希函数在我的数据集上运行良好,那么我应该期望相同哈希值(或冲突)的最大数目是 .

如果不是,则可能是由于以下原因:

2. 哈希函数不能很好地处理数据—请尝试使用随机数据。

3. 你的哈希函数工作不好。

我在问题中提到的其他测试也有助于查看哈希函数是否按预期运行。

顺便说一句,我的哈希函数工作得很好-除了短(1..4个字符)字符串。

我还实现了一个简单的拆分表版本,该版本将哈希值从2个位置中选择放置到最少使用的插槽中。这使冲突的数量减少了一半以上,意味着添加和搜索哈希表的速度要慢一些。

我希望这有帮助。