原文链接：

一，先来看几个变量、常量、静态变量、静态常量：

1）链表与红黑树互相转化的阀值：

    //将链表转化为红黑树的阀值
    static final int TREEIFY_THRESHOLD = 8;

    //将红黑树转回为链表的阀值
    static final int UNTREEIFY_THRESHOLD = 6;

    //将链表转为红黑树的最小entry数组的长度为 64
    //当链表的长度 >= 7，且entry数组的长度>= 64时，才会将链表转为红黑树。
    static final int MIN_TREEIFY_CAPACITY = 64;

2） Map的默认初始化容量以及容量极限：

    //HashMap默认的初始容量大小--16，容量必须是2的幂
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    //HashMap的容量极限，为2的30次幂；
    static final int MAXIMUM_CAPACITY = 1 << 30;

3）默认负载因子、实际元素数量：

    //负载因子的默认大小，
    //元素的数量/容量得到的实际负载数值与负载因子进行对比，来决定容量的大小以及是否扩容；
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    //HashMap的实际元素数量
    transient int size;

4）table——Entry数组；


    //Node是Map.Entry接口的实现类，可以将这个table理解为是一个entry数组；
    //每一个Node即entry，本质都是一个单向链表
    transient Node<K,V>[] table;

5）Map已经修改的次数、下一次扩容的大小、存储负载因子的常量：

    //HashMap已在结构上修改的次数 结构修改是指更改 HashMap 中的映射数量或以其他方式修改其内部结构（例如，重新散列）的那些
    transient int modCount;

    //下一次HashMap扩容的阀值大小，如果尚未扩容，则该字段保存初始entry数组的容量，或用零表示
    int threshold;

    //存储负载因子的常量，初始化的时候将默认的负载因子赋值给它；
    final float loadFactor;

5.5）什么是Map已经修改的次数？

参考链接：https://blog.csdn.net/u012926924/article/details/50452411

modCount用于记录HashMap的修改次数，在HashMap的put(),get(),remove(),Interator()等方法中,都使用了该属性。

由于HashMap不是线程安全的，所以在迭代的时候，会将modCount赋值到迭代器的expectedModCount属性中，然后进行迭代；

如果在迭代的过程中HashMap被其他线程修改了，modCount的数值就会发生变化，这个时候expectedModCount和ModCount不相等，迭代器就会抛出ConcurrentModificationException()并发修改异常。

二，链表转红黑树：

1）为什么要将链表转为红黑树：

当这个链表过长了，查找这个链表上的元素的时候自然会变慢，所以链表如果过长了会影响到HashMap的性能，

所以后来在Java8中，当链表过长时，会将该链表自动转为红黑树，红黑树是一个自平衡二叉树，能够优化查找的性能。

2）链表多长时，会变成红黑树？

把链表转为红黑树、还是选择扩容，看这几个阀值：

    //将链表转化为红黑树的阀值
    static final int TREEIFY_THRESHOLD = 8;

    //将红黑树转回为链表的阀值
    static final int UNTREEIFY_THRESHOLD = 6;

    //将链表转为红黑树的最小entry数组的长度为 64
    //当链表的长度 >= 7，且entry数组的长度>= 64时，才会将链表转为红黑树。
    static final int MIN_TREEIFY_CAPACITY = 64;

结论：

①，当链表的长度 >= 7，并且entry数组的长度>= 64时，才会将链表转为红黑树。

②，当链表的长度 >= 7，但是entry数组的长度< 64时，不转为红黑树，而是调用resize方法进行扩容；

三，看源码：

1）什么时候将链表转化为红黑树？

//将链表转化为红黑树的阀值
static final int TREEIFY_THRESHOLD = 8;

//put方法中的putVal方法的内部源码： 
//binCount：计数链表的长度
for (int binCount = 0; ; ++binCount) {
	if ((e = p.next) == null) {
		p.next = newNode(hash, key, value, null);
		//如果链表的长度大于等于7了，则将其转为红黑树：
		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;
}

再来看进行树化的方法–treeifyBin()：

// 可对链表进行树化的最小表容量(Node数组实际长度)。
static final int MIN_TREEIFY_CAPACITY = 64;

/**
	翻译：①，替换给定哈希索引处 bin 中的所有链接节点（将链表转为红黑树），
          ②，除非表(Node)太小，在这种情况下——调整大小（扩容）。
	*@param tab ：entry数组
    *@param hash：将key进行哈希函数计算之后的哈希值
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
	int n, index; Node<K,V> e;
	//如果entry数组为空，或者entry数组的长度小于64，则进行扩容，(不转红黑树)；
	if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
		resize(); //扩容方法
		
	//否则的话，即只有在链表的长度大于等于7、且entry数组的长度大于等于64的时候，才将链表转为红黑树：	
	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);
	}
}

步骤总结：

1、链表长度达到了转树的阀值(默认为8)-1，即链表的长度 >= 7，且此时entry数组的大小< 转树的容量阀值64，则，不转为红黑树、改为调用resize方法进行扩容；

2、链表长度达到了转树的阀值(默认为8)-1，即链表的长度 >= 7，且此时entry数组的大小>= 转树的容量阀值64，那么此时才将该链表转为红黑树；

2）什么时候将红黑树退化回为链表：

还是在resize()扩容方法中，

final Node<K,V>[] resize() {
    //...
	//如果原Node数组不为空
	if (oldTab != null) {
		//遍历原Node数组：
		for (int j = 0; j < oldCap; ++j) {
			Node<K,V> e;
			if ((e = oldTab[j]) != null) {
				oldTab[j] = null;
				
				//如果该Node元素的next==null，则说明该Node元素后边既没有链表又没有红黑树；
				if (e.next == null)
					//则将该Node元素直接存于新Node数组的指定位置
					newTab[e.hash & (newCap - 1)] = e;
				
				//如果该Node元素后边跟着的是一个红黑树结构：
				else if (e instanceof TreeNode)
					//在新的Node数组中，将该红黑树进行拆分，
					//（如果拆分后的子树过小(子树的节点小于等于6个)，则取消树化，即将其转为链表结构）；	
					((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
				
				//如果是链表的情况下，则进行下面的链表数据转移的操作
				else { // preserve order
                    //...
				}
			}
		}
	}
	return newTab;
}

可以看出，在扩容方法 resize()中的“将原Node数组中的元素拷贝到新的Node数组”中的步骤中，如果遍历到的Node元素是一个红黑树的时候，出现了一个split()方法，

该split方法的目的是：将该红黑树进行拆分，然后迁移到新的Node数组中。

（如果拆分后的子树过小(子树的节点小于等于6个)，则取消树化，即将其转为链表结构）；

扩容方法 resize()，详情请见：HashMap的扩容——resize()方法_Morning sunshine的博客-CSDN博客

点进去这个split方法：

//将红黑树退化转回链表的阀值：
static final int UNTREEIFY_THRESHOLD = 6;

//将树进行拆分的split方法：

//左子树：
if (loHead != null) {
	//如果该左子树的元素数量小于等于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);
	}
}

可以看出，如果拆分后的子树过小，即该左子树/右子树的元素数量小于等于6了，则取消树化，将该红黑树转回链表结构 。

拓展：split()方法完整源码分析：

原文链接：HashMap中红黑树扩容split()_crazyK.的博客-CSDN博客

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;
	//因为红黑树是由链表改造的，所以红黑树的扩容还是对链表进行操作
	//对for循环链表(红黑树)进行高低拆分操作
	for (TreeNode<K,V> e = b, next; e != null; e = next) {
		//取e的下一节点赋值给next遍历
		next = (TreeNode<K,V>)e.next;
		//取好e的下一个节点后将其赋值为空，方便GC回收
		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;
		}
	}
	/*
		拆分之后判断链表的长度是否<=UNTREEIFY_THRESHOLD=6
		如果满足，则将红黑树转回链表
	*/
	//如果低位链表首节点不为null，说明有这个链表存在
	if (loHead != null) {
		//如果低位链表的长度<=UNTREEIFY_THRESHOLD=6
		if (lc <= UNTREEIFY_THRESHOLD)
			//调用红黑树转链表的方法
			tab[index] = loHead.untreeify(map);
		else {
			//否则，把红黑树的头节点转移到数组的新节点上(红黑树的根节点一定是链表的头节点)
			//下标 = 原数组下标
			tab[index] = loHead;
			//如果存在高位链表，说明红黑树已经被拆分成两个链表
			if (hiHead != null) // (else is already treeified)
				//构建新的红黑树
				loHead.treeify(tab);
		}
	}
	//如果高位链表首节点不为null，说明有这个链表存在
	if (hiHead != null) {
		如果高位链表的长度<=UNTREEIFY_THRESHOLD=6
		if (hc <= UNTREEIFY_THRESHOLD)
			 //调用红黑树转链表的方法
			tab[index + bit] = hiHead.untreeify(map);
		else {
			//否则，把红黑树的头节点转移到数组的新节点上(红黑树的根节点一定是链表的头节点)
			//下标 = 原数组下标 + 原数组长度
			tab[index + bit] = hiHead;
			//如果存在低位链表，说明红黑树已经被拆分成两个链表
			if (loHead != null)
				//构建新的红黑树
				hiHead.treeify(tab);
		}
	}
}

3）链表和红黑树互相转化的结论：

链表过长了并不一定会转为红黑树，还会考虑扩容；

1）当链表的长度 >= 7 ，且entry数组的长度 < 64 时，此时会扩容，(不转红黑树)。

2）只有当链表的长度 >= 7，且entry数组的长度 >= 64 时，才会将链表转为红黑树。

3）在resize()方法扩容的时候，在将原Node数组迁移到扩容后的新Node数组的时候，如果该Node元素是一个红黑树，则对其进行拆分、然后才迁移到新的Node数组中，

如果拆分之后的子树的数量小于等于6了，则将该子树转回为链表结构；

HashMap中链表与红黑树的互相转化

原文链接：

一，先来看几个变量、常量、静态变量、静态常量：

1）链表与红黑树互相转化的阀值：

2） Map的默认初始化容量以及容量极限：

3）默认负载因子、实际元素数量：

4）table——Entry数组；

5）Map已经修改的次数、下一次扩容的大小、存储负载因子的常量：

5.5）什么是Map已经修改的次数？

二，链表转红黑树：

1）为什么要将链表转为红黑树：

2）链表多长时，会变成红黑树？

结论：

三，看源码：

1）什么时候将链表转化为红黑树？

步骤总结：

2）什么时候将红黑树退化回为链表：

拓展：split()方法完整源码分析：

3）链表和红黑树互相转化的结论：

标签云

近期文章

分类

HashMap中链表与红黑树的互相转化

原文链接：

一， 先来看几个变量、常量、静态变量、静态常量：

1）链表与红黑树互相转化的阀值：

2） Map的默认初始化容量以及容量极限：

3） 默认负载因子、实际元素数量：

4）table——Entry数组；

5）Map已经修改的次数、下一次扩容的大小、存储负载因子的常量：

5.5）什么是Map已经修改的次数？

二，链表转红黑树：

1）为什么要将链表转为红黑树：

2）链表多长时，会变成红黑树？

结论：

三，看源码：

1）什么时候将链表转化为红黑树？

步骤总结：

2）什么时候将红黑树退化回为链表：

拓展：split()方法完整源码分析：

3）链表和红黑树互相转化的结论：

相关文章

一，先来看几个变量、常量、静态变量、静态常量：

3）默认负载因子、实际元素数量：