public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}1、如果key==null时，hash就返回0。
2、这里先取到key的hashcode -> h，并且让h右移16位，即高位都变成了0，低位变成了高位。例如：
h = 0b 0010 0101 1010 1100 0011 1111 0010 1110
右移16位后h = 0b 0000 0000 0000 0000 0010 0101 1010 1100
就是key的hashcode的高16位和低16位做异或。
这个hash方法的作用其实就是让hash值的高16位也参与运算。因为之后计算index的时候是
index= (length-1) & h，如果length很小的时候，那么它的32位中高16位一定都是0的，如果hash值的高16位也是0，那么高位就相当于没有参与运算，只有低16位参与了运算。所以，这个hash方法使key的hash值高16位也参与了运算，这样计算index时会更均匀一点，防止了碰撞的发生。
二、putVal(hash(key), key, value, false, true)final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
// tab表示当前的散列表；p表示当前散列表的元素；
// n表示散列表数组长度；i表示路由寻址结果
// 这一步表示还没有初始化的话，第一次put时进行初始化，懒加载
// 初始化时通过resize()方法进行table的初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果当前table中这个位置没有数据，那么就将当前数据封装成node,
//直接放入这个table的位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node e; K k;
//当前index这个数组中有元素，并且hash值相同，并且key完全一致
// 那么就需要替换 *** 作，返回旧的值。
// 地址一致或者equals一致
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果是红黑树
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
//通过for循环进行链表查询
for (int binCount = 0; ; ++binCount) {
//如果链表的元素为null,那么就插入新元素
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果链表的长度大于等于8，
//即插入的这个元素是链表的第9个,不包括数组中的那个
//并且数组长度大于64，不大于64的话会进行扩容
//进行红黑树的转换
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果在链表中找到了hash值一样，并且key完全一致的，就替换。
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;
}
}
//记录散列表修改的次数，这个不包括value替换
//只记录新插入元素和删除元素
++modCount;
//如果元素总的数量超过了阈值：tableSize*loadFactor
//进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
} 1、如果table=null或者table的长度等于0是，通过resize()方法进行散列表的初始化，获取当前散列表的长度。
2、计算得到当前的index=(length-1)&h，如果当前散列表数组中该位置没有元素，那么就直接插入。
3、如果当前位置的元素不为null,并且hash值一样，key地址相同或者equals相同，那么就进行替换。
4、for循环，来查看链表上的元素，如果为null，表示还没有链表，那么就插入元素，并且将散列表中该位置元素的next指针指向这个刚插入的元素；如果插入的这个元素是链表上的第8个元素，那么就转换为红黑树；如果不为null，那么就在for循环中，找到hash值相同，并且key完全一致的元素，然后进行替换。直到找到最后面都没有，那么就是插入 *** 作。
5、如果当前位置的元素类型是treeNode，代表是红黑树，那么就行红黑树的 *** 作。
6、最后在插入后判断当前的元素个数是不是大于阈值（tableSize*loadFactor），大于的话就resize()扩容。
三、resize扩容1、如果oldCap>0，代表已经初始化过了，是正常的扩容，进行容量判断，在不超过最大值的时候，扩容为2倍
2、else中就是进行默认初始化的容量和阈值>16和12
3、扩容：
Node[] newTab = (Node[])new Node[newCap];
table = newTab;
//进行初始化过了的情况
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//如果原数组位置的元素，没有链表或者红黑树
//这种情况下直接计算新的index,并存入
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//如果是红黑树节点
else if (e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap);
//链表
else { // preserve order
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
next = e.next;
//如果元素的高位是0，那么新计算的index的值
//应该和以前的是一样的，还是在新数组的原位置
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//元素的高位是1，那么新的index和原index就不同了
//这时就是高位链
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;
} 逐个遍历旧数组中的每一个位置
1）、如果原位置没有next元素，即元素不是链接，也不是红黑树，这种情况就直接计算新的index值，然后插入到新数组中
2）、如果是是treeNode类型，那么就进行红黑树的处理
3）、如果是链表，那么会分为高位链和低位链。例如默认初始容量是16，那么index=15这个位置的hash值后四位就是1111，扩容时容量升了1倍，那么就是参与运算的位数增加了1位（16是1111,32时就是11111）。15位置的hash值的第五位是不知道多少的，可以是1和0。那么是0的与旧的length进行&运算，01111 & 01111就算成了01111，即没有变化，这就是低位链，在新的数组中还是原位置，即index=15；而第五位是1的，11111 & 01111就变成了11111，与原index不同，即index为31了。就要进行迁移。
四、扩展：链表转红黑树 *** 作错略讲解final void treeifyBin(Node[] tab, int hash) {
int n, index; Node e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode hd = null, tl = null;
do {
TreeNode 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);
}
} 1、如果tab还没有初始化，或者table数量小于64，先进行resize()扩容
2、将节点都封装成TreeNode，然后构建红黑树。
红黑树的结构
static final class TreeNode extends LinkedHashMap.Entry {
TreeNode parent; // red-black tree links
TreeNode left;
TreeNode right;
TreeNode prev; // needed to unlink next upon deletion
boolean red; 3、红黑树扩容
1）、通过split方法进行扩容。
2）、通过是分成高位树和低位树
3）、最后根据树结构元素的个数，看是否需要恢复成链表结构。（元素个数<=6）
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）