我正在尝试实现一个通用的 HashTable。（这个问题是这里提出的问题的延续）
我已经为表大小固定的情况实现了通用哈希函数。但是，在实时情况下，使用大小最初固定为大约 2^32 位的 HashTable 是一个非常糟糕的主意，因为它可能会导致大量内存浪费。
所以，我现在要做的是动态增加 hast 表的大小，从某个初始值开始，只要它已满。
但是，当我这样做时，散列函数现在会将新值返回给先前散列的键。
除了用新的值重新散列以前散列的值之外，还有什么办法可以克服这个问题。
问问题
1038 次
1 回答
0
您无法避免重新散列：元素最终在哈希表中的位置取决于两三件事，具体取决于您的冲突解决策略：
- 元素的哈希码，
- 桌子的大小，以及
- 当您使用线性探测时，将它们放在同一个桶中的哈希码的存在与否也是先前元素的存在或不存在
如果你改变了这三个因素中的任何一个，你需要一个完整的rehash：除非你做了一些非常糟糕的事情，比如选择一个非主表大小，hashCode % tableSize当你改变时，决定位置的表达式的值将会不同。tableSize. 在线性探测中散列到同一桶的元素的存在或不存在也将发生变化。这就是为什么你需要一个完整的重新哈希。
于 2013-04-27T10:18:04.143 回答