我正在研究算法类的哈希表，我对负载因子感到困惑。为什么负载因子 n/m 很重要，“n”是元素的数量，“m”是表槽的数量？另外，为什么这个加载因子等于 n(j) 的预期长度，当所有元素都存储在一个槽中时，哈希表中槽 j 处的链表？
问问题
1427 次
2 回答
3
哈希表的关键属性是查找元素所需的预期常数时间。*
为了实现这一点，哈希表的实现者必须确保对哈希表的每个查询都返回低于某个固定数量的步骤。
如果您有一个带有m桶的哈希表并且无限期地添加元素（n>>m即遍历不断增加的链表所需的运行时间将超过对存储桶的查找）。
那么，我们如何才能实现列表不增长呢？好吧，您必须确保列表的长度受某个固定常数的限制——我们如何做到这一点？好吧，我们必须添加额外的桶。
如果哈希表实现得很好，那么用于将元素映射到桶的哈希函数应该将元素均匀地分布在桶中。如果散列函数这样做，那么列表的长度将大致相同。
如果元素分布均匀，其中一个列表有多长？显然，我们将得到元素总数除以桶数，即负载因子 n/m（每个桶的元素数 = 每个列表的预期/平均长度）。
因此，为了确保恒定的时间查找，我们要做的是跟踪负载因子（再次：列表的预期长度），以便当它超过固定常数时，我们可以添加额外的桶。
当然，还有更多的问题，比如如何重新分配你已经存储的元素或者你应该添加多少桶。
要带走的重要信息是，需要加载因子来决定何时向哈希表添加额外的桶——这就是为什么它不仅“重要”而且至关重要。
当然，如果你将所有元素映射到同一个桶中，那么每个列表的平均长度就没有多大价值了。所有这些东西只有在你均匀地分布在桶中时才有意义。
*注意预期- 我不能强调这一点。听到“哈希表具有恒定的查找时间”很典型。他们不！最坏的情况总是 O(n)，你不能让它消失。
于 2015-10-15T13:17:10.110 回答
0
添加到现有的答案，让我快速推导一下。
考虑表中任意选择的存储桶。让X_i是指示随机变量，1如果ith元素插入到这个元素中，则它等于，0否则。
我们想找到E[X_1 + X_2 + ... + X_n].
通过期望的线性，这等于E[X_1] + E[X_2] + ... E[X_n]
现在我们需要E[X_i].简单地通过期望值的定义来找到This is(1/m) 1 + (1 - (1/m) 0) = 1/m的值。所以总结 all 的值i's，我们得到1/m + 1/m + 1/m n时间。这等于n/m.我们刚刚发现了插入随机桶的预期元素数量，这就是负载因子。
于 2015-10-16T09:49:20.383 回答