HashMap源码分析JDK8：treeifyBin方法

超、凢脫俗 2023-06-24 13:27 81阅读 0赞

**HashMap底层数据结构**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70_pic_center]  
**源码分析**

/**
         * 在满足一定条件的情况下，将链表转换成红黑树
         * 
    	 * 形参tab：成员变量table
    	 * 形参hash：新增键值对中key的hash值
         */
        final void treeifyBin(Node<K,V>[] tab, int hash) {
        
            int n, index; Node<K,V> e;
            //1.不转换
            //成员变量table为空 或 table的长度小于MIN_TREEIFY_CAPACITY（64）
            if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            	//扩容即可
                resize();
            //2.转换
            //经哈希函数计算得到新增键值对链接在数组的哪个单元格下
            else if ((e = tab[index = (n - 1) & hash]) != null) {
        
            	//定义首、尾节点
                TreeNode<K,V> hd = null, tl = null;
                //循环链表上的每一个节点
                do {
        
                	//把节点由node类型转换成treeNode类型
                    TreeNode<K,V> p = replacementTreeNode(e, null);
                    //尾节点为空
                    if (tl == null)
                    	//hd成为首节点
                        hd = p;
                    //尾节点不为空
                    //下面这两行代码的意思是：
                    //原来node之间是单向链表，现在treeNode之间要改为双向链表
                    else {
        
                        p.prev = tl;
                        tl.next = p;
                    }
                    tl = p;
                } while ((e = e.next) != null);
                if ((tab[index] = hd) != null)
                	//其实这里正戏才开始。。。
                	//调用treeify方法将准备好的双向链表转换成红黑树
                    hd.treeify(tab);
            }
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20191223143344756.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg==,size_16,color_FFFFFF,t_70#pic_center