c - 缩小哈希表的大小是否有意义？什么时候？

Question

我的哈希表实现具有在负载达到约 70% 时调整表大小的功能。我的哈希表是通过单独的冲突链接实现的。

我应该在任何时候缩小哈希表的大小还是应该让它保持原样是否有意义？否则，如果我在负载为 70% 时增加大小（几乎翻倍，实际上我遵循：Link），当负载达到 30% 或更低时，我是否应该将其缩小？

Answer 1

如果你有一个高质量的散列函数，散列表不必有素数长度（见这里）。您可以将它们设为 2 的幂，这大大加快了索引计算的速度。

为什么这与问题有关？因为当您缩小二次幂哈希表时，您可以将所有条目留在它们所在的下半部分，并简单地将 slot 中的链表i（从上半部分）附加到 slot 中的链表上i - n/2。

Answer 2

如果内存很便宜，别管它。如果内存很昂贵，请按照您的建议调整滞后大小。完成后，分析结果以确保它表现良好并且没有做一些愚蠢的事情。

Answer 3

您是为通用目的编写哈希表，还是有特定目的？我建议不要为一般实现调整较小的大小。这将使您的表格保持简单，并避免在表格经常被填满和清空的情况下发生内存抖动。如果您最终遇到需要减小哈希表大小的情况，请在该时间点扩展它。

Answer 4

第一个想法：增长哈希表的唯一原因是如果冲突太多，哈希表性能会降低。当它的负载超过 70% 时增长表是一个很好的经验法则，以防止这种情况发生，但这只是一个经验法则。更好的是跟踪冲突的数量，并且仅在它们超过某个限制或达到某个冲突比率时才增长哈希表。毕竟，你为什么要增加一个加载了 90% 却没有一次冲突的哈希表呢？它不会有任何优势。

第二个想法：缩小哈希表的唯一原因是为了节省内存，但缩小它可能会增加冲突的数量，从而降低查找性能。这是经典的速度与内存权衡，为什么要自己解决？把它留给使用你的代码的人。永远不要自己收缩，而是提供收缩方法。如果需要低内存使用率，那么使用您的代码的任何人都可以定期调用shrink。如果需要最大性能，那么任何使用您的代码的人都不应调用收缩。其他人都可以使用某种启发式方法来决定是否以及何时调用收缩。

第三个想法：在增长或收缩时，始终以在操作后保证一定负载因子的方式增长/收缩。例如，在增长时，总是增长到之后的负载因子为 50%，而在收缩时，总是收缩到之后的负载因子为 70%。当然，这并没有说明冲突的数量，因此在增长/收缩后立即添加元素可能会导致哈希表再次增长，但这是不可避免的，因为模拟增长/收缩的效果通常过于昂贵。一旦没有计划进一步的修改，通常也会调用收缩，因此它应该节省内存而不是避免将来再次增长。

最后一个想法：对于您做出的每一个决定，您都会使哈希表对某些用例更好，而对其他用例则更糟。如果您知道如何使用您的哈希表，这将不是问题。然而，如果你不这样做，而且通常你不这样做，为什么要自己做出这些决定呢？只是委托他们。允许您的代码用户自定义所有小细节，例如增加或缩小多少，方法是允许在创建哈希表时设置所有这些因素，或者允许您的哈希表具有委托函数（您的回调函数）不确定该怎么做时总是可以问）。这样，即使在运行时，您的代码的每个用户都可以针对他们需要的任何使用场景自定义您的代码。