public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//HashMap.put的具体实现
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
//判定table不为空并且table长度不可为0,否则将从resize函数中获取
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//JDK1.7之前的indexfor() 方法，也是扩容必须2^n的原因
if ((p = tab[i = (n - 1) & hash]) == null) //令table数组索引处的首位节点为p
//如果p为null则直接放入新节点Node
tab[i] = newNode(hash, key, value, null);
else { //如果p不为空
Node e; K k;
//对这个元素进行Hash和key值匹配
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; // 如果索引首位节点p的key值与新节点key相同，则直接覆盖
else if (p instanceof TreeNode) //如果数组中的这个元素p是TreeNode类型
//判定成功则在红黑树中查找符合的条件的节点并返回此节点
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else { //若以上条件均判断失败，则执行以下代码
//向Node单向链表中添加数据，遍历链表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) { //如过链表的每个节点key.equals都返回false，则直接添加到末尾
p.next = newNode(hash, key, value, null);
//若节点数大于等于8
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//转换为红黑树
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break; //如果链表中有节点key.equals返回true，则后续用新节点覆盖该节点
p = e; //更新节点p以记录下一个节点
}
}
if (e != null) { // break之后，使用新节点覆盖key.equals为true的节点
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold) //判断是否需要扩容
resize();
afterNodeInsertion(evict);
return null;
}
putVal() 原理总结：
- HashMap默认有一个Node数组table； 将K、V以及hash(key)算得的哈希值封装到Node对象当中；
- 使用indexfor方法，用哈希值和（数组长度-1）做与运算 算出数组的索引值 i 以定位，得到i索引处的数组元素首位节点p （JDK1.7之后没有indexfor方法），如果p为null则直接放入新节点Node；
- 需要判断：
①先调用equals方法，如果索引首位节点p的key和新节点的Key相同，则新节点直接覆盖 p，不用看p后面的节点；
②如果p节点属于TreeNode，则在红黑树中查找符合的条件的节点并返回此节点
③如果p不属于红黑树则是单向链表，遍历单向链表，调用每个节点的key.equals() 方法，返回true则 覆盖，全都false则添加到末尾
（过程中会判断节点数是否＞8，是则转换为红黑树）
因为计算索引时是 i = (n - 1) & hash即将( 数组长度-1 ) 和Key的哈希值进行与运算，只有当数组的长度是2的n次方，则（数组长度-1）的二进制才能保持后面全是1，全是1才能保证数组中的任意一位置都能取到；
如数组长度5 ，则5-1=4 ，4的二进制为00000100 ，那么索引 1 2 3都无法获取到！ （与运算中真真才能为真）；
public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;
//tab：内部数组 first: 索引位首节点 n: 数组长度 k: 索引位首节点的key
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) { //JDK1.8之前的indexfor()
//如果索引位首节点的hash值与需要寻找的hash值相等，并且key的内容也相同，则返回该节点
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
//如果是首结点p属于TreeNode，则到红黑树中去查找并返回
return ((TreeNode)first).getTreeNode(hash, key);
//遍历单链表寻找节点
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e; // 链表中节点key.equals为true则返回
} while ((e = e.next) != null);
}
}
return null; // 如果链表中节点key.equals全为false则返回null
}
getNode()原理总结：
- 使用indexfor方法，用Key的哈希值和（数组长度-1）做与运算，算出数组的索引值 i 以定位，得到i索引处的数组元素首位节点first，如果first的key.equals返回true，则直接返回first节点
- 判断：
①如果first为空，返回null
②如果first属于TreeNode，则到红黑树中去查找并返回
③遍历单链表，若链表中节点key.equals为true则返回，如果链表中节点key.equals全为false则返回null
由于在Java中两个不同的对象可能有一样的哈希值，因为不同的键可能有一样hashCode，从而导致冲突的产生；
HashMap使用链式地址法应对哈希冲突；
在JDK1.8 之前， 如果发生碰撞往往是将该value直接链接到该位置的其他所有value的末尾，即相互碰撞的所有value形成一个链表。因此，在最坏情况下，HashMap的查找时间复杂度将退化到O（n）.
JDK1.8后，当一个位置所在的冲突过多时（元素>8），存储的value将形成一个红黑树，目的是提高检索效率，在最坏情况下，HashMap的查找时间复杂度将从O（1）退化到O（logn）；
参考：
https://blog.csdn.net/xadasss/article/details/116793267
https://blog.csdn.net/m0_51212267/article/details/124144767
