「Java并发」 HashMap实现原理及源码分析（Java 1.8.0_101）
「Java并发」 HashMap实现原理及源码分析（Java 1.8.0_101）
阅读本文大概需要30分钟。
参考：揭秘 HashMap 实现原理（Java 8）- https://www.cnblogs.com/yangming1996/p/7997468.html 在其基础上做了修改和补充。
HashMap 作为一种容器类型，无论你是否了解过其内部的实现原理，它的大名已经频频出现在各种互联网面试中了。从基本的使用角度来说，它很简单，但从其内部的实现来看（尤其是 Java 8 的改进以来），它又并非想象中那么容易。如果你一定要问了解其内部实现与否对于写程序究竟有多大影响，我不能给出一个确切的答案。但是作为一名合格程序员，对于这种遍地都在谈论的技术不应该不为所动。本篇文章主要从 jdk 1.8 的版本初步探寻 HashMap 的基本实现情况，主要涉及内容如下：
- HashMap 的基本组成成员
- put 方法的具体实现
- remove 方法的具体实现
- 其他一些基本方法的基本介绍
一、HashMap 的基本组成成员
首先，HashMap 是 Map 的一个实现类，它代表的是一种键值对的数据存储形式。Key 不允许重复出现，Value 随意。jdk 8 之前，其内部是由数组+链表来实现的，而 jdk 8 对于链表长度超过 8 的链表将转储为红黑树。大致的数据存储形式如下：
下面分别对其中的基本成员属性进行说明：
// 默认的容量，即默认的数组长度 16
static final int DEFAULT_INITIAL_CAPACITY = << ;
// 最大的容量，即数组可定义的最大长度
static final int MAXIMUM_CAPACITY = << ;
这就是上述提到的数组，数组的元素都是 Node 类型，数组中的每个 Node 元素都是一个链表的头节点，通过它可以访问连接在其后面的所有节点。其实你也应该发现，上述的容量指的就是这个数组的长度。
transient Node<K,V>[] table;
// 实际存储的键值对个数
transient int size;
// 用于迭代防止结构性破坏的标量
transient int modCount;
下面这三个属性是相关的，threshold 代表的是一个阈值，通常小于数组的实际长度。伴随着元素不断的被添加进数组，一旦数组中的元素数量达到这个阈值，那么表明数组应该被扩容而不应该继续任由元素加入。而这个阈值的具体值则由负载因子（loadFactor）和数组容量来决定，公式：threshold = capacity * loadFactor。
int threshold;
final float loadFactor;
// HashMap 中默认负载因子为 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
好了，有关 HashMap 的基本属性大致介绍如上。下面我们看看它的几个重载的构造函数。
/**
*
* @param initialCapacity 初始容量
* @param loadFactor 负载因子
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < ) // 校验初始容量的合法性
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY) // 限制初始容量最大为MAXIMUM_CAPACITY
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= || Float.isNaN(loadFactor)) // 校验负载因子的合法性
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
这是一个最基本的构造函数，需要调用方传入两个参数，initialCapacity 和 loadFactor。程序的大部分代码在判断传入参数的合法性，initialCapacity 小于零将抛出异常，大于 MAXIMUM_CAPACITY 将被限定为 MAXIMUM_CAPACITY。loadFactor 如果小于等于零或者非数字类型也会抛出异常。
整个构造函数的核心在对 threshold 的初始化操作：
static final int tableSizeFor(int cap) {
int n = cap - ;
n |= n >>> ;
n |= n >>> ;
n |= n >>> ;
n |= n >>> ;
n |= n >>> ;
return (n < ) ? : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + ;
}
这是一个小巧但精妙的方法，这里通过位运算生成大于等于 cap 但最接近它的 2 的 N 次幂的一个数值。例如：
那么通过该方法，我们将获得一个 2 的N次幂的容量的值，此处存放至 threshold，实际上我们获取的是一个有关数组容量的值，不应该存放至阈值 threshold 中，但在后续实际初始化数组的时候并不会受到影响，这里可能是写 jdk 的大神偷了一次懒吧。
那么我们对于这个最基本的构造函数的介绍就已经结束了，当然，HashMap 中还有很多的重载构造函数，但几乎都是基于上述的构造函数的。例如：
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
最后需要说明一点的是，以上的一些构造函数都没有直接的创建一个切实存在的数组，他们都是在为创建数组需要的一些参数做初始化，所以有些在构造函数中并没有被初始化的属性都会在实际初始化数组的时候用默认值替换。
二、put 方法的具体实现
put 方法的源码分析是本篇的一个重点，因为通过该方法我们可以窥探到 HashMap 在内部是如何进行数据存储的，所谓的数组+链表+红黑树的存储结构是如何形成的，又是在何种情况下将链表转换成红黑树来优化性能的。带着一系列的疑问，我们看这个 put 方法：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
添加一个元素只需要传入一个键和一个值即可，putVal 方法是关键，我已经在该方法中进行了基本的注释，具体的细节稍后详细说明，先从这些注释中大体上建立一个直观的感受。
static final int TREEIFY_THRESHOLD = ;
static final int MAXIMUM_CAPACITY = << ;
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = << ; // aka 16
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// Create a regular (non-tree) node
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
// 如果 table 还未被初始化，那么初始化它
if ((tab = table) == null || (n = tab.length) == )
n = (tab = resize()).length;
// 根据键的 hash 值找到该键对应到数组中的bucket
// 如果为 null，那么说明此索引位置并没有被占用，创建一个新的Node保存到该索引位置
if ((p = tab[i = (n - ) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 不为 null，说明此处已经被占用，只需要将构建一个节点插入到这个链表的尾部即可
else {
Node<K,V> e;
K k;
// 当前节点和将要插入的节点的 hash 和 key 相同，说明这是一次修改操作
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果 p 这个头节点是红黑树节点的话，以红黑树的插入形式进行插入
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // TODO
// 遍历此条链表，将构建一个节点插入到该链表的尾部
else {
for (int binCount = ; ; ++binCount) {
if ((e = p.next) == null) { // 已遍历到了链表的尾部
p.next = newNode(hash, key, value, null); // 在尾部插入新的节点
// default, binCount >= 7
// 如果插入前链表长度大于等于 8 ，将链表裂变成红黑树
if (binCount >= TREEIFY_THRESHOLD - ) // -1 for 1st
treeifyBin(tab, hash); // TODO
break;
}
// 遍历的过程中，如果发现与某个节点的 hash 和 key 相同，这依然是一次修改操作
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 继续遍历
p = e;
}
}
// e 不是 null，说明当前的 put 操作是一次修改操作并且e指向的就是需要被修改的节点
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 如果添加后，数组容量达到阈值，进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
从整体上来看，该方法的大致处理逻辑已如上述注释说明，下面我们针对其中的细节进行详细的解释。
首先，我们看 resize 这个方法是如何对 table 进行初始化的：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; // 旧数组
int oldCap = (oldTab == null) ? : oldTab.length; // 旧数组长度，即容量
int oldThr = threshold; // 旧数组的阈值
int newCap, newThr = ;
// 说明旧数组已经被初始化完成了，此处需要给旧数组扩容
if (oldCap > ) {
// 达到容量限定的极限将不再扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 未达到极限，将数组容量扩大两倍，阈值也扩大两倍。
//
// 此外，如果数组容量扩容后大于极限，此时阈值不再有意义，没必要再扩大两倍，
// 这时newThr为0，后面的逻辑会将其赋值为Integer.MAX_VALUE，标记不再触发扩容。
else if ((newCap = oldCap << ) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << ; // double threshold
}
// 数组未初始化，但阈值不为 0，说明使用构造函数 HashMap(int initialCapacity, float loadFactor) 初始化的。
//
// 为什么不为0呢？
// 上述提到 jdk 大神偷懒的事情就指的这，构造函数根据传入的容量计算出了一个合适的数组容量暂存在阈值中，这里直接拿来使用
//
// 但是此时，newThr为0
else if (oldThr > ) // initial capacity was placed in threshold
newCap = oldThr;
// 数组未初始化并且阈值也为0，说明使用无参构造函数 HashMap() 初始化的，一切都以默认值进行构造
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY; // 16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 16 * 0.75
}
// 上面有两处提到newThr为0，这里对其进行赋值
if (newThr == ) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; // 设置新的阈值threshold
// 这一部分代码结束后，无论是初始化数组还是扩容，总之，必需的数组容量和阈值都已经计算完成了。下面看后续的代码：
// 根据新的容量初始化一个数组
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab; // 设置新的数组table
// 旧数组不为 null，这次的 resize 是一次扩容行为
if (oldTab != null) {
for (int j = ; j < oldCap; ++j) {
Node<K,V> e;
// 获取旧数组中索引为j的bucket链表的头节点
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 说明链表只有一个头节点，转移至新表
if (e.next == null)
newTab[e.hash & (newCap - )] = e;
// 如果 e 是红黑树结点，红黑树分裂，转移至新表
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // TODO
// 这部分是将链表中的各个节点原序地转移至新表中，具体为什么会这么做，我们后续会详细说明
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;
// 判断扩容后节点的索引是否会发生变化，
// 不变的节点组成一条新链；
// 改变的节点也组成一条新链；
if ((e.hash & oldCap) == ) { // 等于0，节点的索引不变
if (loTail == null) // loTail 为 null，则初始化链表 loTail = loHead = e
loHead = e;
else
loTail.next = e;
loTail = e;
}
else { // 不等于0，节点的索引改变
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;
}
}
}
}
}
// 不论你是扩容还是初始化，都可以返回 newTab
return newTab;
}
对于下半部分的代码段来说，主要完成的是将旧链表中的各个节点按照原序地复制到新数组中。关于头节点是红黑树的情况我们暂时不去涉及，下面重点介绍下链表的拷贝和优化代码块，这部分代码不再重复贴出，此处直接进行分析，有需要的可以参照上述列出的代码块或者自己的 jdk 进行理解。
这部分其实是一个优化操作，将当前链表上的一些节点移出来向刚扩容的另一半存储空间放。
一般我们有如下公式：
index = e.hash & (oldCap - )
CASE1：
e.hash = 01010010 01100100 10011000 01000101
oldCap = 10000
index = 01010010 01100100 10011000 01000101 & 1111 = 0101
newCap = 100000
newIndex = 01010010 01100100 10011000 01000101 & 11111 = 00101
随便举个例子，此时的 e 在容量扩大两倍以后的索引值没有变化，所以这部分节点是不需要移动的，那么程序如何判断扩容前后的 index 是否相等呢？
CASE2：
e.hash = 01010010 01100100 10011000 01010101
oldCap = 10000
index = 01010010 01100100 10011000 01010101 & 1111 = 0101
newCap = 100000
newIndex = 01010010 01100100 10011000 01010101 & 11111 = 10101
如果原 oldCap 为 10000 的话，那么扩容后的 newCap 则为 100000，会比原来多出一位。通过对比，会发现CASE1与CASE2的区别，CASE1扩容后的索引没变，而CASE2则变了。
所以对于任意节点，我们只要知道其原索引值在其hash的前一位是 0 还是 1 即可，如果是 0，那么重新运算后的索引还是 0 并不改变索引的值，如果是 1 的话，那么索引值会增加 oldCap。
我们可以通过如下公式判断节点的原索引值在其hash的前一位是 0 还是 1：
// oldCap 一定是 100...000 的形式
if ((e.hash & oldCap) == )
这样就分两步拆分当前链表，一条链表是不需要移动的，依然保存在当前索引值的节点上，另一条则需要变动到 index + oldCap 的索引位置上。
这里我们只介绍了普通链表的分裂情况，至于红黑树的裂变其实是类似的，依然分出一些节点到 index + oldCap 的索引位置上，只不过遍历的方式不同而已。
这样，我们对于 resize 这个扩容的方法已经解析完成了，下面接着看 putVal 方法，篇幅比较长，该方法的源码已经在介绍 resize 之前贴出，建议读者根据自己的 jdk 对照着理解。
上面我们说到，如果在 put 一个元素的时候判断内部的 table 数组还未初始化，那么调用 resize 根据相应的参数信息初始化数组。
接下来的这个判断语句就很简单了：
if ((p = tab[i = (n - ) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
根据键的 hash 值找到对应的索引位置，如果该位置为 null，说明还没有头节点，于是 newNode 并存储在该位置上。
否则的话说明该位置已经有头节点了，或者说已经存在一个链表或红黑树了，那么我们要做的只是新建一个节点添加到链表或者红黑树的最后位置即可。
第一步，
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
e = p;
p 指向当前节点，如果我们要插入的节点的键以及键所对应的 hash 值和 p 节点完全一样的话，那么说明这次 put 是一次修改操作，新建一个引用指向这个需要修改的节点。
第二步，
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
如果当前 p 节点是红黑树节点，那么需要调用不同于链表的添加节点的方法来添加一个节点到红黑树中。（主要是维持平衡，建议读者去了解下红黑树，此处没有深谈是限于它的复杂度和文章篇幅）。
第三步，
else {
for (int binCount = ; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - )
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
这里主要处理的是向普通链表的末尾添加一个新的节点，e 不断地往后移动，如果发现 e 为 null，那么说明已经到链表的末尾了，那么新建一个节点添加到链表的末尾即可，因为 p 是 e 的父节点，所以直接让 p.next 指向新节点即可。添加之后，如果发现链表长度超过 8，那么将链表转储成红黑树。
在遍历的过程中，如果发现 e 所指向的当前节点和我们即将插入的节点信息完全匹配，那么也说明这是一次修改操作，由于 e 已经指向了该需要被修改的结点，所以直接 break 即可。
那么最终，无论是第一步中找到的头节点即需要被修改的节点，还是第二、三步在遍历中找到的需要被修改的节点，它们的引用都是 e，此时我们只需要用传入的 Value 值替换 e 指向的节点的 value 即可。正如这段代码一样：
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
如果 e 为 null，那更简单了，说明此次 put 是添加新元素并且新元素也已经在上述代码中被添加到 HashMap 中了，我们只需要关心下，新加入一个元素后是否达到数组的阈值，如果是则调用 resize 方法扩大数组容量。该方法已经详细阐述过，此处不再赘述。
所以，这个 put 方法是集添加与修改一体的一个方法，如果执行的是添加操作则会返回 null，是修改操作则会返回旧结点的 value 值。
那么至此，我们对添加操作的内部实现想必已经了解的不错了，接下来看看删除操作的内部实现。
三、remove 方法的具体实现
删除操作就是一个查找+删除的过程，相对于添加操作其实容易一些，但那是你基于上述添加方法理解的不错的前提下。
public V remove(Object key) {
Node<K,V> e; // 根据key查找到的节点
// 节点存在，删除节点并返回节点的value
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
根据键值删除指定节点，这是一个最常见的操作了。显然，removeNode 方法是核心。
/**
* Implements Map.remove and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to match if matchValue, else ignored
* @param matchValue if true only remove if value is equal
* @param movable if false do not move other nodes while removing
* @return the node, or null if none
*/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; // table数组
Node<K,V> p;
int n, index; // n - 数组长度
if ((tab = table) != null // 数组不为null
&& (n = tab.length) > // 数组长度大于0
&& (p = tab[index = (n - ) & hash]) != null // 根据key定位到数组的 bucket 不为null，即该 bucket 存在节点
) {
Node<K,V> node = null, e; // node - 要删除的节点，e - 下一节点
K k;
V v;
// 当前节点和将要删除的节点的 hash 和 key 相同，说明当前节点即为要删除的节点
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) { // p 节点 next 不为 null，说明 bucket 为链表或者红黑树
// 如果 p 这个头节点是红黑树节点的话，以红黑树的查找形式进行查找
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; // 当前遍历的节点，如果查找到节点，则 p 为查找到的节点的上一节点
} while ((e = e.next) != null);
}
}
// 查找到要删除的节点，执行删除
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) // 当前 bucket 只有一个节点
tab[index] = node.next;
else // 当前 bucket 为链表，p 为查找到的节点的上一个节点
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
删除操作需要保证在表不为空的情况下进行，并且 p 节点根据键的 hash 值对应到数组的索引，在该索引处必定有节点，如果为 null ，那么间接说明此键所对应的节点并不存在于整个 HashMap 中，这是不合法的，所以首先要在这两个大前提下才能进行删除结点的操作。
第一步，
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
node = p;
需要删除的节点就是这个头节点，让 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);
}
}
如果头节点是红黑树节点，那么调用红黑树自己的遍历方法去得到这个待删结点。否则就是普通链表，我们使用 do while 循环去遍历找到待删结点。找到节点之后，接下来就是删除操作了。
第三步，
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;
afterNodeRemoval(node);
return node;
}
删除操作也很简单，如果是红黑树节点的删除，直接调用红黑树的删除方法进行删除即可，如果待删节点在该 bucket 就只有一个节点，那么用它的 next 节点（null）顶替它存放在 table[index] 中，如果删除的是普通链表中的一个节点，用该节点的前一个节点直接跳过该待删结点指向它的 next 结点即可。
最后，如果 removeNode 方法删除成功将返回被删节点的 value，否则返回 null。
这样，相对复杂的 put 和 remove 方法的内部实现，我们已经完成解析了。