引言
结合网上的各种资料，记录HashMap源码阅读的过程。
存储结构
HashMap(1.8)的存储结构为数组+链表+红黑树。
transient Node<K,V>[] table;
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
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;
}
.....
}
HashMap中一些关键的字段
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
int threshold;
final float loadFactor;
DEFAULT_INITIAL_CAPACITY表示Node[] table的初始化长度length(默认值是16)， loadFactor为负载因子(默认值是0.75)，threshold是扩容的阈值，是HashMap所能容纳的最大的Node(键值对)个数。threshold = DEFAULT_INITIAL_CAPACITY *loadFactor。TREEIFY_THRESHOLD为链表转换为红黑是的阈值，当链表的长度大于TREEIFY_THRESHOLD是转换为红黑树。UNTREEIFY_THRESHOLD为红黑是拆解为链表的阈值，当红黑树上的节点数量小于UNTREEIFY_THRESHOLD是，拆解为链表。
确定数组下标位置
HashMap确定数组下标的过程可分为三个步骤：取key对应的哈希值、高低16为异或运算、取模得到数组下标。下面重点来介绍一下后面两步运算的原理。下面先来介绍HashMap的取模运算。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
取模得到数组下标：HashMap的取模运算不是采用hash% table.length的形式，而是采用hash&(table.length-1)的形式，采用与运算可以更加高效的定位到数组下标的位置。如下图所示：
<img src="https://user-gold-cdn.xitu.io/2020/7/3/17313b7c2841c714?w=2322&h=500&f=png&s=39311" alt="低位与.png" title="低位与.png" />
高低16为异或运算：因为HashMap使用与运算定位数组代替取余运算来得到数组下标，虽然性能得到了提升，但这也产生了一个弊端，当数组的长度不大时，参与到定位下标运算的永远都是低位的二进制，高维二进制无法参与进来，因此采用高低16位异或的形式让高位也参与到定位数组下标的运算中去。
<img src="https://user-gold-cdn.xitu.io/2020/7/3/17313ba3a1a0c6d2?w=2363&h=932&f=png&s=69493" alt="高低16位异或.png" title="高低16位异或.png" />
扩容机制
当数组中Node节点的数量超过阈值threshold时需要调用resize()方法进行扩容。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 超过最大值就不再扩充了。
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
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
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;
@SuppressWarnings({"rawtypes","unchecked"})
// 创建新的Node数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 如果只有一个Node元素，则直接添加到新数组中。
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果是红黑树的树节点，则拆分后添加到新数组中。
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;
// 不需要改变数组下标位置
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;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
扩容的重点在计算数组下标。1.7会重新计算所有元素的在新的数组中的下标位置，1.8在采用更加高效的方式计算新的数组下标。由于扩容总是扩大位原数组容量的两倍，如上图所示，在进行hash(key)&newTab.length时，实际上只多出了红框框出来的一位，如果红框框出来的部分与操作为0，这数组下标位置不变。如果红框框出来的部分与操作为1，则新的数组下标为旧数组下标加上新增位代表的数字（即旧数组容量）。如下图所示，1.8通过判断e.hash & oldCap（oldCap的二进制表示就是新增位），如果是0，则下标位置不变，如果是1，新下标位置为旧的下标位加上旧数组容量。
1.8对1.7死循环问题的改进
1.7中扩容是采用的头插法，在多线程情况下会产生死循环。1.8采用尾插法解决1.7的死循环问题，1.8中分别记录了当前下标位置和新的下标位置的首位指针，添加节点时，分别添加到对应的尾指针后面。
