哈 ，一年一更新 ，orz
鉴于jdk里面源码实在是贼乱，代码倒是不难，但是写的太紧凑了(
你为毛不加括号，为毛啊，看起来费劲
)，我决定刨开写写注释
putVal方法 插入数据的
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//当前表
Node<K,V>[] tab;
//
Node<K,V> p;
int n, i;
//如果table是否为空，为空则进行 resize() 操作，
if ((tab = table) == null || (n = tab.length) == 0){
n = (tab = resize()).length;
}
//此时： n = table的容量
// tab = table表
// 计算hash对应table的数组下标
i = (n - 1) & hash；
//取出对应位置的节点
p = tab[i];
//如果对应节点为空的话，就创建一个新的节点
if ( p == null){
tab[i] = newNode(hash, key, value, null);
} else {
//如果节点不为空的话
Node<K,V> e;
K k;
//当前取到的节点的hash值和请求的的hash相等 并且
//key值也和请求的key内存位置相等 或者 equals相等 总之 ，如果判断是一个对象
if (p.hash == hash &&
(
(k = p.key) == key || (key != null && key.equals(k))
)
){
//直接将当前节点赋给e
e = p;
}else if (p instanceof TreeNode){
//如果当前节点是一个树节点,就使用 putTreeVal 的方式进行插入
//并且，如果 key 如果判断是一个对象 就返回， 如果插入成功，就返回null
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
}else {
//如果当前是链表节点，便利链表节点
for (int binCount = 0; ; ++binCount) {
//如果当前节点下一个节点是null，就添加一个新节点放在 p 后面
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果这个时候，达到了树 阈值 ，就 执行treeifyBin
//但是 实际上，如果没有达到 MIN_TREEIFY_CAPACITY = 64 最小容量，也是不会转化为树的，只是执行 resize 操作
//这个很多人以为 到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;
p = e;
}
}
//所以这里只有 如果判断是一个对象 就是说 existing mapping for key 的时候才会调用
if (e != null) { // existing mapping for key
V oldValue = e.value;
//value 替换为最新的
if (!onlyIfAbsent || oldValue == null){
e.value = value;
}
afterNodeAccess(e);
return oldValue;
}
}
//修改次数，修改版本+1
++modCount;
//不够用了，resize
if (++size > threshold){
resize();
}
//LinkHashMap用的
afterNodeInsertion(evict);
return null;
}
treeifyBin方法 将一个hash对应节点位置的 链表转化为红黑树
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n,
index;
Node<K,V> e;
//划重点，不是到8就转化为树，而是大于 MIN_TREEIFY_CAPACITY = 64 的时候才会去转化 ，否则就是 resize
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY){
resize();
//大于 64 ，并且table 的 hash 计算 的位置的节点不为空 ，判断很严谨啊
//e,此时为 hash对应位置 首个节点
}else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null,
tl = null;
//do循环整起来，
do {
//构造一个树节点，没啥
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);
//总之经过上面，hd 变成了一个 链表 ，一个节点上 TreeNode 的链表
//所以下一步自然是要把链表转化成树
if ((tab[index] = hd) != null){
//向下看
hd.treeify(tab);
}
}
}
treeify 方法 把链表转化为🌲 --- 未完待续
/**
* Forms tree of the nodes linked from this node.
*/
final void treeify(Node<K,V>[] tab) {
//红黑树的根节点
TreeNode<K,V> root = null;
//国际惯例，先便利链表
//初始化的时候 x 就是head节点 ，
//之后依次往后
for (TreeNode<K,V> x = this, next; x != null; x = next) {
//next 当前节点下一个节点
next = (TreeNode<K,V>)x.next;
//当前节点左右子树🍠设置为null
x.left = x.right = null;
//初始化根节点
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
//开始决定当前节点插入到那个 下面，
for (TreeNode<K,V> p = root;;) {
int dir,
ph;
K pk = p.key;
//----决定dir的大小
if ((ph = p.hash) > h){
dir = -1;
}else if (ph < h){
dir = 1;
}else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0){
dir = tieBreakOrder(k, pk);
}
//----
TreeNode<K,V> xp = p;
//如果 dir小于0 也就是 当前这个比当前值小的，就把左子树 设置为p
//所以看到了吧 hashMap的红黑树 大顶树
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0){
xp.left = x;
}else{
xp.right = x;
}
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
网友评论