HashMap 内部算法

定位 key 位于 table 中的位置

public V get(Object key) 方法来看在 HashMap 内部是如何分布 key 的。

第一步是计算 key 在 HashMap 内部的哈希值:如果 key 值为 null 则直接返回 0,否则使用 hashCode() 方法获取 key 的原始哈希值 h,然后计算 key 的内部哈希值,计算公式为 h ^ (h >>> 16)。一次运算的过程如下:

       h = hashCode(): 0000 1111 1111 0000 0000 0000 0101 0101
             h >>> 16: 0000 0000 0000 0000 0000 1111 1111 0000
hash = h ^ (h >>> 16): 0000 1111 1111 0000 0000 1111 1010 0101

在计算 key 的内部哈希值时,会保留 key 的原始哈希值高 16 位值不变,低 16 位值会与高 16 位值进行 异或 运算,这一步中的算法是与计算 key 在 HashMap 的 table 中位置相关的。

第二步是计算 key 在 HashMap 的 table 中的位置:根据 key 的内部哈希值来决定 key 在 table 中的位置,计算公式为 (table.length - 1) & hash。一次运算的过程如下:

    hash = h ^ (h >>> 16): 0000 1111 1111 0000 0000 1111 1010 0101
         table.length - 1: 0000 0000 0000 0000 0000 0000 1111 1111
(table.length - 1) & hash: 0000 0000 0000 0000 0000 0000 1010 0101

此处需要注意 HashMap 中的一个限制:table 的长度总会是 2 的幂次。在计算 key 位于 table 中的具体位置时,计算结果只会与 key 的内部哈希值的低位有关,为了让 key 的原始哈希值的高位也参与到计算过程中来,所以在第一步计算 key 内部哈希值时采用了将原始哈希值高 16 位与低 16 位进行异或的运算过程。

扩容 table

当元素个数达到 threshold 个时,HashMap 便会对 table 进行扩容,newTable 的容量是 oldTable 容量的两倍。

在 OpenJDK 中的实现

OpenJDK 7 中 HashMap 的扩容算法是从 oldTable 中各个队列的队头读取元素,然后逐个按序插入到 newTable 新位置中队列的队尾,该过程中会 反转哈希槽上的链表元素顺序,具体源码请见 GitHub。一次扩容示例过程如下:

// 扩容之前,哈希表槽数为 2
+-+
| |
+-+  +-+  +-+
|3|->|7|->|5|->NULL
+-+  +-+  +-+

// 扩容之后,哈希表槽数为 4
+-+
| |
+-+
|5|->NULL
+-+
| |
+-+  +-+
|7|->|3|->NULL
+-+  +-+

该算法在并发场景下可能会产生死循环问题。例如上例中的数据,扩容之前为 3->7,扩容之后为 7->3,当两个线程交替执行扩容算法时,就可能会产生 3<->7 的数据,从而产生了死循环。具体分析请见文章 《疫苗:JAVA HASHMAP的死循环》

在 OracleJDK 中的实现

OracleJDK 8 中 HashMap 扩容算法是将 oldTable 中哈希槽上的链表整体迁移到 newTable 中,该过程中会 保留哈希槽上的链表元素顺序,因此不会产生如 OpenJDK 8 中 HashMap 的死循环问题,一次扩容示例过程如下:

// 扩容之前
+-+
| |
+-+  +-+  +-+
|3|->|7|->|5|->NULL
+-+  +-+  +-+

// 扩容之后
+-+
| |
+-+
|5|->NULL
+-+
| |
+-+  +-+
|3|->|7|->NULL
+-+  +-+

最后更新于