我该如何决定何时重新散列整个哈希表？
3个回答
9
这很大程度上取决于您如何解决冲突。如果您使用线性探测，则负载因子高于60％时，性能通常会急剧下降。如果您使用双重哈希，负载因子为80-85％通常相当合理。如果您使用冲突链接，则负载因子通常可以保持在约150％左右或更高。
我有时甚至使用平衡树创建哈希表以解决冲突。在这种情况下，你几乎可以忘记再次哈希 - 性能直到项目数量超过表大小至少两个数量级才开始明显恶化。
我有时甚至使用平衡树创建哈希表以解决冲突。在这种情况下，你几乎可以忘记再次哈希 - 性能直到项目数量超过表大小至少两个数量级才开始明显恶化。
- Jerry Coffin
3
一般来说，你有一个包含N个元素的哈希表分布在M个插槽的数组中。
在实例化哈希表时，用户定义了一个百分比值（称为“growthFactor”），它被用于以下方式：
if (growthRatio < (N/M))
Rehash();
重新散列意味着你的M个插槽的数组应该被调整大小以包含更多元素（最好是当前大小的素数大于1倍或2倍），并且你的元素必须分布在新的较大数组中。
此类值应该设置在0.6和0.8之间。
- ebasconp
1
2仅供参考，通常称为“负载因子”，而不是“增长因子”。 - Jerry Coffin
0
一条经验法则是在表格填充到3/4时调整其大小。
- Craig Gidney
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接