JDK1.8中HashMap在出现hash碰撞时链表长度超过8一定会变成红黑树?

朱雀 2023-07-06 14:49 16阅读 0赞

转载：[https://blog.csdn.net/it\_qingfengzhuimeng/article/details/100041994][https_blog.csdn.net_it_qingfengzhuimeng_article_details_100041994]  
原创清风追梦enjoy 最后发布于2019-08-23 16:50:59 阅读数 699  收藏  
展开  
JDK1.8中HashMap在出现hash碰撞时链表长度超过8就一定会变成红黑树吗

答案是:否.

实际上转换红黑树有个大前提,就是当前hash table的长度也就是HashMap的capacity(不是size)不能小于64.小于64就只是做个扩容.

看HashMap源码

核心代码如下(大体上调用关系就是 put->putVal->treeifyBin):

put()

public V put(K key, V value) \{  
    return putVal(hash(key), key, value, false, true);  
\}  
putVal()

/\*\*  
 \* 实现了 Map.put 以及其它相关的方法.  
 \*  
 \* @param hash key的hash值  
 \* @param key the key  
 \* @param value the value to put  
 \* @param onlyIfAbsent true:在key相同时,不会覆盖原有的value  
 \* @param evict if false, the table is in creation mode.  
 \* @return previous value, or null if none  
 \*/  
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) \{  
    // hash table 对象   
   Node<K,V>\[\] tab;  
    // 下标i对应的Node对象  
    Node<K,V> p;  
    // hash table的长度   
    int n;   
    // key在hash table中存放的索引下标  
    int i;  
    // 获取hash table的长度  
   if ((tab = table) == null || (n = tab.length) == 0)\{  
        n = (tab = resize()).length;  
    \}  
      
    // i = (n - 1) & hash  根据hash值计算key在hash table中的位置  
    // 那么根据这行代码可以得到个结论:如果key为null(此时对应的hash为0),那么一定是在下标为0的位置  
    if ((p = tab\[i = (n - 1) & hash\]) == null)\{  
        // 如果下标i的位置是null(尚未有元素),那么直接放入  
        tab\[i\] = newNode(hash, key, value, null);  
    \} else \{  
        //   
        Node<K,V> e; K k;  
        if ( p.hash == hash  
             && ((k = p.key) == key || (key != null && key.equals(k)))  
        )\{  
            // 如果p的key和输入的key相等  
            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的目的是找到位置i上的链表/红黑树的最后一个Node元素  
                if ((e = p.next) == null) \{  
                    p.next = newNode(hash, key, value, null);  
                    // TREEIFY\_THRESHOLD = 8  
                    if (binCount >= TREEIFY\_THRESHOLD - 1) \{  
                        // 转换为红黑树(如果hash table的长度不到MIN\_TREEIFY\_CAPACITY即64,那么只是做扩容处理,并不会转换为红黑树)  
                        treeifyBin(tab, hash);  
                    \}// -1 for 1st  
                    break;  
                \}  
                // 如果链表上已有相同key的Node,那么直接返回此Node  
                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;  
\}  
treeifyBin()

/\*\*  
 \* 如果hash table的长度大于64,则将指定位置上的所有节点转换为TreeNode;  
 \* 否则只对hash table进行扩容.  
 \*/  
final void treeifyBin(Node<K,V>\[\] tab, int hash) \{  
    int n, index; Node<K,V> e;  
    // MIN\_TREEIFY\_CAPACITY = 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 \{  
            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);//转换为红黑树  
    \}  
\}  
\---------------------------------------------------

划重点：

putVal()

static final int TREEIFY\_THRESHOLD = 8;

if ((e = p.next) == null) \{

p.next = newNode(hash, key, value, null);

if (binCount >= TREEIFY\_THRESHOLD - 1) // -1 for 1st

treeifyBin(tab, hash);

break;

treeifyBin()

static final int MIN\_TREEIFY\_CAPACITY = 64;

if (tab == null || (n = tab.length) < MIN\_TREEIFY\_CAPACITY)

resize();  
————————————————  
版权声明：本文为CSDN博主「清风追梦enjoy」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。  
原文链接：https://blog.csdn.net/it\_qingfengzhuimeng/article/details/100041994

[https_blog.csdn.net_it_qingfengzhuimeng_article_details_100041994]: https://blog.csdn.net/it_qingfengzhuimeng/article/details/100041994