P8 Java 13中 HashMap的 put方法

    /**
     * 链表转为红黑树的临界值
     */
    static final int TREEIFY_THRESHOLD = 8;
    /**
     * 红黑树退化为链表的临界值
     */    
    static final int UNTREEIFY_THRESHOLD = 6;
    // 构造函数 put
    public V put(K key, V value) {
        // 对key的hashCode()做hash
        return 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为空则创建
    if ((tab = table) == null || (n = tab.length) == 0) // 如果table为null或者没有元素，则扩容
        n = (tab = resize()).length;
    // 步骤②：计算index，并对null做处理
    // 如果首结点值为空，则创建一个新的首结点
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null); 
    else {    // 出现哈希碰撞，开始处理
        Node e; K k;
      
        // 步骤③：节点key存在，直接覆盖value
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;   // 判断元素相等的标准：p与新元素有相同的哈希值和key值
        // 步骤④：判断该链为红黑树
        // 如果首结点的类型是红黑树类型，则按照红黑树方法添加该元素
        else if (p instanceof TreeNode)
            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
        // 步骤⑤：判断该链为链表
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {  // 如果遍历到末尾时，先在尾部追加该元素结点
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // 当遍历的结点数目大于8时，则采取树化结构
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果找到与新元素具有相同的hash和key值的结点，则停止遍历。此时e已经记录了该结点
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;// p指向下一个节点
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // 如果允许修改节点，则修改
            if (!onlyIfAbsent || oldValue == null)
               e.value = value;
            afterNodeAccess(e);  //节点被访问的回调函数，可根据需要覆盖
            return oldValue; // 返回旧值
        }
    }
    ++modCount; //如果执行到了这里，说明插入了一个新的节点，所以会修改modCount，以及返回null
    //步骤⑥：超过最大容量时进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict); // 这个是空函数，可根据需要覆盖
    return null;
}

//将桶内所有的 链表节点 替换成 红黑树节点

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) {
       //如果哈希表中的元素个数超过了 树形化阈值，进行树形化
       // e 是哈希表中指定位置桶里的链表节点，从第一个开始
       TreeNode hd = null, tl = null; //红黑树的头、尾节点
        do {
            //新建一个树形节点，内容和当前链表节点 e 一致
            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);
    }
 }
    TreeNode replacementTreeNode(Node p, Node next) {
    return new TreeNode(p.hash, p.key, p.value, next);
}