本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 发问。
前言
大家好，我是小彭。
在上一篇文章里，咱们聊到了散列表的整体设计思维，在后续几篇文章里，咱们将以 Java 语言为例，剖析规范库中实现的散列表实现，包含 HashMap、ThreadLocalMap、LinkedHashMap 和 ConcurrentHashMap。
明天，咱们来探讨 Java 规范库中十分典型的散列表构造，也是“面试八股文”的规范题库之一 —— HashMap。
本文源码基于 Java 8 HashMap，并关联剖析局部 Java 7 HashMap。
小彭的 Android 交换群 02 群曾经建设啦，扫描文末二维码进入~
思维导图：
1. 回顾散列表工作原理
在剖析 HashMap 的实现原理之前，咱们先来回顾散列表的工作原理。
散列表是基于散列思维实现的 Map 数据结构，将散列思维利用到散列表数据结构时，就是通过 hash 函数提取键（Key）的特征值（散列值），再将键值对映射到固定的数组下标中，利用数组反对随机拜访的个性，实现 O(1) 工夫的存储和查问操作。
散列表示意图
在从键值对映射到数组下标的过程中，散列表会存在 2 次散列抵触：
- 第 1 次 – hash 函数的散列抵触： 这是个别意义上的散列抵触；
- 第 2 次 – 散列值取余转数组下标： 实质上，将散列值转数组下标也是一次 Hash 算法，也会存在散列抵触。同时，这也阐明 HashMap 中同一个桶中节点的散列值不肯定是雷同的。
事实上，因为散列表是压缩映射，所以咱们无奈防止散列抵触，只能保障散列表不会因为散列抵触而失去正确性。罕用的散列抵触解决办法有 2 类：
- 凋谢寻址法： 例如 ThreadLocalMap；
- 拆散链表法： 例如明天要剖析的 HashMap 散列表。
拆散链表法（Separate Chaining）的核心思想是： 在呈现散列抵触时，将抵触的元素增加到同一个桶（Bucket / Slot）中，桶中的元素会组成一个链表，或者跳表、红黑树等动静数据结构。相比于凋谢寻址法，链表法是更罕用且更稳固的抵触解决办法。
拆散链表法示意图
影响散列表性能的关键在于“散列抵触的产生概率”，抵触概率越低，工夫复杂度越靠近于 O(1)。那么，哪些因素会影响抵触概率呢？次要有 3 个：
- 因素 1 – 装载因子： 装载因子 (Load Factor) = 散列表中键值对数目 / 散列表的长度。随着散列表中元素越来越多，闲暇地位越来越少，就会导致散列抵触的产生概率越来越大，使得散列表操作的均匀工夫会越来越大；
- 因素 2 – 采纳的抵触解决办法： 凋谢寻址法的抵触概率人造比拆散链表法高，适宜于小数据量且装载因子较小的场景；拆散链表法对装载因子的容忍度更高，适宜于大数据量且大对象（绝对于一个指针）的场景；
- 因素 3 – 散列函数设计： 散列算法随机性和高效性也会影响散列表的性能。如果散列值不够随机，即便散列表整体的装载因子不高，也会使得数据汇集在某一个区域或桶内，仍然会影响散列表的性能。
2. 意识 HashMap 散列表
2.1 说一下 HashMap 的底层构造？
HashMap 是基于拆散链表法解决散列抵触的动静散列表：
- 在 Java 7 中应用的是“数组 + 链表”，产生散列抵触的键值对会用头插法增加到单链表中；
- 在 Java 8 中应用的是“数组 + 链表 + 红黑树”，产生散列抵触的键值对会用尾插法增加到单链表中。如果链表的长度大于 8 时且散列表容量大于 64，会将链表树化为红黑树。在扩容再散列时，如果红黑树的长度低于 6 则会还原为链表；
- HashMap 的数组长度保障是 2 的整数幂，默认的数组容量是 16，默认装载因子下限是 0.75，扩容阈值是 12（16*0.75）；
- 在创立 HashMap 对象时，并不会创立底层数组，这是一种懒初始化机制，直到第一次 put 操作才会通过 resize() 扩容操作初始化数组;
- HashMap 的 Key 和 Value 都反对 null，Key 为 null 的键值对会映射到数组下标为 0 的桶中。
2.2 为什么 HashMap 采纳拉链法而不是凋谢地址法？
我认为 Java 给予 HashMap 的定位是一个绝对“通用”的散列表容器，它应该在面对各种输出场景中都体现稳固。
凋谢地址法的散列抵触产生概率人造比拆散链表法更高，所以基于凋谢地址法的散列表不能把装载因子的下限设置得很高。在存储雷同的数据量时，凋谢地址法须要事后申请更大的数组空间，内存利用率也不会高。因而，凋谢地址法只适宜小数据量且装载因子较小的场景。
而拆散链表法对于装载因子的容忍度更高，可能适宜大数据量且更高的装载因子下限，内存利用率更高。尽管链表节点会多耗费一个指针内存，但在个别的业务场景中能够忽略不计。
咱们能够举个反例，在 Java 原生的数据结构中，也存在应用凋谢地址法的散列表 —— 就是 ThreadlLocal。因为我的项目中不会大量应用 ThreadLocal 线程部分存储，所以它是一个小规模数据场景，这里应用凋谢地址法是没问题的。
2.3 为什么 HashMap 在 Java 8 要引入红黑树呢？
因为当散列抵触加剧的时候，在链表中寻找对应元素的工夫复杂度是 O(K)，K 是链表长度。在极其状况下，当所有数据都映射到雷同链表时，工夫复杂度会“进化”到 O(n)。
而应用红黑树（近似均衡的二叉搜寻树）的话，树形构造的工夫复杂度与树的高度无关，查找复杂度是 O(lgK)，最坏状况下工夫复杂度是 O(lgn)，工夫复杂度更低。
2.4 为什么 HashMap 应用红黑树而不是均衡二叉树？
这是在查问性能和保护老本上的衡量，红黑树和均衡二叉树的区别在于它们的均衡水平的强弱不同：
均衡二叉树谋求的是一种 “齐全均衡” 状态：任何结点的左右子树的高度差不会超过 1。劣势是树的结点是很平均分配的；
红黑树不谋求这种齐全均衡状态，而是谋求一种 “弱均衡” 状态：整个树最长门路不会超过最短门路的 2 倍。劣势是尽管就义了一部分查找的性能效率，然而可能换取一部分维持树均衡状态的老本。
2.5 为什么常常应用 String 作为 HashMap 的 Key？
- 1、不可变类 String 能够防止批改后无奈定位键值对： 假如 String 是可变类，当咱们在 HashMap 中构建起一个以 String 为 Key 的键值对时，此时对 String 进行批改，那么通过批改后的 String 是无奈匹配到方才构建过的键值对的，因为批改后的 hashCode 可能会变动，而不可变类能够躲避这个问题；
- 2、String 可能满足 Java 对于 hashCode() 和 equals() 的通用约定： 既两个对象 equals() 雷同，则 hashCode() 雷同，如果 hashCode() 雷同，则 equals() 不肯定雷同。这个约定是为了防止两个 equals() 雷同的 Key 在 HashMap 中存储两个独立的键值对，引起矛盾。
2.6 HashMap 的多线程程序中会呈现什么问题？
- 数据笼罩问题：如果两个线程并发执行 put 操作，并且两个数据的 hash 值抵触，就可能呈现数据笼罩（线程 A 判断 hash 值地位为 null，还未写入数据时挂起，此时线程 B 失常插入数据。接着线程 A 取得工夫片，因为线程 A 不会从新判断该地位是否为空，就会把方才线程 B 写入的数据笼罩掉）。事实上，这个未同步数据在任意多线程环境中都会存在这个问题；
- 环形链表问题： 在 HashMap 触发扩容时，并且正好两个线程同时在操作同一个链表时，就可能引起指针凌乱，造成环型链条（因为 Java 7 版本采纳头插法，在扩容时会翻转链表的程序，而 Java 8 采纳尾插法，再扩容时会放弃链表本来的程序）。
2.7 HashMap 如何实现线程平安？
有 3 种形式：
- 形式 1 – 应用 hashTable 容器类（过期）： hashTable 是线程平安版本的散列表，它会在所有办法上减少 synchronized 关键字，且不反对 null 作为 Key。
- 办法 2 – 应用 Collections.synchronizedMap 包装类： 原理也是在所有办法上减少 synchronized 关键字；
- 办法 3 – 应用 ConcurrentHashMap 容器类： 基于 CAS 无锁 + 分段实现的线程平安散列表；
3. HashMap 的属性
在剖析 HashMap 的执行流程之前，咱们先用一个表格整顿 HashMap 的属性：
| 版本 | 数据结构 | 节点实现类 | 属性 |
|---|---|---|---|
| Java 7 | 数组 + 链表 | Entry（单链表） | 1、table（数组） 2、size（尺寸） 3、threshold（扩容阈值） 4、loadFactor（装载因子下限） 5、modCount（批改计数） 6、默认数组容量 16 7、最大数组容量 2^30 8、默认负载因子 0.75 |
| Java 8 | 数组 + 链表 + 红黑树 | 1、Node（单链表） 2、TreeNode（红黑树） |
9、桶的树化阈值 8 10、桶的还原阈值 6 11、最小树化容量阈值 64 |
HashMap.java
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
// 默认数组容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 疑难 3：为什么最大容量是 2^30 次幂？// 疑难 4：为什么 HashMap 要求数组的容量是 2 的整数幂？// 数组最大容量：2^30（高位 0100，低位都是 0）static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子：0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 疑难 5：为什么要设置桶的树化阈值，而不是间接应用数组 + 红黑树？//（Java 8 新增）桶的树化阈值：8
static final int TREEIFY_THRESHOLD = 8;
//（Java 8 新增）桶的还原阈值：6（在扩容时，当原有的红黑树内数量 <= 6 时，则将红黑树还原成链表）static final int UNTREEIFY_THRESHOLD = 6;
// 疑难 6：为什么要在设置桶的树化阈值后，还要设置树化的最小容量？//（Java 8 新增）树化的最小容量：64（只有整个散列表的长度满足最小容量要求时才容许链表树化，否则会间接扩容，而不是树化）static final int MIN_TREEIFY_CAPACITY = 64;
// 底层数组（每个元素是一个单链表或红黑树）transient Node<K,V>[] table;
// entrySet() 返回值缓存
transient Set<Map.Entry<K,V>> entrySet;
// 无效键值对数量
transient int size;
// 扩容阈值（容量 * 装载因子）int threshold;
// 装载因子下限
final float loadFactor;
// 批改计数
transient int modCount;
// 链表节点（一个 Node 等于一个键值对）static class Node<K,V> implements Map.Entry<K,V> {
// 哈希值（雷同链表上 Key 的哈希值可能雷同）final int hash;
// Key（一个散列表上 Key 的 equals() 肯定不同）final K key;
// Value（Value 不影响节点地位）V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
// Node 的 hashCode 取 Key 和 Value 的 hashCode
public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);
}
// 两个 Node 的 Key 和 Value 都相等，才认为相等
public final boolean equals(Object o) {if (o == this)
return true;
if (o instanceof Map.Entry) {Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
//（Java 8 新增）红黑树节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
// 父节点
TreeNode<K,V> parent;
// 左子节点
TreeNode<K,V> left;
// 右子节点
TreeNode<K,V> right;
// 删除辅助节点
TreeNode<K,V> prev;
// 色彩
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {super(hash, key, val, next);
}
// 返回树的根节点
final TreeNode<K,V> root() {for (TreeNode<K,V> r = this, p;;) {if ((p = r.parent) == null)
return r;
r = p;
}
}
}
}LinkedHashMap.java
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {super(hash, key, value, next);
}
}相比于线性表，HashMap 的属性可算是上难度了，HashMap 真卷。不出意外的话又有小朋友进去举手发问了🙋🏻♀️：
- 🙋🏻♀️疑难 1： 为什么字段不申明
private关键字？（答复过多少次了，把手给我放下） - 🙋🏻♀️疑难 2： 为什么字段申明
transient关键字？（答复过多少次了，把手给我放下） - 🙋🏻♀️疑难 3：为什么最大容量是 2^30？
因为 HashMap 要求散列表的数组容量是 2 的整数幂，而 int 类型可能示意的最大 2 的整数幂就是 2^30，即高位第 31 位是 1，低位都是 0。
- 🙋🏻♀️疑难 4：为什么 HashMap 要求数组的容量是 2 的整数幂？
这个问题咱们上面再答复。
- 🙋🏻♀️疑难 5：为什么要设置桶的树化阈值，而不是间接应用数组 + 红黑树？
其实，红黑树是“兜底”策略，而不肯定是最优策略。
首先，红黑树节点自身的内存耗费是链表节点的 2 倍。其次，红黑树在增加和删除数据时须要保护红黑树的性质，会减少旋转等操作。所以，当桶的节点数很低时，并不能体现出红黑树的劣势（相似于 Arrays.sort 在子数组长度小于 47 时用插入排序而不是疾速排序）。
再联合散列剖析的数据统计，在装载因子下限为 0.75 且均匀负载因子为 0.5 HashMap 中，桶长度的呈现频率合乎泊松散布，大部分的桶散布在 0 ~ 3 的长度上，长度大于 8 的桶的呈现频率低于千万分之一。
综上所述，为了防止在小桶中应用红黑树，HashMap 在桶的长度大于等于 8 时才会树化为红黑树。并且在扩容再散列时，如果桶的长度小于等于 6，也会还原为链表。
散列抵触数据统计
# 装载因子下限为 0.75、均匀负载因子为 0.5，且散列函数随机性良好时，不同长度桶的呈现频率
0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
more: less than 1 in ten million # 低于千万分之一- 🙋🏻♀️疑难 6：为什么要在设置桶的树化阈值后，还要设置树化的最小容量？
这是为了防止有效的树化。
在散列表的容量较低时，增加数据时很容易会触发扩容。此时，一部分本来曾经树化的桶会因为长度降落而退还回链表。因而，红黑树为树化操作设置了最小容量要求：如果链表长度达到树化阈值，但散列表整体的长度未达到最小容量要求，那么就间接扩容，而不是在桶上树化。
3. HashMap 源码剖析
3.1 HashMap 的构造方法
HashMap 有 4 个构造方法：
- 1、带初始容量和装载因子的构造方法： 查看初始容量和 装载因子的有效性，并计算初始容量最近的 2 的整数幂；
- 2、带初始容量的构造方法： 应用默认负载因子 0.75 调用上一个构造方法；
- 3、无参构造方法： 设置默认 装载因子 0.75；
- 4、带 Map 参数的构造方法： 设置默认 装载因子 0.75，并一一增加 Map 中的映射关系。
能够看到，在 HashMap 的构造方法中并没有创立底层数组，而是提早到 put 操作中触发的 resize 扩容操作中创立数组。另外，在能够已知存储的数据量时，能够在结构器中事后设置初始容量，防止在增加数据的过程中屡次触发扩容。
// 带初始容量和装载因子的构造方法
public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity:" + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
// 最大容量限度
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor:" + loadFactor);
// 装载因子下限
this.loadFactor = loadFactor;
// 扩容阈值（此处不是真正的阈值，仅仅只是将传入的容量转化最近的 2 的整数幂，该阈值前面会从新计算）this.threshold = tableSizeFor(initialCapacity);
}
// 带初始容量的构造方法
public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR /*0.75*/);
}
// 无参构造方法
public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR /*0.75*/;}
// 带 Map 的构造方法
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR /*0.75*/;
// 疑难 7：为什么不应用 Arrays 工具类整体复制，而是应用 putMapEntries 批量增加？// 批量增加
putMapEntries(m, false);
}
// 疑难 8：tableSizeFor() 的函数体解释一下？// 获取最近的 2 的整数幂
static final int tableSizeFor(int cap) {
// 先减 1，让 8、16 这种自身就是 2 的整数幂的容量放弃不变
// 在 ArrayDeque 中没有先减 1，所以容量 8 会转为 16
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 /*tableSizeFor() 办法外层曾经查看过超过 2^30 的值，应该不存在整型溢出的状况 */
: (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}小朋友总是有太多问号，举手发问🙋🏻♀️：
🙋🏻♀️疑难 7：为什么带汇合的构造方法不应用 Arrays 工具类整体复制，而是应用 putMapEntries 批量增加？
首先，参数 Map 不肯定是基于散列表的 Map，所以不能整体复制。其次，就算参数 Map 也是 HashMap，如果两个散列表的 length 长度不同，键值对映射到的数组下标也会不同。因而不能用 Arrays 工具类整体复制，必须一一再散列到新的散列表中。
🙋🏻♀️疑难 8：tableSizeFor() 的函数体解释一下？
其实，HashMap#tableSizeFor() 函数体与 ArrayDeque#calculateSize() 函数体类似，也是求最近的 2 的整数幂，即 nextPow2 问题。区别在于 HashMap 在第一步对参数 cap – 1，而 ArrayDeque 没有这一步，会将 8、16 这种自身就是 2 的整数幂的容量翻倍。
tableSizeFor() 中通过五轮无符号右移和或运算，将 cap 转换为从最高位开始前面都是 1 的数。再执行 +1 运算，就求出了最近的 2 的整数幂（最高无效位是 1，低位都是 0）。
n = 0 0 0 0 1 x x x x x //n
n = 0 0 0 0 1 1 x x x x //n |= n >>> 1;
n = 0 0 0 0 1 1 1 1 x x //n |= n >>> 2;
n = 0 0 0 0 1 1 1 1 1 1 //n |= n >>> 4;
n = 0 0 0 0 1 1 1 1 1 1 //n |= n >>> 8;（这一步对 n 没有影响了）n = 0 0 0 0 1 1 1 1 1 1 //n |= n >>> 16;（这一步对 n 没有影响了）n = 0 0 0 1 0 0 0 0 0 0 //n + 1（进位，失去最近 2 的整数幂）3.2 HashMap 的哈希函数
将 HashMap#put 办法中，有一个重要的步骤就是应用 Hash 函数计算键值对中键（Key）的散列值。HashMap#put 的执行流程非常复杂，为了升高了解难度，咱们先剖析 HashMap#hash 办法。
Hash 函数是散列表的外围个性，Hash 函数是否足够随机，会间接影响散列表的查问性能。在 Java 7 和 Java 8 中，HashMap 会在 Object#hashCode() 的根底上减少 “扰动”：
- Java 7： 做 4 次扰动，通过无符号右移，让散列值的高位与低位做异或；
- Java 8： 做 1 次扰动，通过无符号右移，让高 16 位与低 16 位做异或。在 Java 8 只做一次扰动，是为了在随机性和计算效率之间的衡量。
HashMap#hash
public V put(K key, V value) {return putVal(hash(key) /* 计算散列值 */, key, value, false, true);
}
// Java 7：4 次位运算 + 5 次异或运算
static final int hash(int h) {h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
// 疑难 9：为什么 HashMap 要在 Object#hashCode() 上减少扰动，而不是要求 Object#hashCode() 尽可能随机？// 为什么让高位与低位做异或就能够进步随机性？// Java 8：1 次位运算 + 1 次异或运算
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}小朋友总是有太多问号，举手发问🙋🏻♀️：
- 🙋🏻♀️疑难 9：为什么 HashMap 要在 Object#hashCode() 上减少扰动，而不是要求 Object#hashCode() 尽可能随机？
这是兜上限，以保障所有应用 HashMap 的开发者都能取得良好的性能。而且，因为数组的长度无限，在将散列值映射到数组下标时，会应用数组的长度做取余运算，最终影响下标地位的只有散列值的低几位元素，会毁坏映射的随机性（即散列值随机，但映射到下标后不随机）。
因而，HashMap 会对散列值做位移和异或运算，让高 16 位与低 16 位做异或运算。等于说在低位中退出了高位的个性，让高位的数值也会影响到数组下标的计算。
到这里，根本能够答复上一节剩下的疑难 4：
- 🙋🏻♀️疑难 4：为什么 HashMap 要求数组的容量是 2 的整数幂？
这是为了进步散列值映射到数组下标的计算效率和随机性，起因有 3 个：
1、进步取余操作的计算效率：
如果数组的容量是 2 的整数幂，那么就能够将取余运算 |hash % length| 替换为位运算 hash & (length - 1)，不论被除数是正负后果都是负数。不仅将取余运算替换为位运算，而且缩小了一次取绝对值运算，进步了索引的计算效率。
10 % 4 = 2
-10 % 4 = -2 // 正数
10 & (4 - 1) = 2
-10 & (4 - 1) = 2 // 负数2、数组长度是偶数能防止散列值都映射到偶数下标上：
如果数组的长度是奇数，那么 (length – 1) 的后果肯定是偶数，即二进制最低 1 位是 0。这就会导致 hash & (length – 1) 的后果肯定是偶数，即始终会映射到偶数下标中，不仅节约了个别数组空间，也会增大抵触概率。
3、保留所有的低位特色：
数组长度 length 为 2 的整数幂对应 (length – 1) 正好是高位为 0，低位都是 1 的低位掩码，可能让影响映射的因素全副归结到散列值上。
3.3 HashMap 的增加办法
HashMap 间接增加一个键值对，也反对批量增加键值对：
- put： 一一增加或更新键值对
- putAll： 批量增加或更新键值对
不论是一一增加还是批量增加，最终都会先通过 hash 函数计算键（Key）的散列值，再通过 putVal 增加或更新键值对。
putValue 的流程非常复杂，我将次要步骤概括为 5 步：
- 1、如果数组为空，则应用扩容函数创立（阐明数组的创立机会在首次 put 操作时）；
- 2、(n – 1) & hash：散列值转数组下标，与 Java 7 的 indexFor() 办法类似；
- 3、如果是桶中的第一个节点，则创立并插入 Node 节点；
- 4、如果不是桶中的第一个节点（即产生哈希抵触），须要插入链表或红黑树。在增加到链表的过程中，遍历链表找到 Key 相等（equals）的节点，如果不存在则应用尾插法增加新节点。如果链表节点数超过树化阈值
8，则将链表转为红黑树。 - 5、如果键值对数量大于扩容阈值，则触发扩容。
HashMap#put
// 增加或更新键值对
public V put(K key, V value) {return putVal(hash(key) /* 计算散列值 */, key, value, false, true);
}
// 批量增加或更新键值对
public void putAll(Map<? extends K, ? extends V> m) {putMapEntries(m, true);
}
// 批量增加或更新键值对
// evict：是否驱赶最早的节点（在 LinkedHashMap 中应用，咱们先疏忽）final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {int s = m.size();
if (s > 0) {if (table == null) {
// 如果数组为空，则先初始化 threshold 扩容阈值
float ft = ((float)s / loadFactor) + 1.0F;
// 扩容阈值下限
int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
} else if (s > threshold)
// 参数 Map 的长度大于扩容阈值，先扩容（如果扩容后仍然有余，在上面的 putVal 中会再次扩容）// 这里应该有优化空间，批量增加时能够间接扩容到满足要求的容量，防止在 for 循环中屡次扩容
resize();
// 一一增加 Map 中的键值对
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {K key = e.getKey();
V value = e.getValue();
// hash(key)：计算 Key 的哈希值
// pubVal：增加或更新键值对
putVal(hash(key), key, value, false, evict);
}
}
}
// 最终都会走到 putVal 办法：// hash：Key 的散列值（通过扰动）// onlyIfAbsent：如果为 true，不会笼罩旧值
// evict：是否驱赶最早的节点（在 LinkedHashMap 中应用，咱们先疏忽）final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
// 数组
Node<K,V>[] tab;
// 指标桶（同一个桶中节点的散列值有可能不同）Node<K,V> p;
// 数组长度
int n;
// 桶的地位
int i;
// 1. 如果数组为空，则应用扩容函数创立（阐明数组的创立机会在首次 put 操作时）if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2. (n - 1) & hash：散列值转数组下标，与 Java 7 的 indexFor() 办法类似
if ((p = tab[i = (n - 1) & hash]) == null)
// 3. 如果是桶中的第一个节点，则创立并插入 Node 节点
tab[i] = newNode(hash, key, value, null);
else {
// 4. 如果不是桶中的第一个节点（即产生哈希抵触），须要插入链表或红黑树
// e：最终匹配的节点
Node<K,V> e;
// 节点上的 Key
K k;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
// 4.1 如果桶的根节点与 Key 相等，则将匹配到根节点
// p.hash == hash：快捷比拟（同一个桶中节点的散列值有可能不同，如果散列值不同，键不可能雷同）// (k = p.key) == key：快捷比拟（同一个对象）// key != null && key.equals(k)：判断两个对象 equals 雷同
e = p;
else if (p instanceof TreeNode)
// 4.2 如果桶是红黑树结构，则采纳红黑树的插入方式
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 4.3 如果桶是链表构造，则采纳链表的插入方式：// 4.3.1 遍历链表找到 Key 相等的节点
// 4.3.2 否则应用尾插法增加新节点
// 4.3.3 链表节点数超过树化阈值，则将链表转为红黑树
for (int binCount = 0; ; ++binCount) {
// 尾插法（Java 7 应用头插法）if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 链表节点数超过树化阈值，则将链表转为红黑树
treeifyBin(tab, hash);
break;
}
// 找到 Key 相等的节点
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 4.4 新 Value 替换旧 Value（新增节点时不会走到这个分支）if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 拜访节点回（用于 LinkedHashMap，默认为空实现）afterNodeAccess(e);
return oldValue;
}
}
// 批改记录
++modCount;
// 5. 如果键值对数量大于扩容阈值，则触发扩容
if (++size > threshold)
resize();
// 新增节点回调（用于 LinkedHashMap，默认为空实现）afterNodeInsertion(evict);
return null;
}
// -> 4.2 如果桶是红黑树结构，则采纳红黑树的插入方式
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {...}
// -> 链表节点数超过树化阈值，则将链表转为红黑树
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}小朋友总是有太多问号，举手发问🙋🏻♀️：
- 🙋🏻♀️疑难 10：为什么 Java 8 要将头插法改为尾插法？
HashMap 不思考多线程同步，会存在多线程平安问题。当多个线程同时执行 put 操作并且触发扩容时，Java 7 的头插法会翻转链表的程序，有可能会引起指针凌乱造成环形链表，而 Java 8 应用尾插法，在扩容时会放弃链表本来的程序。
- 🙋🏻♀️疑难 11：解释一下 p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))？
这个问题等价于问 HashMap 如何确定键值对的地位：
1、首先，HashMap 会对键 Key 计算 hashCode() 并增加扰动，失去扰动后的散列值 hash。随后通过对数组长度取余映射到数组下标中；
2、而后，当数组下标的桶中存在多个节点时，HashMap 须要遍历桶找到与 Key 相等的节点，以辨别是更新还是增加。为了提高效率，就有了 if 语句中的屡次判断：
2.1 p.hash == hash 快捷判断：同一个桶中节点的散列值有可能不同，如果散列值不同，键肯定相等：
2.2 (k = p.key) == key 快捷判断：同一个对象；
2.3 key != null && key.equals(k) 最终判断：判断两个键 Key 是否相等，即 equals 相等。
综上所述，HashMap 是通过 hashCode() 定位桶，通过 equals() 确定键值对。
HashMap#put 执行流程
3.4 HashMap 的扩容办法
在 putVal 办法中，如果增加键值对后散列值的长度超过扩容阈值，就会调用 resize() 扩容，主体流程分为 3 步：
- 1、计算扩容后的新容量和新扩容阈值；
- 2、创立新数组；
- 3、将旧数组上的键值对再散列到新数组上。
扩容分为 2 种状况：
- 1、首次增加元素： 会依据构造方法中设置的初始容量和装载因子确定新数组的容量和扩容阈值在无参构造方法中，会应用 16 的数组容量和 0.75 的扩容阈值；
- 2、非首次增加： 将底层数组和扩容阈值扩充为原来的 2 倍，如果旧容量大于等于 2^30 次幂，则无奈扩容。此时，将扩容阈值调整到整数最大值。
再散列的步骤不好了解，这里解释下：
- 3.1 桶的根节点，间接再散列；
- 3.2 以红黑树的形式再散列，思路与 3.3 链表的形式类似；
- 3.3 以链表的模式再散列：hash & oldCap 就是获取 hash 在扩容后新参加映射的 1 个最高无效位。如果这一位是 0，那么映射后的地位还是在原来的桶中，如果这一位是 1，那么映射后的地位就是原始地位 + 旧数组的容量。
oldCap = 0 0 0 0 1 0 0 0 0 0 // 32
oldCap - 1 = 0 0 0 0 0 1 1 1 1 1 // 32
newCap = 0 0 0 1 0 0 0 0 0 0 // 64
newCap - 1 = 0 0 0 0 1 1 1 1 1 1 // 64
^
减少 1 个无效位参加映射HashMap#resize
// 扩容
final Node<K,V>[] resize() {
// 旧数组
Node<K,V>[] oldTab = table;
// 旧容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 旧扩容阈值
int oldThr = threshold;
// 新容量
int newCap = 0;
// 新扩容阈值
int newThr = 0;
// 1. 计算扩容后的新容量和新扩容阈值
// 旧容量大于 0，阐明不是第一次增加元素
if (oldCap > 0) {
// 如果旧容量大于等于 2^30 次幂，则无奈扩容。此时，将扩容阈值调整到整数最大值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 数组容量和扩容阈值扩充为原来的 2 倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 旧容量为 0，须要初始化数组
else if (oldThr > 0)
//（带初始容量和负载因子的构造方法走这里）// 应用构造方法中计算的最近 2 的整数幂作为数组容量
newCap = oldThr;
else {
//（无参构造方法走这里）// 应用默认 16 长度作为初始容量
newCap = DEFAULT_INITIAL_CAPACITY;
// 应用默认的负载因子乘以容量计算扩容阈值
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
//（带初始容量和负载因子的构造方法走这里）// 应用负载因子乘以容量计算扩容阈值
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
}
// 最终计算的扩容阈值
threshold = newThr;
// 2. 创立新数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 3. 将旧数组上的键值对再散列到新数组上
if (oldTab != null) {
// 遍历旧数组上的每个桶
for (int j = 0; j < oldCap; ++j) {
// 桶的根节点
Node<K,V> e;
// 桶的根节点不为 null
if ((e = oldTab[j]) != null) {oldTab[j] = null;
if (e.next == null)
// 3.1 桶的根节点，间接再散列
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 3.2 以红黑树的形式再散列，思路与 3.3 链表的形式类似
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
// 3.3 以链表的模式再散列
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 3.3.1 若散列值新参加映射的位为 0，那么映射到原始地位上
if ((e.hash & oldCap) == 0) {if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 3.3.2 若散列值新参加映射的位为 0，那么映射到原始地位 + 旧数组容量的地位上
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;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}3.5 HashMap 的获取办法
HashMap 的获取办法绝对简略，与 put 办法相似：先通过 hash 函数计算散列值，再通过 hash 取余映射到数组下标的桶中，最初遍历桶中的节点，找到与键（Key）相等（equals）的节点。
HashMap#get
// 获取 Key 映射的键值对
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key)/* 计算散列值 */, key)) == null ? null : e.value;
}
// 通过 Key 的散列值和 Key 获取映射的键值对
final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
// 先查看根节点
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 以红黑树的形式检索
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 以链表的形式检索
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}HashMap#get 示意图
3.6 HashMap 的移除办法
HashMap 的移除办法是增加办法的逆运算，HashMap 没有做动静缩容。
HashMap#remove
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key)/* 计算散列值 */, key, null, false, true)) == null ? null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
// 底层数组
Node<K,V>[] tab;
// 指标桶（同一个桶中节点的散列值有可能不同）Node<K,V> p;
int n, index;
// 定位到散列值对应的数组下标
if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
// 先查看根节点
node = p;
else if ((e = p.next) != null) {if (p instanceof TreeNode)
// 以红黑树的形式查问节点
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
// 以链表的形式查问节点
do {if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// node 不为 null，删除 node 节点
if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {if (node instanceof TreeNode)
// 以红黑树的形式删除
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
// 以链表的形式删除（删除跟节点）tab[index] = node.next;
else
// 以链表的形式删除（删除两头节点）p.next = node.next;
++modCount;
--size;
// 删除节点回调（用于 LinkedHashMap，默认为空实现）afterNodeRemoval(node);
return node;
}
}
return null;
}HashMap#remove 示意图
3.7 HashMap 的迭代器
Java 的 foreach 是语法糖，实质上也是采纳 iterator 的形式。HashMap 提供了 3 个迭代器：
- EntryIterator： 键值对迭代器
- KeyIterator： 键迭代器
- ValueIterator： 值迭代器
在迭代器遍历数组的过程中，有可能呈现多个线程并发批改数组的状况，Java 很多容器类的迭代器中都有 fail-fast 机制。如果在迭代的过程中发现 expectedModCount 变动，阐明数据被批改，此时就会提前抛出 ConcurrentModificationException 异样（当然也不肯定是被其余线程批改）。
其实，这 3 个迭代器都是 HashIterator 的子类，每个子类在 HashIterator#nextNode() 中获取不同的值：
final class KeyIterator extends HashIterator implements Iterator<K> {public final K next() {return nextNode().key; }
}
final class ValueIterator extends HashIterator implements Iterator<V> {public final V next() {return nextNode().value; }
}
final class EntryIterator extends HashIterator implements Iterator<Map.Entry<K,V>> {public final Map.Entry<K,V> next() {return nextNode(); }
}
// 非动态外部类
abstract class HashIterator {
Node<K,V> next; // next entry to return
Node<K,V> current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
HashIterator() {
// 记录外部类的批改计数
expectedModCount = modCount;
// 记录底层数组
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() {return next != null;}
final Node<K,V> nextNode() {Node<K,V>[] t;
Node<K,V> e = next;
// 查看批改记录
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
// TreeNode 也会用 next 指针串联
if ((next = (current = e).next) == null && (t = table) != null) {do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
...
}基于这 3 个迭代器，HashMap 的遍历形式就分为 3 种：
// 1. 间接遍历节点
Iterator<Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {Entry<String, Integer> next = iterator.next();
}
// 2. 遍历 Key，再通过 Key 查问 Value（性能最差，多一次查问）Iterator<String> keyIterator = map.keySet().iterator();
while (keyIterator.hasNext()) {String key = keyIterator.next();
}
// 3. 间接遍历 Value
Iterator<Integer> valueIterator = map.values().iterator();
while (valueIterator.hasNext()) {Integer value = valueIterator.next();
}
// foreach 是语法糖
for (Map.Entry<String, Integer> entry : map.entrySet()) {
}
// 编译后：Iterator var2 = map.entrySet().iterator();
while(var2.hasNext()) {Entry<String, Integer> entry = (Entry)var2.next();}3.8 HashMap 的序列化过程
HashMap 重写了 JDK 序列化的逻辑，只把 table 数组中无效元素的局部序列化，而不会序列化整个数组。
// 序列化过程
private void writeObject(java.io.ObjectOutputStream s) throws IOException {int buckets = capacity();
s.defaultWriteObject();
// 写入容量
s.writeInt(buckets);
// 写入无效元素个数
s.writeInt(size);
// 写入无效元素
internalWriteEntries(s);
}
// 不关怀键值对所在的桶，在反序列化会从新映射
void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {Node<K,V>[] tab;
if (size > 0 && (tab = table) != null) {for (int i = 0; i < tab.length; ++i) {for (Node<K,V> e = tab[i]; e != null; e = e.next) {s.writeObject(e.key);
s.writeObject(e.value);
}
}
}
}3.9 HashMap 的 clone() 过程
HashMap 中的 table 数组是援用类型，因而在 clone() 中须要实现深拷贝，否则原对象与克隆对象会相互影响：
public Object clone() {
HashMap<K,V> result;
try {result = (HashMap<K,V>)super.clone();} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
// 重置变量
result.reinitialize();
// 深拷贝
result.putMapEntries(this, false);
return result;
}4. 总结
明天，咱们剖析了 HashMap 的设计思路和外围源码，内容很多，播种也很多。其中，红黑树的局部咱们没有展开讨论，这部分咱们留到下一篇文章里探讨。请关注。
一道题目：
在网上看到一道题目，问题挺有迷惑性的：
- 筹备用 HashMap 存 1w 条数据，在结构时传 1w 容量，在增加时还会触发扩容吗？（答案是不会）
- 筹备用 HashMap 存 1k 条数据，在结构时传 1k 容量，在增加时还会触发扩容吗？（答案是会）
这是想考对 HashMap 容量和扩容阈值的了解了。在结构器中传递的 initialCapacity 并不一定是最终的容量，因为 HashMap 会应用 tableSizeFor() 办法计算一个最近的 2 的整数幂，而扩容阈值是在容量的根底上乘以默认的 0.75 装载因子下限。
因而，以上两种状况中，理论的容量和扩容阈值是：
- 1w： 10000 转最近的 2 的整数幂是 16384，再乘以装载因子下限得出扩容阈值为 12288，所以不会触发扩容；
- 1k： 1000 转最近的 2 的整数幂是 1024，再乘以装载因子下限得出扩容阈值为 768，所以会触发扩容；
参考资料
- 数据结构与算法剖析 · Java 语言形容（第 5 章 · 散列）—— [美] Mark Allen Weiss 著
- 算法导论（第 11 章 · 散列表）—— [美] Thomas H. Cormen 等 著
- 数据结构与算法之美（第 18~22 讲）—— 王争 著，极客工夫 出品
- Java：这是一份具体 & 全面的 HashMap 1.7 源码剖析 —— Carson 著
- Java 源码剖析：HashMap 1.8 绝对于 1.7 到底更新了什么？—— Carson 著
- 都说 HashMap 是线程不平安的，到底体现在哪儿？—— developer 著
- 漫画：高并发下的 HashMap —— 程序员小灰 著
- 面试官：筹备用 HashMap 存 1w 条数据，结构时传 10000 还会触发扩容吗？—— 承香墨影 著
- 散列算法 —— Wikipedia
- Poisson Distribution —— Wikipedia