algorithm - 如何为动态哈希表实现哈希函数？

Question

我正在尝试实现一个通用的哈希表。(这个问题是问题 here 的延续)

我已经为表的大小固定的情况实现了通用哈希函数。但是，在实时情况下，使用大小最初固定为大约 2^32 位的 HashTable 是一个非常糟糕的主意，因为它可能会导致大量内存浪费。

所以，我现在要做的是，当 hast 表已满时，从某个初始值动态增加它的大小。

但是，当我执行此操作时，哈希函数将现在将新值返回给之前经过哈希处理的键。

除了用新值重新散列以前散列的值之外，还有什么方法可以解决这个问题。

Answer 1

您无法避免重新哈希:元素在哈希表中结束的桶的位置取决于两个或三个因素，具体取决于您的冲突解决策略:

• 元素的哈希码，
• 表格的大小，以及
• 当您使用线性探测时，是否存在具有哈希码的先验元素也会将它们放在同一个桶中

如果你改变了这三个因素中的任何一个，你需要一个完整的重新散列:除非你做了一些非常糟糕的事情，比如选择一个非主要的表大小，hashCode % tableSize 表达式的值当您更改 tableSize 时，确定位置将有所不同。在线性探测中散列到同一个桶的元素的存在与否也会发生变化。这就是为什么您需要完全重新哈希。