HashMap最小树形化阈值MIN_TREEIFY_CAPACITY

小灰灰 2024-04-20 08:23 38阅读 0赞

HashMap的几个关键参数很重要，大家非常熟悉capacity loadFactory threshold table  size 以及下列jdk1.8后特有的红黑树相关参数。其中，最小树形化参数MIN\_TREEIFY\_THRESHOLD 的作用到底是什么呢？

/\*\*

\* 与红黑树相关的参数

\*/

// 1. 桶的树化阈值：即 链表转成红黑树的阈值，在存储数据时，当链表长度 > 该值时，则将链表转换成红黑树

static final int TREEIFY\_THRESHOLD = 8;

// 2. 桶的链表还原阈值：即 红黑树转为链表的阈值，当在扩容（resize（））时（此时HashMap的数据存储位置会重新计算），在重新计算存储位置后，当原有的红黑树内数量 < 6时，则将 红黑树转换成链表

static final int UNTREEIFY\_THRESHOLD = 6;

// 3. 最小树形化容量阈值：即 当哈希表中的容量 > 该值时，才允许树形化链表 （即 将链表 转换成红黑树）

// 否则，若桶内元素太多时，则直接扩容，而不是树形化

// 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 \* TREEIFY\_THRESHOLD

static final int MIN\_TREEIFY\_CAPACITY = 64;

在我们熟悉的

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,  
               boolean evict)  
方法中并没有出现最小树形化参数，并且在链表转成红黑树的判断语句前并没有相关判断，顿时头痛。仔细再核对一遍putVal（）中的判断语句

for (int binCount = 0; ; ++binCount) \{  
    if ((e = p.next) == null) \{  
        p.next = newNode(hash, key, value, null);  
          
// 链表长度达到8，进行链表转红黑树  
        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;  
\}  
final void treeifyBin(Node<K,V>\[\] tab, int hash) \{  
    int n, index; Node<K,V> e;  
//判断capacity是否小于最小树形化容量阈值  
    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);  
    \}  
\}  
原来MIN\_TREEIFY\_CAPACITY出现在了treeifyBin()中！这样做会让逻辑更清楚，避免了在treeifyBin()前判断capacity与MIN\_TREEIFY\_CAPACITY比较的代码量过大。