java - 如何获得在哈希表中使用的最佳数字？

Question

如问题所述，如何计算要使用的最佳数量以及如何激励它？

如果我们要构建一个使用以下哈希函数的哈希表:

h(k) = k mod m, k = key

所以一些消息来源告诉我:

1. 使用要插入的元素个数作为m的值
2. 使用与 m 相近的质数
3. java 简单地使用 31 作为它们的 m 值
4. 有些人告诉我用 2^n 的闭素数作为 m

此时我很困惑，不知道为 m 使用什么值。例如，如果我们使用 m 的表大小，那么如果我们想扩展表大小会怎样？然后我是否必须使用 m 的新值重新散列所有值。如果是这样，为什么 Java 只使用 31 作为 m 的素数。

我还听说表的大小应该是哈希表中元素总数的两倍，这是每次重新哈希时的结果。但是，当我们应该使用 m=20 来创建额外的空白空间时，为什么我们将 m=10 用于包含 10 个元素的表格？

有人能帮我理解如何根据不同的场景计算要使用的 m 的值，比如当我们想要一个静态的(我们知道我们只会像 10 个元素一样插入)或动态的(在某个特定之后重新散列)限制)哈希表。

让我们通过以下示例说明我的问题:

我得到值 {1,2,...,n}

问题:如果我必须在哈希函数中使用 mod 除法，m 的优化值是多少？

场景 1:n = 100？

场景 2:n = 5043？

补充问题:如果我们使用开放或封闭哈希表，m 值哈希函数会有所不同吗？

请注意，我现在不需要了解 Java 的哈希表，而是一般的哈希表，我必须在其中使用 divsion mod 哈希函数。

感谢您的宝贵时间!

Answer 1

这里有几个问题:1) m 应该等于什么？2) 你的哈希表中应该有多少可用空间？3) 你应该让你的 table 的大小是质数吗？

1) 正如评论中提到的，您描述的 h(k) 不是哈希函数，它为您提供了哈希表的索引。这个想法是每个对象都会产生一些哈希码，它是一个正整数。您使用散列码来确定将对象放在散列表中的什么位置(以便您以后可以再次找到它)。您显然不想要大小为 MAX_INT 的哈希表，因此您选择了大小为 m 的哈希表。然后对于任何对象，您获取其哈希码，计算 k % m，现在您在区间 [0, m-1] 中有一个整数，这是哈希表中的有效索引。

2) 由于哈希表的工作原理是使用哈希码来查找对象在表中的位置，因此如果多个项目被分配到同一位置，您就会遇到麻烦。这称为碰撞。每个哈希表实现都必须处理冲突，要么将项目放入附近的位置，要么在每个位置保留项目的链接列表。无论采用何种解决方案，更多的冲突都意味着哈希表的性能下降。因此，建议您不要让哈希表填满，否则更容易发生冲突。保持哈希表的数量至少是项目数量的两倍是减少冲突概率的常见建议。显然，这意味着您必须在表格填满时调整其大小。是的，这意味着您必须重新散列每个项目，因为当您以不同的值取模时，它会进入不同的位置。这就是哈希表的隐藏成本:它以恒定时间运行(假设很少或没有冲突)，但它可能具有很大的系数(分摊调整大小、重新哈希等)。

3) 通常还建议您将哈希表的大小设为质数。这是因为在某些常见用例中，它往往会在哈希表中产生更好的项目分布，从而避免冲突。我不会在这里给出完整的解释，而是会向您推荐这个优秀的答案:Why should hash functions use a prime number modulus?