HashMap没有直接提供putVal接口给用户调用，而实提供put接口，而他通过putVal来实现插入元素。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
*
* @param hash 指定参数key的哈希值
* @param key 指定参数key
* @param value 指定参数value
* @param onlyIfAbsent 如果为true，即使指定参数key在map中已经存在，也不会替换value
* @param evict 如果为false，数组table在创建模式中
* @return 如果value被替换，则返回旧的value，否则返回null。当然，可能key对应的value就是null。
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 参数解析：onlyIfAbsent表示，如果为true，那么将不会替换已有的值，否则替换
// evict：该参数用于LinkedHashMap，这里没有其他作用（空实现）
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// tab是该方法中内部数组引用，p是数组中首节点，n是内部数组长度，i是key对应的索引下标
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 第一次put的时候，table未初始化，也就是tab为空，需要扩容
if ((tab = table) == null || (n = tab.length) == 0)
// 这里实现扩容，具体逻辑稍后分析
n = (tab = resize()).length;
// 获取指定key的对应下标的首节点并赋值给p，如果首节点为null，那么创建一个新的Node节点作为首节点
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// p此时指向的是不为null的首节点，将p赋值给e
// 如果首节点的key和要存入的key相同，那么直接覆盖value的值（在下一个if中执行的）
e = p;
else if (p instanceof TreeNode)
// 如果首节点是红黑树的，将键值对插添加到红黑树，该方法后续分析
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 能走到这里，说明首节点和新put的的这个节点的key不一样，且该Node节点不是TreeNode类型
// 开始需要遍历链表，如果链表中存在该键值对，直接覆盖value。
// 如果不存在，则在末端插入键值对。然后判断链表长度是否大于等于8（其实就是遍历次数 + 1），
// 尝试转换成红黑树。注意此处使用“尝试”，因为在treeifyBin方法中还会判断
// 当前哈希表长度是否到达64，如果达到，转换为红黑树，否则会放弃次此转换，优先扩充数组容量。
for (int binCount = 0; ; ++binCount) {
// 当binCount = 0时，也就是第一次if判断，此时p就是首节点，p.next就是第二个节点
// 其他情况及时链表中其他节点，当e == null的时候，也就是到达了链表的结尾
if ((e = p.next) == null) {
// 新建一个Node并作为链表的最后一个节点
p.next = newNode(hash, key, value, null);
// 判断遍历次数是否>=7（首节点未遍历，直接从第二个节点开始遍历的，当次数为7时，说明链表长度为8）
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// “尝试”将链表转换为红黑树，内部还会判断哈希表长度，不一定转换成功，也许是扩容
treeifyBin(tab, hash);
break;
}
// 只要没走到上面那个if里面，说明链表没有遍历结束，如果在链表中间发现有key一样的，那么就直接将旧值替换成新值
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 将正在遍历的节点赋值给p，方便能遍历下一个节点
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;
if (++size > threshold)
// 如果满足扩容条件，就扩容
resize();
afterNodeInsertion(evict);
return null;
}
//链表转化为红黑树的方法
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 {
// 将链表中的节点Node类型转换成为TreeNode
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);
// TreeNode链表转换成为红黑树
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
?在JDK8之后引入了红黑树，当哈希表的桶中链表元素超过8个的时候（此时哈希表长度不小于64），会自动转换成红黑树。若桶中元素小于等于6时，树结构还原成链表形式。
红黑树的平均查找长度是log(n)，长度为8，查找长度为log(8)=3，链表的平均查长度为n/2，当长度为8时，平均查找长度为8/2=4，这才有转换成树的必要；链表长度如果是小于等于6，6/2=3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。以6和8来作为平衡点是因为，中间有个差值7可以防止链表和树之间频繁的转换。
假设，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。概括起来就是：链表：如果元素小于8个，查询成本高，新增成本低，红黑树：如果元素大于8个，查询成本低，新增成本高。
