Java 中的 HashMap 使用单独的链接来处理冲突,这就是为什么您可以毫无问题地进行任意次数的插入。
我不明白的是HashMap需要重新散列的原因。
当哈希表中的条目数超过 负载因子和当前容量,哈希表被重新哈希 (即重建内部数据结构)使得哈希 表的桶数量大约是桶的两倍
HashMap 被扩展了,为什么?
这只是经典的单独链接的优化,以限制每个桶可以拥有的键的数量吗? (因为这些键具有相同的哈希值。)
这只是经典分离链接的优化,以限制每个桶可以拥有的键的数量(因为这些键具有相同的哈希值)?
这或多或少是正确的1。
JavaHashMap
查找工作原理的简化版本
2如下:
key.hashCode()
来获取 32 位哈希码。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步骤之后。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)
,并最终位于不同的桶中。
不同的是实现哈希图。上述解释没有考虑其他可能进一步减少开销的方法。