为什么hashmap被重新散列(在java中)?关闭

这只是对经典的分离链接的优化,以限制每个bucket可以拥有的密钥数量吗(因为这些密钥具有相同的哈希)?

这或多或少是正确的 ^1. .

简化版本 ^2. 一个Java HashMap 查找工作如下:

1. 这个 key.hashCode() 被调用以获得32位哈希代码。
2. 32位散列码被缩减为较小的整数,该整数可以用作散列桶阵列的索引。
3. 在选定的哈希桶中搜索一个条目,该条目的关键字等于我们要查找的关键字。
4. 将返回存储在条目中的值。如果没有匹配, null 而是返回。

让我们说,我们总共有 N 地图中的条目,并且当前有 B 水桶。

如果我们假设现有密钥的映射条目在bucket上均匀分布,这意味着大致有 L(N, B) = N / B 每个bucket中的条目。

现在,步骤1、2和4相对于 N 和 B 然而,搜索散列桶的成本取决于该桶中的元素的数量。

在一个天真的实现中 ^3. 搜索的费用是 O(L) 。具体来说,您需要平均检查 L / 2 条目(如果密钥在映射中),并且 L 如果不是的话。

但正如我们之前所述, L 实际上是桶数的函数 B 。事实上,如果我们 增长 数字 B ,我们减少 L(N, B) .

简言之,重新哈希会增加bucket的数量 B 这反过来又减少了 平均的 搜索哈希桶的成本,导致 更快 平均查找数。

^{1-你说: “因为这些密钥具有相同的哈希” 。这是不正确的。钥匙不一定相同 hashCode 。哈希冲突发生在 减少 步
2-例如,这忽略了一个事实,即对于任何链过长的哈希桶,Java都会切换到红黑树表示。只有当关键帧在存储桶之间的分布(明显)不均匀时,才会发生这种情况。这是独立于重洗的,因此我们不需要在这里考虑它。
3-也就是说,忽略红黑树。事实上,这些不应该改变最终结果。如果你想的话,自己检查一下。}

当“bucket”已满,从而影响基于的Hashmap参数的查找时间、冲突和其他因素时,需要重新哈希映射 initial capacity 和 load factor 在JavaDoc中对其进行了解释 HashMap .

想象一下你被散列到 16 列表形式的bucket。然后索引将类似于hashCode mod 16 。但每个水桶都可以 1000's 的条目,因此仍然可以进行线性搜索来找到给定关键字的正确值。如果列表扩展到 256 buckets,那么索引现在将是hashCode mod 256 (或者可能更高,表示桶数越多)。但现在,现有元素在新列表大小的错误桶中,因此需要重新处理所有内容。这种重新散列以一些额外的内存为代价,减少了每个存储桶中的项目数量。理想情况下,这种情况不会经常发生,并且基于数据的先验知识可以选择设置初始大小以及负载系数。

有几点需要注意:

• hashCode不一定是唯一的,这意味着无论上面提到的模数如何,多个对象都可以散列到同一个bucket。或者,如果模量发生变化,当重新灰化发生时,同一个桶中的两个值现在可能在不同的桶中。例如,如果哈希代码是 1234 和 1334 模量为 100 ,它们将具有相同的索引 (34) 在同一个桶里。如果模量为 1000 ,它们将具有不同的索引 (234, 334) 并最终进入不同的桶中。

• 有不同的是实现了散列映射。上面的解释没有考虑可能进一步减少开销的其他方式。