MIN_TREEIFY_CAPACITY不能理解

Question

当桶中节点大于TREEIFY_THRESHOLD时，会由链表结构转换为红黑树结构，当桶中节点小于UNTREEIFY_THRESHOLD时会由红黑树结构转换为链表结构，那么MIN_TREEIFY_CAPACITY是个什么含义呢？看了源码和网上博文，得到的是，如果桶中节点大于TREEIFY_THRESHOLD，但是整个哈希表的容量小于MIN_TREEIFY_CAPACITY时，只会扩容而不会变成红黑树，只有当大于了MIN_TREEIFY_CAPACITY并且大于TREEIFY_THRESHOLD才会变成树结构。。。那么之前的大于TREEIFY_THRESHOLD是在干嘛？理解起来总感觉怪怪的，多半是错了！希望老师或者其他有缘人能解答一下，大于TREEIFY_THRESHOLD时，存储的到底是什么？链表还是红黑树？到底什么时候会出现红黑树？

Answer 1

海与千巷 2020-03-27 22:59:32

链表长度大于TREEIFY_THRESHOLD且数组长度大于MIN_TREEIFY_CAPACITY，链表转化为红黑树

链表长度大于TREEIFY_THRESHOLD（且数组长度不大于MIN_TREEIFY_CAPACITY），进行扩容，还是链表

• 翔仔 #1

  确实是这样的，感谢大神的分享

• 提问者 MySweeties #2

  谢谢大佬

• noob_programmer 回复 翔仔 #3

  老师好！请问为什么在treeifyBin()的时候要判断数组的长度是否小于64，小于64就扩容啊，对链表进行树化和数组长度有什么关系啊。。

点开查看后面1条评论

Answer 2

海与千巷 2020-03-27 23:19:07

当执行put方法时，若某一个桶中的链表长度达到TREEIFY_THRESHOLD(8)时，尝试调用树化方法，树化方法中会再次判断数组长度(即桶的数量)是否大于MIN_TREEIFY_CAPACITY（64），大于则将链表变为红黑树，否则不树化(只进行普通扩容，即桶的数量加倍)