put方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i; // 这个p是开始定位到的Node或者TreeNode
if ((tab = table) == null || (n = tab.length) == 0) // 如果数组是null或者长度是0
n = (tab = resize()).length; // 先扩容，然后获取数组长度
if ((p = tab[i = (n - 1) & hash]) == null) // 获取要存储位置的第一个元素是null，说明该位置是空的
tab[i] = newNode(hash, key, value, null); // 创建一个新的节点对象放在该位置 【添加元素位置1】
else { // hash冲突，位置上有数据了
Node<K,V> e; K k; // 这个e就是最终找到的节点
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) // 第一个的hash值和要存的数据hash相同，而且key相同
e = p; // 说明要找的就是这个元素
else if (p instanceof TreeNode) // 如果第一个节点类型是TreeNode，说明已经变成红黑树了
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 执行红黑树的查找流程
else { // 不是红黑树，第一个也不是，就要按照链表继续往下找了
for (int binCount = 0; ; ++binCount) { // 循环遍历链表
if ((e = p.next) == null) { // 下一个节点是null，也就是之前没有存过这个数据，后面当前没有其他节点了
p.next = newNode(hash, key, value, null); // 创建一个新元素放到链表中下一个节点位置就行了 【添加元素位置2】
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) { // 找到了对应的节点
V oldValue = e.value; // 存一下旧的值
if (!onlyIfAbsent || oldValue == null) // 允许覆盖或者值是null
e.value = value; // 设置新值
afterNodeAccess(e); // 后置处理，空方法
return oldValue; // 返回旧值
}
}
// 如果是新添加的元素会执行到这里，上面的【添加元素位置1】【添加元素位置2】
++modCount;
if (++size > threshold) // 判断容量是否超过阈值
resize(); // 扩容
afterNodeInsertion(evict); // 后置处理，空方法
return null; // 返回null
}
1、数组是不是空，是空的话先扩容；
2、根据hash定位到数组的索引位置，如果是null，直接创建节点添加到该位置；
3、如果不是null，类型是TreeNode，说明已经变成红黑树，按照红黑树的方式进行查找；
4、如果是普通Node类型，就按照链表进行查找；
扩容resize方法
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length; // 旧容量，如果没有初始化就是0，有数据就是数组长度
int oldThr = threshold; // 扩容阈值
int newCap, newThr = 0;
if (oldCap > 0) { // 旧容量 > 0
if (oldCap >= MAXIMUM_CAPACITY) { // 旧容量大于最大值
threshold = Integer.MAX_VALUE; // 阈值更新为最大
return oldTab; // 不能扩容了，直接返回旧数组
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) // 新容量为旧容量的2倍 小于最大容量 而且 旧容量达到初始化阈值
newThr = oldThr << 1; // double threshold // 新容量为旧容量的2倍
}
else if (oldThr > 0) // 旧容量为0，旧阈值大于0
newCap = oldThr; // 新容量为旧阈值
else { // new HashMap()第一次put会执行这里
newCap = DEFAULT_INITIAL_CAPACITY; // 默认初始化容量 16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 默认初始化阈值 12
}
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; // 把原来位置设为null
if (e.next == null) // 如果只有一个节点，没有形成链表
newTab[e.hash & (newCap - 1)] = e; // 重新hash分配到新的数组中
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;
}
红黑树插入
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this; // 找到根节点
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h) // 要插入的hash值比根节点小
dir = -1;
else if (ph < h) // 要插入的hash值比根节点大
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk))) // 要插入的hash值等于根节点，而且key相同，说明就是根节点
return p;
else if ((kc == null && // 第一次默认是null，后面是String
(kc = comparableClassFor(k)) == null) || // k的类型是不是实现了Comparable接口，k一般都是String
(dir = compareComparables(kc, k, pk)) == 0) {// 1、判断pk == null，也就是root节点的key是不是null，一般不会存null，不符合 // 2、判断pk的类型是不是kc，也就是root节点的key类型是不是String，一般都符合
// 3、符合2的话，比较k.compareTo(pk)，前面的if判断已经知道两个key是不相等的
// 也就是发生了hash冲突，所以这里一定不是0，不太懂这里的逻辑
if (!searched) { // 初始值为false
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null && // 左子树不为null
(q = ch.find(h, k, kc)) != null) || // 左子树找到了
((ch = p.right) != null && // 右子树不为null
(q = ch.find(h, k, kc)) != null)) // 右子树找到了
return q; // 找到了就返回
}
dir = tieBreakOrder(k, pk); // hash冲突也要有个顺序，相等放在左边，dir=-1
}
TreeNode<K,V> xp = p; // 根节点
if ((p = (dir <= 0) ? p.left : p.right) == null) { // dir小于等于0表示比根节点小，放在左子树，dir>0表示比根节点大，放在右子树
// 子树遍历到头了，那就插入新节点，否则重新循环
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn); // 创建一个树节点
if (dir <= 0)
xp.left = x; // 放在左边
else
xp.right = x; // 放在右边
xp.next = x; // 记录链表关系
x.parent = x.prev = xp; // 记录树节点的parent和链表的prev
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x; // 记录链表关系
moveRootToFront(tab, balanceInsertion(root, x)); // 平衡操作，旋转
return null; // 插入新节点，返回null
}
}
}
tableSizeFor方法
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
如果指定了初始容量，就按照这个方法计算出不小于指定容量的最小的2的幂作为初始容量。
基本思路：
先把指定的cap减个1，计算完再加个1，目的是为了防止cap本身就是2的幂，最后算出来的变成了cap的2倍，比如指定的是4，最后计算出来的是8；
假设初始值为0001xxxxxxxxxxx，x表示不确定0还是1
右移1位按位取或操作，得到结果00011xxxxxxxxxxxx，最左侧有效位变为两个1
右移2位按位取或操作，得到结果0001111xxxxxxxxxxx，最左侧有效位变为4个1
依次类推，右移4位变为8个1，右移8位变为16个1，右移16位变为32个1
因为是int类型的，所以最长32位，最多移动16位就把有效位全部变为1了，最后再加1，就变成2的n次幂了
标签：Node,hash,HashMap,int,源码,key,null,节点 From： https://www.cnblogs.com/bright1st/p/17596151.html