本文将通过如下简单的代码来分析 HashMap 的内部数据结构的变化过程.
- public static void main(String[] args) {
- Map<String, String> map = new HashMap<>();
- for (int i = 0; i <50; i++) {
- map.put("key" + i, "value" + i);
- }
- }
1 数据结构说明
HashMap 中本文需要用到的几个字段如下:
下面说明一下几个字段的含义
- 1)table
- // HashMap 内部使用这个数组存储所有键值对
- transient Node<K,V>[] table;
Node 的结构如下:
可以发现, Node 其实是一个链表, 通过 next 指向下一个元素.
2)size
记录了 HashMap 中键值对的数量
3)modCount
记录了 HashMap 在结构上更改的次数, 包括可以更改键值对数量的操作, 例如 put,remove, 还有可以修改内部结构的操作, 例如 rehash.
4)threshold
记录一个临界值, 当已存储键值对的个数大于这个临界值时, 需要扩容.
5)loadFactor
负载因子, 通常用于计算 threshold,threshold = 总容量 * loadFactor.
2.new HashMap
new HashMap 的源码如下:
- /**
- * The load factor used when none specified in constructor.
- * 负载因子, 当 已使用容量> 总容量 * 负载因子 时, 需要扩容
- */
- static final float DEFAULT_LOAD_FACTOR = 0.75f;
- public HashMap() {
- this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
- }
此时, HashMap 只初始化了负载因子(使用默认值 0.75), 并没有初始化 table 数组. 其实 HashMap 使用的是延迟初始化策略, 当第一次 put 的时候, 才初始化 table(此时 table 是 null).
3.table 数组的初始化
当第一次 put 的时候, HashMap 会判断当前 table 是否为空, 如果是空, 会调用 resize 方法进行初始化. resize 方法会初始化一个容量大小为 16 的数组, 并赋值给 table. 并计算 threshold=16*0.75=12. 此时 table 数组的状态如下:
4.put 过程
map.put("key0", "value0");
首先计算 key 的 hash 值, hash("key0") = 3288451 计算这次 put 要存入数组位置的索引值: index=(数组大小 - 1) & hash = 3 判断 if (table[index] == null) 就 new 一个 Node 放到这里, 此时为 null, 所以直接 new Node 放到 3 上, 此时 table 如下:
然后判断当前已使用容量大小 (size) 是否已经超过临界值 threshold, 此时 size=1, 小于 12, 不做任何操作, put 方法结束(如果超过临界值, 需要 resize 扩容).
继续 put...
map.put("key1", "value1");
- map.put("key1", "value1");
- map.put("key2", "value2");
- map.put("key3", "value3");
- map.put("key4", "value4");
- map.put("key5", "value5");
- map.put("key6", "value6");
- map.put("key8", "value7");
- map.put("key9", "value9");
- map.put("key10", "value10");
- map.put("key11", "value11");
此时 size=12, 下一次 put 后 size 为 13, 大于当前 threshold, 将触发扩容(resize)
map.put("key12", "value12");
计算 Key 的 hash 值, hash("key12")=101945043, 计算要存入 table 位置的索引值 = (总大小 - 1) & hash = (16 - 1) & 101945043 = 3 从目前的 table 状态可知, table[3] != null, 但此时要 put 的 key 与 table[3].key 不相等, 我们必须要把他存进去, 此时就产生了哈希冲突(哈希碰撞).
这时链表就派上用场了, HashMap 就是通过链表解决哈希冲突的. HashMap 会创建一个新的 Node, 并放到 table[3]链表的最后面. 此时 table 状态如下:
5.resize 扩容
此时 table 中一共有 13 个元素, 已经超过了 threshold(12), 需要对 table 调用 resize 方法扩容. HashMap 会创建一个容量为之前两倍 (162=32) 的 table, 并将旧的 Node 复制到新的 table 中, 新的临界值 (threshold) 为 24(320.75).
下面主要介绍一下复制的过程(并不是原封不动的复制, Node 的位置可能发生变化)
先来看源码:
- for (int j = 0; j <oldCap; ++j) { // oldCap: 旧 table 的大小 =16
- Node<K,V> e;
- if ((e = oldTab[j]) != null) { // oldTab: 旧 table 的备份
- oldTab[j] = null;
- // 如果数组中的元素没有后继节点, 直接计算新的索引值, 并将 Node 放到新数组中
- if (e.next == null)
- newTab[e.hash & (newCap - 1)] = e;
- // 忽略这个 else if. 其实, 如果链表的长度超过 8,HashMap 会把这个链表变成一个树结构, 树结构中的元素是 TreeNode
- else if (e instanceof TreeNode)
- ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
- // 有后继节点的情况
- else { // preserve order
- Node<K,V> loHead = null, loTail = null;
- Node<K,V> hiHead = null, hiTail = null;
- Node<K,V> next;
- do {
- next = e.next;
- // [说明 1]
- if ((e.hash & oldCap) == 0) {
- if (loTail == null)
- loHead = e;
- else
- loTail.next = e;
- loTail = e;
- }
- else {
- if (hiTail == null)
- hiHead = e;
- else
- hiTail.next = e;
- hiTail = e;
- }
- } while ((e = next) != null);
- if (loTail != null) {
- loTail.next = null;
- newTab[j] = loHead;
- }
- if (hiTail != null) {
- hiTail.next = null;
- //[说明 2]
- newTab[j + oldCap] = hiHead;
- }
- }
- }
- }
[说明 1] 遍历链表, 计算链表每一个节点在新 table 中的位置.
计算位置的方式如下:
1)如果节点的 (hash & oldCap) == 0, 那么该节点还在原来的位置上, 为什么呢?
因为 oldCap=16, 二进制的表现形式为 0001 0000, 任何数 & 16, 如果等于 0, 那么这个数的第五个二进制位必然为 0.
以当前状态来说, 新的容量是 32, 那么 table 的最大 index 是 31,31 的二进制表现形式是 00011111. 计算 index 的方式是 hash & (容量 - 1), 也就是说, 新 index 的计算方式为 hash & (32 - 1) 假设 Node 的 hash = 01101011, 那么
- 01101011
- & 00011111
- ----------
- 00001011 = 11
2)下面再对比(hash & oldCap) != 0 的情况
如果节点的(hash & oldCap) != 0, 那么该节点的位置 = 旧 index + 旧容量大小
假设 Node 的 hash = 01111011, 那么
- 01111011
- & 00011111
- ----------
- 00011011 = 27
上一个例子的 hash 值 01101011 跟这个例子的 hash 值 01111011 只是在第 5 位二进制上不同, 可以发现, 这两个值在旧的 table 中, 是在同一个 index 中的, 如下:
- 01101011
- & 00001111
- ----------
- 00001011 = 11
- 01111011
- & 00001111
- ----------
- 00001011 = 11
由于扩容总是以 2 倍的方式进行, 也就是: 旧容量 << 1, 这也就解释了[说明 2] , 当(hash & oldCap) != 0 时, 这个 Node 的新 index = 旧 index + 旧容量大小.
扩容后, table 状态如下所示:
最终, 重新分配完所有的 Node 后, 扩容结束.
来源: https://juejin.im/post/5c41d0f8f265da615115033d