19

当大小超过 maxthreshold 值时，如何在 hashmap 或 hashtable 中完成重新散列过程？

所有对都只是复制到一个新的存储桶数组中吗？

编辑：

重新散列后同一个桶（链表中）的元素会发生什么？我的意思是他们会在重新散列后留在同一个桶中吗？

4

3 回答 3

22

问题中的最大阈值称为负载因子。

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

重新散列可以在两种情况下完成：

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

  2. M'/n 比率下降到非常低的值，例如 0.1

在这两种情况下，m' 都是当前条目数。此外，这两种情况都要求将当前条目转移到更大或更小的哈希表中。

在问题的上下文中，重新散列是将散列函数应用于条目以将它们移动到另一个散列表的过程。可以使用之前使用的散列函数或完全使用新函数。

请注意：当发生碰撞时，也会进行重新散列。（这也是一种处理碰撞的方法。）

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

于 2012-05-23T13:23:13.463 回答
16

当映射中的元素数量达到最大阈值时，就会对哈希映射进行重新散列。

通常负载因子值为 0.75，默认初始容量值为 16。一旦元素数量达到或超过容量的 0.75 倍，就会发生 map 的重新散列。在这种情况下，当元素数量为 12 时，就会发生重新散列。(0.75 * 16 = 12)

当重新散列发生时，可以使用新的散列函数，甚至可以使用相同的散列函数，但存在值的存储桶可能会发生变化。基本上，当重新散列发生时，桶的数量大约翻了一番，因此必须放置值的新索引会发生变化。

在重新散列时，每个桶的链表按顺序颠倒。发生这种情况是因为 HashMap 没有在尾部附加新元素，而是在头部附加新元素。因此，当重新散列发生时，它会读取每个元素并将其插入到头部的新存储桶中，然后继续从旧映射中添加下一个元素到新映射的头部，从而导致链表反转。

如果有多个线程处理相同的哈希映射，则可能导致无限循环。

可以在此处找到说明在上述情况下如何发生无限循环的详细说明：http: //mailinator.blogspot.hu/2009/06/beautiful-race-condition.html

如果必须根据键对插入到地图中的元素进行排序，则可以使用 TreeMap。但是如果键的顺序无关紧要，HashMap 会更有效。

于 2015-03-02T14:03:00.747 回答
11

散列 - 重新散列和竞争条件

基本上，在创建哈希映射时，集合会为其分配一个默认容量（2^4，即 16）。在地图中添加元素的后期阶段以及在接近初始定义容量的某个阶段之后，需要 ReHashing 来保持性能。

为集合定义了 LoadFactor（据说可以达到 0.75），这指定了时间和空间的良好索引。

  • 更大的负载因子 => 更低的空间消耗但更高的查找
  • 更小的负载系数 => 与所需的元素数量相比，空间消耗更大。

Java 规范建议良好的负载因子值为 .75

因此，假设您最大要求在哈希中存储 10 个元素，然后考虑到 Good Loadfactor .75 = 在集合中添加 7 个元素后会发生重新哈希。如果您的要求（在这种情况下）不符合 7，那么 Rehashing 将永远不会发生。

如果没有大量元素要存储在 hashmap 中，那么创建具有足够容量的 HashMap 总是好的；这比让它执行自动重新散列更有效。

RACE 条件：在对存储在给定存储桶的链表中的内部元素进行重新哈希处理时。他们的顺序相反。假设有两个线程同时遇到竞争条件，那么由于顺序已更改，因此在遍历时有可能第二个线程进入无限循环。

于 2014-08-08T19:44:28.173 回答