当哈希表或散列表的大小超过最大阈值时，如何进行重新散列过程？
是否所有键值对都会被复制到一个新的桶数组中？
编辑：
在重新散列后，同一桶中的元素（在链表中）会发生什么？我的意思是它们是否会留在同一桶中？
哈希表中的重新哈希过程
20
- a Learner
5
3http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashMap.java#HashMap.resize%28int%29 - JB Nizet
当您重新散列并将所有内容移动到新位置（桶等）时，旧元素也会再次进行重新散列，并根据其新哈希码存储在新桶中。用于存储元素的旧空间将被垃圾回收。 - dharam
@dharam：因此，结论是在重新哈希之后，位于同一桶中的元素可能不再位于同一桶中，而不在同一桶中的元素可能会在重新哈希后位于同一桶中？ - a Learner
是的，你说得完全正确 :) - dharam
问“通常按照教科书上的方法怎么做”并不等同于“在这个特定实现中如何完成”。例如，Java对于少于8个条目的桶使用链表节点，但对于8个或更多的桶使用树形节点。 - tucuxi
3个回答
22
问题中的最大阈值称为负载因子。
建议将负载因子设置为约0.75。负载因子定义为(m/n)，其中n是哈希表的总大小，m是在需要增加基础数据结构的大小之前可以插入的首选条目数。
重新散列可以在两种情况下进行：
当当前m'/n比率超过负载因子时
M'/n比率下降到非常低的值，例如0.1
在这两种情况下，m'是当前条目数。此外，在两种情况下都要求将现有条目移动到更大或更小的哈希表中。
在问题的上下文中，重新散列是将条目应用于哈希函数以将它们移动到另一个哈希表的过程。可以使用先前使用过的哈希函数或者使用全新的函数。
请注意：当发生冲突时也会执行重新散列。（这是处理冲突的一种方式。）
要了解更多内容和详细讨论，请访问我的博客哈希基础知识
- dharam
4
1"可以使用相同的哈希函数": 当桶的数量增加时，新桶将如何被使用？ - Aravind
我相信新的桶（和重新哈希的表）将与原始哈希表一样被使用，也就是说，在重新哈希后，使用更多的桶就像往常一样。 - Tim Biegeleisen
你已经掌握了要点。在高级的地图实现中，重新哈希是一个复杂的过程。它需要一段时间，在这段时间内，多个线程参与其中，以保持每个线程的平摊成本较低。因此，释放原始数组的空间需要合理的时间。在此期间，两个数组都存在并且完全可用 :) - dharam
请注意：当发生冲突时，也会进行重新散列。在这种情况下的阈值是多少？如何计算桶中允许的最大元素数量？ - Gusev Slava
20
当哈希表中的元素数量达到最大阈值时，会对哈希表进行重新哈希。
通常情况下，负载因子的值为0.75，初始容量的值为16。一旦元素数量达到或超过容量的0.75倍，则会进行重新哈希。例如，当元素数量为12时，就会发生重新哈希。（0.75 * 16 = 12）
在重新哈希时，可以使用新的哈希函数或相同的哈希函数，但存储值的桶可能会改变。基本上，当重新哈希发生时，桶的数量将近翻倍，因此值必须放置的新索引也会发生变化。
在重新哈希时，每个桶的链表顺序都会被反转。这是因为HashMap不会将新元素附加到尾部，而是将其附加到头部。因此，在重新哈希时，它会读取每个元素并将其插入到新桶的头部，然后继续从旧地图的头部添加下一个元素到新地图的头部，导致链表反转。
如果有多个线程处理同一个哈希表，可能会导致无限循环。
在上述情况下详细解释无限循环如何发生可以在此处找到：http://mailinator.blogspot.hu/2009/06/beautiful-race-condition.html 如果要按键对插入的元素进行排序，则可以使用TreeMap。但是，如果键的顺序不重要，则HashMap将更有效率。
通常情况下，负载因子的值为0.75，初始容量的值为16。一旦元素数量达到或超过容量的0.75倍，则会进行重新哈希。例如，当元素数量为12时，就会发生重新哈希。（0.75 * 16 = 12）
在重新哈希时，可以使用新的哈希函数或相同的哈希函数，但存储值的桶可能会改变。基本上，当重新哈希发生时，桶的数量将近翻倍，因此值必须放置的新索引也会发生变化。
在重新哈希时，每个桶的链表顺序都会被反转。这是因为HashMap不会将新元素附加到尾部，而是将其附加到头部。因此，在重新哈希时，它会读取每个元素并将其插入到新桶的头部，然后继续从旧地图的头部添加下一个元素到新地图的头部，导致链表反转。
如果有多个线程处理同一个哈希表，可能会导致无限循环。
在上述情况下详细解释无限循环如何发生可以在此处找到：http://mailinator.blogspot.hu/2009/06/beautiful-race-condition.html 如果要按键对插入的元素进行排序，则可以使用TreeMap。但是，如果键的顺序不重要，则HashMap将更有效率。
- Melwin
2
我的唯一问题是，如果重新散列发生在每13个元素中，那么它将是次优的，对吧。假设， num_buckets = 16，
total_no_entries = - chaitra.kear
最初，桶的数量为16，当第13个元素被遇到时，将进行重新哈希操作，桶的数量将加倍。这将使桶的总数达到32个，并且下一次重新哈希发生在超过0.75 * 32，即第25个元素时。然后，桶的数量再次加倍为64，并且下一次重新哈希应在超过0.75 * 64，即第49个元素时发生。类似地，它继续进行，您可以看到它不是在每个第13个元素之后重新哈希，而是保持加倍。如果n是重新哈希发生的点，则下一次重新哈希将在2 * n - 1处发生。 - Melwin
11
哈希 - 重哈希和竞争条件
创建哈希映射时，集合会为其分配默认容量（即2 ^ 4，即16）。在向地图中添加元素后，在接近初始定义的容量的某个阶段之后，需要进行重新哈希以保持性能。
集合定义了负载因子（称为.75），这指定了时间和空间的良好索引。
- 较大的负载因子 => 较低的空间消耗但更高的查找次数
- 较小的负载因子 => 比所需元素的空间消耗大。
Java规范建议使用0.75作为良好的负载因子值。
因此，假设您最多需要存储10个元素，则考虑到良好的负载因子0.75 = 在集合中添加7个元素后将进行重新哈希。如果您的要求在这种情况下不超过7，则不会发生重新哈希。
如果要存储的元素数量非常大，则最好使用足够容量创建HashMap；这比让它执行自动重新哈希更有效率。
竞争条件：在进行重新哈希时，存储在给定桶中的内部元素会以相反的顺序存储。假设两个线程在同一时间遇到竞争条件，则第二个线程在遍历时可能会进入无限循环，因为顺序已更改。
- Manjul
2
2在发布答案之前，请检查您的答案在预览窗口中的显示效果。您可能会发现缺少一些换行符，可以通过在前一行末尾添加两个空格来解决这个问题。 - skrrgwasme
2Hashmap 的默认大小为 16。 - sid_09
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接