缩小哈希表的大小有意义吗?何时缩小? (注:哈希表是一种常见的数据结构,用于存储键值对。)

4
我的哈希表实现有一个函数,在负载达到约70%时调整哈希表的大小。我的哈希表使用分离链接处理冲突。
在任何时候,将哈希表的大小调整为更小的值是否有意义,还是应该保持原样?否则,如果我在负载达到70%时增加大小(实际上几乎翻倍,我遵循这个:Link),那么当负载降至30%或以下时,我应该将其调整为更小的大小吗?
4个回答

4
哈希表不需要长度为质数,如果你有一个好的质量哈希函数的话(参见此处)。你可以让它们成为2的幂,这将大大加速索引计算。
那么这对问题有什么影响呢?因为当你缩小一个2的幂哈希表时,你可以将底部一半的所有条目保留在原位,并将槽 i 中的链接列表(来自上半部分)附加到槽 i- n / 2 的链接列表中。

这是非常好的链接。谢谢分享。 你关于缩小并保留另一半的观点也很有道理。 - Jack

3

如果内存便宜,就别动它。如果内存昂贵,按照你建议的方法使用滞后调整来调整大小。完成后,请对结果进行分析以确保其性能良好并且没有做出愚蠢的事情。


1
你是为了通用目的编写哈希表,还是有特定目的?我建议不要在一般实现中调整大小。这将使您的表格保持简单,并在填充和清空表格经常发生时防止内存抖动。如果最终遇到哈希表需要缩小的情况,请在那个时间点进行扩展。

0

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

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

第三个想法:无论是增长还是缩小,始终应以一定的负载因子来保证增删操作后的负载因子。例如,当增长时,总是增长到负载因子为50%,而当收缩时,总是以在操作之后负载因子为70%的方式缩小。 当然,这并不代表哈希表中没有碰撞发生。因此,在增长/收缩后立即添加元素可能会导致哈希表再次增长,但由于模拟增长/收缩的效果通常太昂贵,这是不可避免的。同时,当没有计划进一步修改哈希表时,通常会调用收缩,因此它应该节省内存,而不是为了避免将来需要再次增长。
最后一个想法:对于你所做的每个决策,你都会为某些使用情况使哈希表变得更好,而对其他情况则更差。如果你知道如何使用哈希表,这不会成为问题。但是,通常情况下你不知道如何使用哈希表,为什么要自己做出这些决策呢?只需委托它们。允许代码的用户自定义所有细节,例如增加或缩小多少,可以通过在创建哈希表时允许设置所有这些因素,或通过允许哈希表具有委托函数(可以在不确定要做什么时始终询问的回调函数)来实现。这样,您代码的每个使用者都可以根据所需的使用场景在运行时自定义您的代码。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接