深入解析JDK1.8后的HashMap底层存储

深入解析JDK1.8后的HashMap底层存储

前言

这次分享总结很多内容,保姆级注释,有空会将一些核心东西拆开分享

HashMap底层存储数据的结构变化
JDK1.7底层是由 【数组】 & 【链表】组成的,单向链表Entry挂在数组上。JDK1.8后底层则变为【数组】 & 【链表】、【红黑树】,特殊情况下(数组容量大于等于64后,链表的节点数超过了8个),将该链表转换为红黑树

满足红黑树的条件
1、每个节点要么是红色,要么是黑色
2、根节点一定是黑色的
3、每个叶子节点一定是黑色的(最后都会指向 NIL/NULL 的叶子节点)
4、如果一个节点是红色,那么它的左右子节点一定都是黑色的
5、从任意一个节点到叶子节点,所经过的黑色节点的数量一样多

源码解析

全局变量

transient Node<K,V>[] table;  //当前使用的数组

int threshold;			//当前使用的阈值

final float loadFactor;  //当前使用的加载因子

transient int modCount;		//结构变更次数

transient int size;			//k-v对数

对于源码解析的方向是先从HashMap的构造函数开始,到put数据方法

构造函数

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
	//默认加载因子
	//值含义:数组容量的长度到达其容量长度的0.75倍的时候,就会被扩容
	//类似水库中的安全水位线的意思
	static final float DEFAULT_LOAD_FACTOR = 0.75f;
	.
    final float loadFactor;
	.
	public HashMap() {
		// all other fields defaulted
		//初始化加载因子参数值为0.75f
		//元素所占的空间达到加载因⼦的规定值的时候,那么就会执⾏扩容。
		this.loadFactor = DEFAULT_LOAD_FACTOR; 
	}

}

好奇心驱使引出,默认加载因子为何设置成0.75,不是0.6,0.7,0.8这个问题

通过查阅相关资料,得出关键词——泊松分布。大概理解为,在理想情况下,默认加载因子配合hash算法得到的hash码可以使数组中的节点数量遵循泊松分布。可以尽量避免数组节点上的链表长度,避免HashMap的查询时间复杂度从O(1)变成O(n)

视线回到put方法

	public V put(K key, V value) {
	        return putVal(hash(key), key, value, false, true);
	}
	//--------------------------------------------------------
	/**
     * Implements Map.put and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value  如果是true,不改变现有的value
     * @param evict if false, the table is in creation mode.  如果是false, table为创建模式
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;   //tab 存储链表的数组,p 为链表节点, 数字 n,i
        if ((tab = table) == null || (n = tab.length) == 0)  //第一步、赋值 tab 为table数组  , n 为tab的数组长度
            n = (tab = resize()).length;		//如果都为null,对table数组进行初始化并构建
        if ((p = tab[i = (n - 1) & hash]) == null)  //第二步、 向数组中插入元素  
            tab[i] = newNode(hash, key, value, null);   //没有哈希冲突,给tab数组对应索引位置赋值
        else {   							//发生哈希冲突,HashMap是如何处理的?  
            Node<K,V> e; K k;
            if (p.hash == hash &&          
                ((k = p.key) == key || (key != null && key.equals(k))))  
                e = p;						
            else if (p instanceof TreeNode)         
                e = ((TreeNode<K,V>)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) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    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;
            }
        }
        ++modCount;   //记录变更次数
        if (++size > threshold)   //第三步、容量大于阈值,进行扩容调整
            resize();
        afterNodeInsertion(evict);
        return null;
    }

putVal方法中分为三大步

1、创建table数组
2、向table数组中赋值,对哈希冲突与不冲突两种情况的处理
3、判断容量大小是否超过阈值,对其扩容操作

针对putVal三大步进行详细剖析

1、创建table数组

 if ((tab = table) == null || (n = tab.length) == 0)  //赋值 tab 为table数组  , n 为tab的数组长度
            n = (tab = resize()).length;		//如果数组为null,长度为0,对table数组进行初始化并构建

对HashMap数组是否null,或者长度为0时,执行resize()扩容方法
来看看resize方法的源码

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;  //创建旧table数组
        int oldCap = (oldTab == null) ? 0 : oldTab.length;  //旧容量
        int oldThr = threshold;  //旧阈值
        int newCap, newThr = 0;  //新容量,阈值
        if (oldCap > 0) {
        	// 最大容量 MAXIMUM_CAPACITY = 1 << 30  == 1073741824(2的30次方)
            if (oldCap >= MAXIMUM_CAPACITY) { 
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&   //新容量扩容原来的2倍(oldCap << 1)
             		// 默认初始化容量 DEFAULT_INITIAL_CAPACITY = 1 << 4 == 16
                     oldCap >= DEFAULT_INITIAL_CAPACITY)  
                newThr = oldThr << 1; // double threshold   //新阈值扩容原来的2倍
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
        	//oldCap  == 0 && oldThr  == 0
            newCap = DEFAULT_INITIAL_CAPACITY;     
            //新阈值赋值为默认初始容量 * 默认加载因子(16 * 0.75) = 12
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);   
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        //创建newTab数组
        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        //oldTab为null,则直接返回新创建数组
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {  //遍历旧table数组,进行数据迁移操作
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {  
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;   //重新计算新table数组中的位置,并迁移赋值
                    else if (e instanceof TreeNode) 
                     	//对象为TreeNode时进行分裂操作
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order  维护顺序
                        Node<K,V> loHead = null, loTail = null;//定义头尾node
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next; //下个node
                        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;
                            //将低位链表放到新table下标处
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            //将高位链表放到新table[j + oldCap]处
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }
resize方法逻辑判断虽多,主要分为两部分:

1、取旧容量,阈值,对新容量,阈值重新赋值,并扩容
2、对于oldTab 不为 null 的逻辑处理为 旧table数组以及链表或红黑树向扩容后新table数组数据迁移过程,数组长度变化,导致hash寻址的时候有些元素位置变化,进而拆分链表,分裂红黑树操作。红黑树长度分裂后长度小到一定程度,会转换回链表,后续深入讲解链表,红黑树相互转换

2、向table数组中插入元素

分两种情况插入:无哈希冲突,发生哈希冲突

2.1 、没有发生哈希冲突
if ((p = tab[i = (n - 1) & hash]) == null) 
            tab[i] = newNode(hash, key, value, null);   //没有哈希冲突,给tab数组对应索引位置赋值

通过(n - 1)& hash来寻找地址,找索引位置

2.2 、发生哈希冲突
		else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))  //判断索引位置值与待插入值是否相同
                e = p;			//讲旧node赋值给e
            else if (p instanceof TreeNode)			//红黑树处理哈希冲突
                e = ((TreeNode<K,V>)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) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    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;				//将新值value覆盖旧value
                afterNodeAccess(e);		//将红黑树root节点放到链表队首并放到数组中
                return oldValue;
            }
          }
2.2.1 冲突节点与待插入节点key相同
		if (p.hash == hash &&
			  ((k = p.key) == key || (key != null && key.equals(k))))  //判断索引位置值与待插入值是否相同
			e = p;			//讲旧node赋值给e
      //
      //
      //
      if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;				//将新值value覆盖旧value
                afterNodeAccess(e);		
                return oldValue;
            }

不涉及到链表、红黑树时,将旧node赋值为e,新值value赋值给旧value
注意:在put方法中的onlyAbsent设置为false,运行覆盖旧value,反之不可覆盖。

2.2.2 向红⿊树中插⼊元素
else if (p instanceof TreeNode)			//红黑树处理哈希冲突
     e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
.
.
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
}

TreeNode包含两部分:
1、树结构(⽗节点:parent,左⼦节点:left,右⼦节点:right)
2、链表结构(前指针:prev,后指针:next)

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>{
 static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }
 }
 //hashMap中
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        .
        .
    }

继续看详细putTreeVal方法

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;  //寻址root根节点
            for (TreeNode<K,V> p = root;;) {
                int dir, ph; K pk;
                //先确定待插入节点在树的什么位置,左侧,右侧,还是本身位置
                if ((ph = p.hash) > h)      
                    dir = -1;			//左侧
                else if (ph < h)
                    dir = 1;			//右侧
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    return p;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0) {
                    if (!searched) {
                        TreeNode<K,V> q, ch;
                        searched = true;
                        if (((ch = p.left) != null &&
                             (q = ch.find(h, k, kc)) != null) ||
                            ((ch = p.right) != null &&
                             (q = ch.find(h, k, kc)) != null))
                            return q;
                    }
                    dir = tieBreakOrder(k, pk);
                }

                TreeNode<K,V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {			
                    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;
                    if (xpn != null)
                        ((TreeNode<K,V>)xpn).prev = x;			//作为子节点插入相应位置
                        //moveRootToFront将最新的root插入到数组中
                    moveRootToFront(tab, balanceInsertion(root, x));		//balanceInsertion平衡红黑树插入
                    return null;
                }
            }
        }

通过上面分析可以将putTreeVal方法分为五步:
1、寻址根节点
2、确定插入位置
3、构造TreeNode插入对应位置
4、红黑树平衡调整
5、moveRootToFront

2.2.2.1 寻址根节点
深入解析JDK1.8后的HashMap底层存储
parent代表父节点,可知p = tab[i],就是table数组中i位置上元素

 TreeNode<K,V> root = (parent != null) ? root() : this;  //寻址root根节点

如果p的父节点为null,说明自身为root根节点,如果不为null,继续遍历查找
深入解析JDK1.8后的HashMap底层存储
2.2.2.2 确定插入位置
*在for循环中根据p节点的哈市值与待插入元素的hash值,如果p节点哈希值大,则待插入值元素在p节点左侧,判断相反则反之。

2.2.2.3 构造TreeNode插入对应位置
深入解析JDK1.8后的HashMap底层存储
可以看出dir参数等于 -1 时为左侧,反之为右侧。局部变量 x表示待插入的树节点,xp表示x节点的parent节点, xpn表示xp的next节点,后置节点。逻辑过程,将xp双向next互指xpn——>xp双向pre互指x双向next互指xpn

2.2.2.4 红黑树平衡调整
看一下balanceInsertion方法

static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                    TreeNode<K,V> x) {
            x.red = true; 				//初始化待插入元素为红色
            for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
                if ((xp = x.parent) == null) {     //判断是否有父节点元素,没有直接返回自身,并改为黑色
                    x.red = false;
                    return x;
                }
                else if (!xp.red || (xpp = xp.parent) == null)	//判断父节点是否为黑色,或者没有祖父节点,直接返回root节点
                    return root;
                //--------------平衡插入逻辑--------------------
                if (xp == (xppl = xpp.left)) {					//判断x的父节点元素是在祖父节点左侧
                    if ((xppr = xpp.right) != null && xppr.red) {		//判断祖父节点的左右节点如果都是红色节点
                        xppr.red = false;						//将这两个节点颜色变为黑色,祖父节点变为红色
                        xp.red = false;
                        xpp.red = true;
                        x = xpp;
                    }
                    else {
                        if (x == xp.right) {
                            root = rotateLeft(root, x = xp);		//向左旋转
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                root = rotateRight(root, xpp);		//向右旋转
                            }
                        }
                    }
                }
                else {										//x的父节点在祖父节点右侧
                    if (xppl != null && xppl.red) {			//祖父节点的左右子节点如果都为红色节点
                        xppl.red = false;					//将这两个节点都变为黑色,祖父节点变为红色
                        xp.red = false;
                        xpp.red = true;
                        x = xpp;
                    }
                    else {
                        if (x == xp.left) {					
                            root = rotateRight(root, x = xp);		//右旋操作
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                root = rotateLeft(root, xpp);		//左旋
                            }
                        }
                    }
                }
            }
        }

平衡逻辑分两部分
部分一:
如果x的父节点在祖父节点的左侧,操作类型为:变色
操作条件:如果祖父节点的右节点(/左节点)是红色的,操作类型为:旋转 & 变色
部分二:
如果x的父节点在祖父节点的右侧,操作类型为:变色
操作条件:如果祖父节点的左节点(/右节点)是红色的,操作类型为:旋转 & 变色

变色场景一
深入解析JDK1.8后的HashMap底层存储

深入解析JDK1.8后的HashMap底层存储
变色场景二
深入解析JDK1.8后的HashMap底层存储
深入解析JDK1.8后的HashMap底层存储
旋转 + 变色 场景一
深入解析JDK1.8后的HashMap底层存储深入解析JDK1.8后的HashMap底层存储
深入解析JDK1.8后的HashMap底层存储
深入解析JDK1.8后的HashMap底层存储

旋转 + 变色 场景二
深入解析JDK1.8后的HashMap底层存储
深入解析JDK1.8后的HashMap底层存储
深入解析JDK1.8后的HashMap底层存储
深入解析JDK1.8后的HashMap底层存储
2.2.2.5 moveRootToFront
先从方法名分析,将root移动到整条双向链表的头部,并放入到数组中

看一下 moveRootToFront方法

		static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
            int n;
            if (root != null && tab != null && (n = tab.length) > 0) {
                int index = (n - 1) & root.hash;					//判断table数组中存储的元素是不是最新的root节点
                TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
                if (root != first) {								//如果不是,重塑双向链表的链接,
                    Node<K,V> rn;
                    tab[index] = root;
                    TreeNode<K,V> rp = root.prev;					//把root放链表头位置,并插入到table数组中
                    if ((rn = root.next) != null)
                        ((TreeNode<K,V>)rn).prev = rp;
                    if (rp != null)
                        rp.next = rn;
                    if (first != null)
                        first.prev = root;
                    root.next = first;
                    root.prev = null;
                }
                assert checkInvariants(root);						//最终检验整个红黑树结构
            }
        }
2.2.3 向单向链表中插⼊元素

看一下源码部分

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
       		.
       		.
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                    //如果没有与待插入key相同的节点,创建新Node,放入链表末尾
                        p.next = newNode(hash, key, value, null);  	
                        //如果达到红黑树阈值(TREEIFY_THRESHOLD == 8),满足条件后转换为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st	
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                    //如果发现链表中有key相同元素,直接取出,根据onlyAbsent来决定是否覆盖旧value
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
           .
           .
        }
       .
       .
    }

2.2.3.1 treeifyBin方法逻辑

 final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        //如果table数组长度小于64,对数组扩容
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        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 = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
            	//链表转换红黑树操作
                hd.treeify(tab);
        }
    }

对于初始化resize方法中的split方法最后来看一下—((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

 final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
            TreeNode<K,V> b = this;
            //先将原红黑树分为高低位两种红黑树
            // Relink into lo and hi lists, preserving order
            TreeNode<K,V> loHead = null, loTail = null;
            TreeNode<K,V> hiHead = null, hiTail = null;
            int lc = 0, hc = 0;
            //由于TreeNode结构中,有树结构,也有双向链表结构,可通过该双向链表去遍历红黑树每个节点
            for (TreeNode<K,V> e = b, next; e != null; e = next) {
            	//循环体中逻辑:进行扩容后,hash寻址会发生变化
            	//通过重新计算将原有红黑树也拆分高低位双向链表
                next = (TreeNode<K,V>)e.next;
                e.next = null;
                if ((e.hash & bit) == 0) {
                    if ((e.prev = loTail) == null)
                        loHead = e;
                    else
                        loTail.next = e;
                    loTail = e;
                    ++lc;
                }
                else {
                    if ((e.prev = hiTail) == null)
                        hiHead = e;
                    else
                        hiTail.next = e;
                    hiTail = e;
                    ++hc;
                }
            }

            if (loHead != null) {
            	// UNTREEIFY_THRESHOLD = 6  非树阈值为6
                if (lc <= UNTREEIFY_THRESHOLD)
                	//如果低位链表中的元素较少,将红黑树转换为链表	
                    tab[index] = loHead.untreeify(map);
                else {
                    tab[index] = loHead;
                    if (hiHead != null) // (else is already treeified)
                    	//将低位链表重新组装成红黑树
                        loHead.treeify(tab);
                }
            }
            if (hiHead != null) {
            	//如果高位链表中的元素较少,将红黑树转换为链表	
                if (hc <= UNTREEIFY_THRESHOLD)
                    tab[index + bit] = hiHead.untreeify(map);
                else {
                    tab[index + bit] = hiHead;
                    if (loHead != null)
                    	//将高位链表重新组装成红黑树
                        hiHead.treeify(tab);
                }
            }
        }

相比前面逻辑untreeify方法逻辑就很简单

		final Node<K,V> untreeify(HashMap<K,V> map) {
            Node<K,V> hd = null, tl = null;
            //遍历node链表,重新组装成链表
            for (Node<K,V> q = this; q != null; q = q.next) {
                Node<K,V> p = map.replacementNode(q, null);
                if (tl == null)
                    hd = p;
                else
                    tl.next = p;
                tl = p;
            }
            return hd;
        }

// For conversion from TreeNodes to plain nodes
    Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
        return new Node<>(p.hash, p.key, p.value, next);
    }

下面的treeify方法大概看一下

	final void treeify(Node<K,V>[] tab) {
            TreeNode<K,V> root = null;
            //遍历双向链表中的TreeNode
            for (TreeNode<K,V> x = this, next; x != null; x = next) {
                next = (TreeNode<K,V>)x.next;
                x.left = x.right = null;
                //循环第一次进来,默认第一个TreeNode为root
                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;
                        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);
						//将节点x插入到树中
                        TreeNode<K,V> xp = p;
                        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);
        }

最后将链表转换为红黑树方法treeifyBin

	final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            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);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

总结

前辈留我们的东西,值得我们深入体会与学习,第一次分享,有不太准确的地方,还希望交流学习。

上一篇:优雅的拦截TabLayout的点击事件


下一篇:HashSet 如何保证元素不重复——hash码