当前位置: 首页 > 面试题库 >

哈希表或哈希表中的重新哈希处理

常睿范
2023-03-14
问题内容

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

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

编辑:

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


问题答案:

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

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

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

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

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

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

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

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

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



 类似资料:
  • 哈希表 通过最简单的取模运算作为哈希算法 class HashNode(object): def __init__(self, id, data): self.id = id self.data = data self.next = None def __str__(self): return '(%d,%s)' %

  • REDIS_HASH (哈希表)是 HSET 、 HLEN 等命令的操作对象, 它使用 REDIS_ENCODING_ZIPLIST 和 REDIS_ENCODING_HT 两种编码方式: 字典编码的哈希表 当哈希表使用字典编码时, 程序将哈希表的键(key)保存为字典的键, 将哈希表的值(value)保存为字典的值。 哈希表所使用的字典的键和值都是字符串对象。 下图展示了一个包含三个键值对的哈希

  • Hashtbl 模块 Hashtbl模块实现了一个高效的,可变的查询表。如下创建一个哈希表: # let my_hash = Hashtbl.create 123456;; val my_hash : ('_weak1, '_weak2) Hashtbl.t = <abstr> 这个123456是哈希表的初始大小。这个值可以是你对数据量的一种猜测,但是哈希表有可能会 随着数据量的增多而变大,因此

  • 主要内容:Hashtable 类中的属性,Hashtable 类中的方法在 C# 中,Hashtable(哈希表) 类表示根据键的哈希代码进行组织的键(key)/值(value)对的集合,可以使用键来访问集合中的元素。也就是说当您需要使用键来访问指定元素时,可以选择使用哈希表。 Hashtable 类中的属性 下表中列出了 Hashtable 类中一些常用的属性: 属性 描述 Count 获取哈希表中包含的键值对的个数 IsFixedSize 获取一个值,用来表示哈希

  • 3. 哈希表 下图示意了哈希表(Hash Table)这种数据结构。 图 26.12. 哈希表 如上图所示,首先分配一个指针数组,数组的每个元素是一个链表的头指针,每个链表称为一个槽(Slot)。哪个数据应该放入哪个槽中由哈希函数决定,在这个例子中我们简单地选取哈希函数h(x) = x % 11,这样任意数据x都可以映射成0~10之间的一个数,就是槽的编号,将数据放入某个槽的操作就是链表的插入操作

  • 哈希是键/值对 如果你想按名字查询,那么需要哈希。哈希的键必须唯一,但值可以是任意标量。 有时候你仍然会看到人们称它为“关联数组”,但不要想当然的把它作为数组。 通过键/值对列表来创建哈希 使用键/值对列表创建哈希: my %stooges = ( 'Moe', 'Howard', 'Larry', 'Fine', 'Curly', 'Howard', 'Iggy'