HashMap的put方法
同学们都知道在使用HashMap保存数据时，都是通过调用其put()方法完成的，但是从来没有看过其源码或者被源码劝退的人依然数不胜数。今天我们就一起看看它是怎么实现的，又有哪些细节
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
可以看到，只有短短的一行，调用一个putVal()方法。因此我们主要看一下该方法的实现。
putVal()方法源码
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)方法是所有存放数据的核心方法，是面试中常见的知识点之一。j下面我们贴上源码来分析一下
/**
* hash - 根据参数key调用 hash(Object key) 方法得到的hash值
* key - 传入的key
* value - key对应的value
* onlyIfAbsent - Absent为缺席的意思，ture - 在当前哈希表中不存在当前key的情况下，才会保存或覆盖该key对应的value
* evict - 该参数用于LinkedHashMap的putVal()方法，在HashMap中可忽略该参数，
* 返回 - 如果产生了value覆盖，则返回原value，否则返回为空
**/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果底层数组为空，或其长度为0，则通过扩容的方式对底层数组初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 根据key对应的hash值，与数组长度减一，进行与运算，得出该key应保存在数组位置的下标
// 如果该下标处没有数据，则直接通过newNode()来实例化一个Node对象，并保存在该数组位置。
if ((p = tab[i = (n - 1) & hash]) == null)
// 已经通过hash值确定了数组下标
// 处理当前位置不存在数据的情况
tab[i] = newNode(hash, key, value, null);
else {
// e表示将要保存的Node对象
Node<K,V> e; K k;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
// 如果当前位置所保存数据的hash值、key值与将要保存数据的hash值、key值相同，则将该Node对象作为要保存的Node对象e，进行value的覆盖
e = p;
else if (p instanceof TreeNode)
// 如果当前位置所保存数据是TreeNode对象，说明该位置保存的是一个红黑树
// 调用TreeNode类的putTreeVal把将要保存的数据保存到红黑树中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 当前位置既有数据，但其key与将要保存的key不相同，且该位置保存了一个链表
for (int binCount = 0; ; ++binCount) {
// 遍历链表并记录该链表上node对象的数量binCount
if ((e = p.next) == null) {
// 以尾插法的方式，通过newNode()来实例化一个Node对象，并保存在该链表尾部，并结束遍历
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 如果该链表上node对象的数量达到8个，则调用treeifyBin()方法将该链表进化为红黑树。
// 注意，在该方法中，还会进一步判断数组长度，
// 当数组长度达到64时，才会真正的将其进化为红黑树
// 否则，仅仅将数组进行扩容
treeifyBin(tab, hash);
break;
}
// 在遍历链表的过程中，如果某个node对象的hash值和key值与将要保存的hash值和key值相同，则结束遍历
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 遍历链表的操作
p = e;
}
}
// 如果在上面的逻辑中，找到了key值相同的node对象，则将value值进行覆盖
if (e != null) {
// existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 至此，数据key-value已经保存到哈希表中了
++modCount;
if (++size > threshold)
// 如果当前哈希表中的节点数量超过扩容阈值(即 数组长度 * 0.75)，则对数组进行扩容。
resize();
// 该方法在LinkedHashMap中实现，作为插入数据后的回调
afterNodeInsertion(evict);
return null;
}
在上面的注释中我们已经把该方法讲的非常透彻了，下面再通过简洁的叙述对其进行概括
当我们向HashMap中保存一个key-value键值对时
如果地层数组尚未实例化，或数组长度为0，则通过扩容对其进行实例化以及初始化
首先，通过key计算出的hash值，找到当前key-value键值对应保存的位置，即数组的下标
如果数组该位置没有数据，则直接将key-value键值对保存在该位置即可。
如果该位置有数据，则通过判断key是否相同(通过
equals()方法)，如果key相同，则将value值进行覆盖，并返回原value值。注意：判断key是否相同时，
(k = e.key) == key || (key != null && key.equals(k))说明key是允许为空的判断该位置数据的类型(红黑树或链表)，并以不同的方式遍历红黑树或链表，在遍历的过程中，依然是通过判断key是否相同(通过
equals()方法)，如果key相同，则将value值进行覆盖，并返回原value值。否则，将以红黑树或链表的方式将该key-value键值对保存到红黑树或链表中。
图例
下面再以图例进行分析
当我们插入一个
key=F，value=6的键值对时，通过hash()方法得出F的hash值为6，根据hash & length - 1得到该键值对应保存在数组下标为2的位置。而下标为2的位置上为空，因此直接将该键值对保存到该位置即可。
当我们插入一个
key=G，value=7的键值对时，通过hash()方法得出G的hash值为0，根据hash & length - 1得到该键值对应保存在数组下标为0的位置。而下标为0的位置上已经存在一个key-value键值对(A-1)了，因此比较A是否与G相等，因为A ≠ G，所以通过尾插法将 < G - 7 > 插入到 < A - 1 > 后面
当我们插入一个键值对 < D - 8 > 时，通过
hash()方法得出D的hash值为5，根据hash & length - 1得到该键值对应保存在数组下标为1的位置。而下标为1的位置上已经存在一个key-value键值对(B-2)了，因此比较D是否与B相等，因为D ≠ B，所以通过节点的next属性来遍历链表，然后遍历到键值对 < C - 3 > ，比较C是否与B相等，因为D ≠ C，所以继续通过next属性遍历。当遍历到键值对 < D - 4 > 时，比较D是否与D相等，因为D == D，所以将value值进行覆盖即可。
如果插入一个键值对 < H - 9 > 时，通过
hash()方法得出H的hash值为3，根据hash & length - 1得到该键值对应保存在数组下标为3的位置。而通过key值的判断，E ≠ H，所以需要通过遍历红黑树的方式找出该红黑树中key也等于H的节点并将其value值进行覆盖，如果没有找到key也等于H的节点，则将键值对 < H - 9 > 构造成TreeNode对象，以红黑树的插入方式，将该对象插入树中。红黑树的操作可参考前面的文章红黑树当插入操作完成后，再判断当前链表是否需要进化为红黑树，当前数组是否需要扩容。
小结
延迟初始化
底层数组在第一次调用put()方法是通过resize()扩容进行实例化的。
当出现哈希冲突或扩容，且当前位置为链表时，采用尾插法将节点插入到链表
key可以为空，value也可以为空
先插入，后扩容
插入的数据是无序的，因为在整个put过程中，并没有什么信息能够体现出整个哈希表内数据的存放顺序。
