HashMap put(K key, V value)解析
这篇博客主要记录HashMap put(K key, V value)方法以及resize()的解析。
根据具体的Demo来解析代码流程，该Demo比较极端，主要是为了在存储键值对时让hashMap调用replacementTreeNode()方法。在创建HashMap时没有指定集合的容量(capacity)。
在阅读之前先了解一下HashMap的数据结构，如下图所示：
Map<String, String> map = new HashMap<>();
map.put("A", "1"); // line 1
map.put("B", "2"); // line 2
map.put("C", "3"); // line 3
map.put("D", "4"); // line 4
map.put("E", "5"); // line 5
map.put("F", "6"); // line 6
map.put("G", "7"); // line 7
map.put("H", "8"); // line 8
map.put("I", "9"); // line 9
map.put("J", "10"); // line 10
map.put("K", "11"); // line 11当第一次向集合中放入键值对时，即运行line 1时
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}hash(key)方法，从下面的代码可以看到hashmap集合会根据key自身的hashcode再次计算得到用于集合内部的hash值。本例比较极端的地方在于：往集合中加入的11个键值对的key（"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"）通过hash(key)方法得到的集合内部的hash值都为0。目的在于让11个节点（Node）都放入第一个桶中。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}putVal(...)
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length; // 1
if ((p = tab[i = (n - 1) & hash]) == null) // 2
tab[i] = newNode(hash, key, value, null); // 3
else {
Node<K,V> e; K k;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 5
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 4
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}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;
}
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
// 1
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<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;
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;
}
当放入第一个键值对<"A", "1">时，table = null(table是hashmap集合底层的Node数组)，进入putVal(...)方法的代码 1 处，此时会进行一次扩容。进入resize方法，int oldCap = (oldTab == null) ? 0 : oldTab.length，oldCap 为 0，运行到resize方法的代码 2 处。集合的新容量（newCap）变成16（DEFAULT_INITIAL_CAPACITY），新阈值（newThr）变成12（DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY 即0.75*16）,所以第一次resize后，集合底层节点数组变成长度为16的数组。
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;回到putVal(...)的代码1处，继续执行，到putVal(...)的代码2处， i = (n - 1) & hash是用来确定该键值对应该放入哪个桶中（这里将集合底层的节点数组（Node[]）的每一个节点称之为桶）。上面的描述中已经说过String "A"~"K"在集合内部的hash值为0，所以15&0=0（&是按位与，即15&0，用二进制表示为 1111 & 0000），此时tab[0]为null，执行putVal(...)的代码3处，创建一个节点，并放入桶0中。
if ((p = tab[i = (n - 1) & hash]) == null)运行到putVal(...)的代码4处时，会判断放入集合中的键值对数是否会超过阈值（threshold），来判断是否进行扩容。但是需要扩容的地方不止这一处，当某一个桶中放入的键值对超过8个并且整个集合的桶的数量不超过64时，也会进行扩容，后续会了解到。
if (++size > threshold)
resize();当放入第二个键值对<"B", "2">时，执行到putVal(...)的代码5处，遍历到该桶的最后一个节点NodeTail，创建一个新的节点newNode，NodeTail.next指向新创建的节点newNode，即 代码对应的 p.next = newNode(hash, key, value, null)。binCount就是用来计数该节点对应应该放入的桶中有多少个节点。当桶中的节点数超过8个时，执行treeifyBin(...)
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}treeifyBin(...) ，这个方法的作用是将桶转换为树，桶中 的节点变成树节点，但是当桶的数量小于64（MIN_TREEIFY_CAPACITY）时，不将桶转为树，而是直接执行扩容，直到桶的数量达到要求。这里不具体解析桶转树的过程（桶转树是将单向链表节点变为双向链表节点，再转为树（双向链表转树，参考treeify(...)方法），树又分为红黑树）。
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);
}
}所以放入第9个键值对<"I", "9">时，binCount = 7，此时集合的容量为16，会触发treeifyBin(...)，但是集合的容量不满足64的大小，所以只会执行扩容，而不会执行将桶替换为树的操作。
当放入第10个键值对<"J", "10">时，binCount = 8，此时集合的容量为32，会触发treeifyBin(...)，但是集合的容量不满足64的大小，所以只会执行扩容，而不会执行将桶替换为树的操作。
当放入第11个键值对<"K", "11">时，binCount = 9，此时集合的容量为64，会触发treeifyBin(...)，集合的容量满足64的大小，所以不执行扩容，而执行将桶替换为树的操作。
总结：
桶转变为treeNode的条件（二者同时满足）：
1.该桶的节点长度超过8
2.table（节点数组）长度大于等于64
当只满足条件1时，会进行扩容（resize）
HashMap的扩容条件（二者满足其一）
1. 当放入HashMap中的键值对数量（++size）> 阈值时（threshold）
2.桶的节点长度超过8
所以，在创建HashMap时，需要根据数据量的大小来设置HashMap的容量，减少放入数据时集合的扩容操作，从而提高性能。另一个值得注意的是：在使用自定义的类对象作为HashMap中映射的键时，务必在重写hashcode()方法时使得节点在桶中分布均匀，减少遍历集合时的时间复杂度。比较极端的例子就是这个博客所展示的，11个键值对的key在集合内部的hash值都为0，从而11个元素都会被放在第一个桶中，整个集合就相当于一个链表，增加了遍历集合时的时间复杂度。
本篇博客主要用于记录HashMap代码解析的学习过程，仅作参考。有什么不恰当的地方，欢迎各位大佬指出。