为什么HashMap要重新哈希? [已关闭]

问题描述 投票:0回答:2

Java 中的 HashMap 使用单独的链接来处理冲突,这就是为什么您可以毫无问题地进行任意次数的插入。

我不明白的是HashMap需要重新散列的原因。

当哈希表中的条目数超过 负载因子和当前容量,哈希表被重新哈希 (即重建内部数据结构)使得哈希 表的桶数量大约是桶的两倍

HashMap 被扩展了,为什么?

这只是经典的单独链接的优化,以限制每个桶可以拥有的键的数量吗? (因为这些键具有相同的哈希值。)

java hashmap
2个回答
2
投票

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

这或多或少是正确的1

Java

HashMap 查找工作原理的简化版本

2
如下:

  1. 调用
    key.hashCode()
    来获取 32 位哈希码。
  2. 32位哈希码被简化为更小的整数,可以用作哈希桶数组的索引。
  3. 在选定的哈希桶中搜索其键等于我们正在查找的键的条目。
  4. 返回条目中存储的值。如果没有匹配,则返回
    null

假设地图中共有

N
个条目,当前有
B
个存储桶。

如果我们假设现有键的映射条目均匀分布在存储桶中,则意味着每个存储桶中大约有

L(N, B) = N / B
条目。

现在步骤 1、2 和 4 相对于

N
B
是恒定的。然而,搜索哈希桶的成本取决于桶中元素的数量。

在简单的实现中3,搜索成本将是

O(L)
。具体来说,您需要检查平均
L / 2
条目是否密钥在地图中,如果不在地图中,则需要检查
L

但正如我们之前所说,

L
实际上是桶
B
数量的函数。事实上,如果我们增加数量
B
,我们就会减少
L(N, B)

简而言之,重新哈希会增加存储桶的数量

B
,从而降低搜索哈希存储桶的平均成本,从而平均实现更快的查找。


1 - 你说:“因为这些键具有相同的哈希值”。这是不正确的。按键不一定具有相同的

hashCode
。哈希冲突发生在reduction步骤之后。
2 - 例如,这忽略了这样一个事实:对于链太长的任何哈希桶,Java 都会切换到红黑树表示。仅当存储桶中的键分布(显着)不均匀时才会发生这种情况。这与重新哈希无关,因此我们不需要在这里考虑它。
3 - 即忽略红黑树。事实上,这些不应该改变最终的结果。如果你愿意的话可以自己检查一下。


1
投票
当“桶”太满而影响查找时间、冲突和其他基于

initial capacity

load factor
 的哈希图参数(在 
HashMap 的 JavaDoc 中对此进行了解释)的因素时,需要对 Hashmap 进行重新哈希处理。

想象一下,您以列表的形式散列到

16
存储桶。那么索引将类似于 hashCode mod
16
。但是每个桶在链表中都可以有
1000's
的条目,因此仍然可以进行线性搜索来找到给定键的正确值。如果列表扩展到
256
个存储桶,那么索引现在将是 hashCode mod
256
(对于更多数量的存储桶,索引可能会更高)。但现在现有元素对于新列表大小来说位于错误的存储桶中,因此所有内容都需要重新哈希。这种重新散列会减少每个存储桶中的项目数量,但会消耗一些额外的内存。理想情况下,这种情况不会经常发生,并且可以根据数据的先验知识来设置初始大小和负载系数。

有几点需要注意:

  • hashCode 不一定是唯一的,这意味着无论上述模数如何,多个对象都可以散列到同一个存储桶。或者,如果模数发生变化,那么当重新哈希发生时,同一存储桶中的两个值现在可能位于不同的存储桶中。例如,如果哈希码是

    1234
    1334
    并且模数是
    100
    ,则它们将具有相同的索引
    (34)
    并且位于同一个存储桶中。如果模数为
    1000
    ,它们将具有不同的索引
    (234, 334)
    ,并最终位于不同的桶中。

  • 不同的是实现哈希图。上述解释没有考虑其他可能进一步减少开销的方法。

© www.soinside.com 2019 - 2024. All rights reserved.