一尘不染

在哈希图或哈希表中重新哈希处理

algorithm

当大小超过maxthreshold值时,如何在哈希表或哈希表中进行重新哈希处理?

是否所有对都都复制到新的存储桶阵列中?

编辑:

重新哈希后,同一存储桶(链接列表中)中的元素会发生什么情况?我的意思是说,他们在重新哈希处理后会留在同一个桶中吗?


阅读 367

收藏
2020-07-28

共1个答案

一尘不染

问题中的最大阈值称为负载系数。

建议负载系数约为0.75。负载因子定义为(m / n),其中n是哈希表的总大小,m是在需要增加基础数据结构的大小之前可以插入的首选条目数。

可以在两种情况下进行重新哈希处理:

  1. 当当前的m / n比增加到超过负载系数时

  2. M’/ n比降到非常低的值,例如0.1

在两种情况下,m’是当前条目数。同样,这两种情况都要求将当前条目转移到更大或更小的哈希表中。

在问题的上下文中,重新哈希处理是将哈希函数应用于条目以将其移动到另一个哈希表的过程。可以使用之前使用的哈希函数或完全使用新函数。

请注意:当发生冲突时,也会进行重新哈希处理。(这也是一种处理冲突的方法。)

要添加更多上下文和详细讨论,请访问我的博客Hashing
Basics

2020-07-28