【面试基础】HashMap在什么条件触发链表变成红黑树？

面试官：我看简历里有写掌握常用的数据结构，hashMap肯定天天打交道吧？HashMap在什么条件触发链表变成红黑树？

我：当数据size超过64个的时候吧。
面试官：哦？这个说法不太准确。。。

HashMap天天打交道，可是我们搬砖人只把他当成工具，不知道一些细节，以及他怎么保证查找添加删除效率的，是不是有点对不起他，那我们今天就来啃啃这个HashMap以及红黑树，让你自信面对红黑树，再也不谈”红黑树“就大脑宕机，超出范围了。
红黑树很复杂本文讲不完，可以在这里看我写的《【全网最详细图文讲解】❤ 彻底搞懂你 @红黑树》

如果你现在已经打开IDEA,建议一起打开源码，没有也没关系，先看懂图，建议收藏后面在自己对照源码再次领悟。

一、
HashMap 是 Java 中的一个非常重要的数据结构，它实现了 Map<K,V>接口，该结构基于哈希表，主要用于存储键值对。
HashMap 的重要特性包括：

无序性：HashMap 不保证顺序，特别是不保证顺序会随着时间的推移保持一致。
键唯一性：每个键最多只能映射到一个值。
时间复杂度：理想情况下，HashMap 提供对插入、删除和定位元素的常数时间性能（O(1)），非理想的情况下，尤其是发生大量哈希冲突时，比如哈希函数的设计不良，导致大量的键映射到相同的哈希桶中，这时候HashMap的性能在链表可以退化为 O(n)，红黑树为O(log n)。
空值：HashMap 允许存储 NULL 值作为键或者值。

HashMap 的内部实现是一个动态数组，数组的每个槽位又是一个链表或者红黑树（当链表长度过长时会转化为红黑树以优化搜索性能，变成红黑树实际情况数据可能的到以及亿上级别，普通客户端使用很少出现）。当发生哈希碰撞，即不同的键被哈希到同一个槽位时，键值对会以链表的形式存储在该槽位上。

HashMap 的性能和那些有关？

哈希函数
哈希函数的质量直接影响到键值对在HashMap中的分布。一个好的哈希函数应该能够将键均匀地分布在不同的哈希桶中，减少冲突。如果哈希函数导致许多键聚集在相同的桶中，性能会显著降低。
初始容量和负载因子
初始容量是HashMap创建时的哈希表大小。
负载因子是哈希表在其容量自动增加之前可以达到多满的一种度量。当哈希表中的条目数超过负载因子与当前容量的乘积时，哈希表会进行扩容。
这两个参数决定了哈希表需要进行扩容的频率。频繁的扩容会影响性能，因为它涉及到重新计算现有键的哈希值并将它们重新分配到新的桶中。

源码分析

1. Node<K,V>，TreeNode<K,V>节点结构

HashMap中使用Node<K,V>[] table 来存放map<K,V>键值对。

Node<K,V>，TreeNode<K,V>的声明如下：

java复制代码   // 创建一个Node
   Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
       return new Node<>(hash, key, value, next);
   }

Node<K,V>表示table中的每个节点，每个节点包含hash,key,value,next。每个table[i]是一个链表的头，也就是相同hash值的元素都在一个hash bins中,next可以看出此时属于单链表结构。

java复制代码   // 创建一个TreeNode
   TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
       return new TreeNode<>(hash, key, value, next);
   }

TreeNode中多出parent,left,right,prev,red字段, 这个prev字段通常用于保持一个部分的双向链表，以便在删除操作中方便地找到并断开与前一个节点的连接。这种做法不是红黑树数据结构的标准部分，但它可以用于优化某些操作。在删除一个节点时，必须重构树以保持红黑树的性质。这个prev字段的存在可以帮助在不违背红黑性质的情况下，更快地修复树的链接，因为它为节点提供了一种返回到前一个节点的直接方式，从而减少了在删除操作中需要执行的比较和旋转次数。

TreeNode继承LinkedHashMapEntry,其实最终是Node<K,V> ,LinkedHashMap是直接继承HashMap, TreeNode继承LinkedHashMapEntry 是为了更好兼容LinkedHashMap

2. 初始化

hashMap初始化构造方法有4个，如下：

java复制代码   //可以自定义初始容量initialCapacity和加载因子loadFactor
    public HashMap(int initialCapacity, float loadFactor) {
        ...                                     loadFactor);
        this.loadFactor = loadFactor;
        //初始化扩容阀值，此时不会更具initialCapacity实例化table的，此时table的为空。
        this.threshold = tableSizeFor(initialCapacity);
    }
    //默认加载因子loadFactor，DEFAULT_LOAD_FACTOR = 0.75
    //值0.75是一个在时间和空间成本上取得较好平衡的经验值。它是工程领域基于大量实验和实践得出的结果，对大多数情况来说提供了良好的性能
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    //无参构造，此时
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; 
    }
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    } 
    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {//evict,指明是否要替换已有的映射
        int s = m.size();
        if (s > 0) {
            //如果当前table为空，重新计算threshold
            if (table == null) { // pre-size
                //通过当前的装载因子来除，得到了在保持装载因子不变的情况下，理论上所需要的桶(bucket)数量,也就是table数组的大小
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                if (t > threshold)//如果t大于当前的threshold值，重新设置threshold
                    threshold = tableSizeFor(t);//更具容量重新计算
            }
            else if (s > threshold)
                resize();//扩容
            //循环追加value    
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, false, evict);
            }
        }
    }
    //返回大于等于给定目标容量的最小2的n次方的数
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

DEFAULT_LOAD_FACTOR值0.75是一个在时间和空间成本上取得较好平衡的经验值。它是工程领域基于大量实验和实践得出的结果，对大多数情况来说提供了良好的性能
tableSizeFor返回大于等于给定目标容量的最小2的n次方的数,算法很巧。对n （cap-1）无符号右移1,2,4,8,16位,得到一个所有位均为1的数，举例：

java复制代码{
    int n = 16 - 1; // n = 15, 即二进制的 0000 1111

    n |= n >>> 1;   // n = 0000 1111 | 0000 0111 = 0000 1111
    n |= n >>> 2;   // n = 0000 1111 | 0000 0011 = 0000 1111
    n |= n >>> 4;   // n = 0000 1111 | 0000 0000 = 0000 1111
    n |= n >>> 8;   // 对于一个int类型，8位和16位的移动不会改变值，因为数字已经足够大
    n |= n >>> 16;  // 确保覆盖所有可能的1位

    return n + 1;   // n = 15 + 1 = 16
}

{
   int n = 18 - 1; // n = 17, 即二进制的 0001 0001

    n |= n >>> 1;   // n = 0001 0001 | 0000 1000 = 0001 1001
    n |= n >>> 2;   // n = 0001 1001 | 0000 0110 = 0001 1111
    n |= n >>> 4;   // n = 0001 1111 | 0000 0001 = 0001 1111
    n |= n >>> 8;   // n = 0001 1111 | 0000 0000 = 0001 1111
    n |= n >>> 16;  // n = 0001 1111 | 0000 0000 = 0001 1111

    return n + 1;   // n = 31 + 1 = 32  
}

3. hash函数

在上面我们已经看到putMapEntries调用的方法putVal来添加元素：

1	java复制代码 putVal(hash(key), key, value, false, evict);

可以看到putVal中对于新增的节点，使用newNode方法（可见下面添加源码），其中hash(key) 就是计算key的hash值的哈希函数。

java复制代码//静态方法，
static final int hash(Object key) {
    int h;
    //(h = key.hashCode()) ^ (h >>> 16) 使用  key.hashCode()计算h,h 与 （h >>> 16 ）异或运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

第一步：h = key.hashCode();h是一个4个字节的int,假如此时h = 0x98438919

第二步：h >>> 16 ;这个是将h无符号右移，得到 hr = 0x00009843

第三步：h ^ hr;异或操作，return 0x9843115a

为了避免在哈希表中出现冲突，这个方法通过将哈希值的高位部分与低位部分进行异或（XOR）运算来扩散影响，以此增加低位的随机性，因为高位的信息通常不会参与到哈希表索引计算中，所以需要将低位异或，增加哈希值的均匀性。

4. 添加

添加方法源码如下：

java复制代码 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //如果当前为空，则进行扩容，即初始化table大小
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;

        //按照 (n - 1) & hash 来寻找下标，n为当前table的大小，可以理解为对hash 的（n-1）取模。
        //如果此时对应下标为空，则直接添加。
        if ((p = tab[i = (n - 1) & hash]) == 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))))
                e = p; // //如果k值已经存在，并且相等,后面根据onlyIfAbsent覆盖原来的值。
            else if (p instanceof TreeNode)
            //p为当前相同hash值的链表第一个，如果当前已经是TreeNode，根据红黑树结构添加节点，后面将红黑树在细讲
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                //否则轮询p链表，
                for (int binCount = 0; ; ++binCount) {
                    //到链表结尾，也没有相同的key值，就添加到链尾
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //!!!!!!!!!!
                        //添加完了，再次判断 当前p链表的节点数是不是大于等于8（TREEIFY_THRESHOLD = 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;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        //添加成功，size增加一个，并判断是否大于threshold阈值，如果大于就有触发一次扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
     //将一个hash bin（哈希桶）中的节点 尝试变成红黑树结构
     final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        //!!!!!!
        // MIN_TREEIFY_CAPACITY = 64
        //如果tab.length < MIN_TREEIFY_CAPACITY ,此时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 {
                //将节点变成TreeNode
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;//hd 链表头指针
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);

            if ((tab[index] = hd) != null)
            //如果大于64，就将hd有链表结构整理变成红黑树结构
                hd.treeify(tab);
        }
    }

添加元素的过程包含hash bin(哈希桶)的树化过程，变成红黑树的触发条件是当一个hash bin(哈希桶)的链表程度大于8，并且当前table的length是大于64 ，才开始将此此时的hash bin(哈希桶)由链表结构变成红黑树结构。

5. 扩容

扩容过程也很重要，因为一次扩容将会触发hash表的重新移位，方法源码中如下

java复制代码final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            //oldCap大于0，之前触发过resize,table已经有值了
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                     //newCap 变成原来oldCap（ table length）的两倍，如果此时oldCap大于初始容量（16）就将新的扩容阀值变成之前两倍。
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // 如果oldCap= 0，但是 oldThr大于0 ，那么直接将新的容量变成oldThr
            newCap = oldThr;
        else { //都等于0的时候，直接赋值默认初始容量，
            newCap = DEFAULT_INITIAL_CAPACITY;
            // 新的threshold位 16 * 0.75 = 12
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 
        }
        if (newThr == 0) { 
            //前面 如果oldCap= 0，但是 oldThr大于0，已经设置了newCap
            float ft = (float)newCap * loadFactor;
            // 重新设置newThr = newCap * loadFactor
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }

        //设置新的 table，threshold
        threshold = newThr;
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        
        //这里判断是需要移位，将老的table中hash值，按照新的长度重新安排索引
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)//如果老的hash bin 只有链表头，重新赋值到新的索引
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                    //如果是树的结构移位，split方法原理和下面链表移位类似
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else {
                        //不是树的结构，还是移位该hash bin 到新的索引。这里的算法也很巧妙，我们后面举例分析
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        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;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

扩容过程最重要的部分就是移位哈希桶到新的table索引的过程。一开始很难理解loHead，loTail，hiHead，hiTail。我们需要明确前提条件，当前哈希桶中的所有元素key的hash值与原本 (oldcap-1) 取模是是一样的，但是和当前(newcap-1)取模可能一样也可能不一样，因为cap都是2的幂次方。所以移位要么还在原来的索引，要么在新的索引。所以loHead 可以理解为将要在原本索引index的表头指针，也就是其他博主说的低位链表表头，hiHead同理是新的索引的表头，即高位表头指针。

还有一个比较难理解的点是为什么要使用(e.hash & oldCap) == 0 来区分loHead，hiHead。我们举例：

yaml复制代码假设当前oldcape容量为 16,newcap为32
1.如果当前hash 低位字节：0000 1011 
0000 1011 & （16-1）
0000 1011 & 0000 1111 =  0000 1011 （11 十进制）
0000 1011 & （32-1）
0000 1011 & 0001 1111 =  0000 1011 （11 十进制）
此时hash值 对应在容量 16 和 32 都是下标索引为11
此时 0000 1011 & （16）
0000 1011 &  0001 0000 = 0000 0000 （0 十进制）
说明如果直接和 oldcap 与运算为0 ，那么下标不变。

2.如果我们换一个高位的hash值：1011 1011 
1011 1011 & （16-1）
1011 1011 & 0000 1111 =  0000 1011 （11 十进制）
1011 1011 & （32-1）
1011 1011 & 0001 1111 =  0001 1011 （27 十进制）

此时
此时 1011 1011 & （16）
1011 1011 &  0001 0000 = 0001 0000 （16 十进制）
直接和 oldcap 与运算为16不为0 ，
那么下标就是 11(原本下标 ) +  16(oldcap) = 27

举例中的两个hash值老的oldcap中，经过 hash &(oldcap -1) 都是相同索引，在同一个链表，经过这样操作以后，这两个元素被分到不同的hash桶中了。（此处给如此巧妙的算法掌声(^▽^)👏👏👏👏🏻）

6. HashMap 序列化

HashMap是通过实现如下方法直接将元素数量(size), key, value等写入到了ObjectOutputStream中，实现的定制化的序列化和反序列化。在Serializable接口中有关于这种做法的说明。

java复制代码 private void writeObject(java.io.ObjectOutputStream out)
        throws IOException
private void readObject(java.io.ObjectInputStream in)
         throws IOException, ClassNotFoundException;

而hashmap重写 writeObject， readObject，如下：

java复制代码    final int capacity() {
        return (table != null) ? table.length :
            (threshold > 0) ? threshold :
            DEFAULT_INITIAL_CAPACITY;
    }

    private void writeObject(java.io.ObjectOutputStream s)
        throws IOException {
        int buckets = capacity(); 
        s.defaultWriteObject();
        s.writeInt(buckets);//保存 capacity
        s.writeInt(size);// 保存元素个数
        internalWriteEntries(s);//轮询保存 key,value 对象
    }
    void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
        Node<K,V>[] tab;
        if (size > 0 && (tab = table) != null) {
            for (int i = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                    s.writeObject(e.key);
                    s.writeObject(e.value);
                }
            }
        }
    } 
    private void readObject(java.io.ObjectInputStream s)
        throws IOException, ClassNotFoundException {
        // Read in the threshold (ignored), loadfactor, and any hidden stuff
        s.defaultReadObject();
        reinitialize();
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new InvalidObjectException("Illegal load factor: " +
                                             loadFactor);
        s.readInt();                // Read and ignore number of buckets
        int mappings = s.readInt(); // Read number of mappings (size)
        if (mappings > 0) { // (if zero, use defaults)
            ...略//（计算cap的值）
            Node<K,V>[] tab = (Node<K,V>[])new Node[cap];
            table = tab;
            // Read the keys and values, and put the mappings in the HashMap
            for (int i = 0; i < mappings; i++) { 
                    K key = (K) s.readObject(); 
                    V value = (V) s.readObject();
                putVal(hash(key), key, value, false, false);
            }
        }
    }

后面查询和删除和上边的关键之处差不多,本文就不赘述了。

总结

把hashmap的结果简单的复习了一遍，我们对源码分析部分做一个总结，下面以经常被问到hashmap相关问题的方式总结一下，这个答案都在上文源码分析部分。

Q:HashMap 的初始容量和负载因子是什么？

初始容量是创建 HashMap 时的数组大小，默认是 16。负载因子用于计算初始容量的扩容阈值，扩容阈值用来控制当前衡量 HashMap 在其容量自动增加之前可以有多满，负载因子默认是 0.75。负载因子越高，阈值越高，出发扩容之前存储元素越多，但对于哈希表来说，空间利用率提高了，查询速度可能会降低。

Q: 何时需要扩容呢？

A: 在使用put方法添加键值对的时候，首先会判断table表是否为空，是的话resize一次初始化table大小，每次完成了put操作添加成功（不是替换的情况）以后，都判断一下++size是否大于threshold,如果大于则进行扩容。

Q: 那么threshold又是如何得到的呢？

A: 旧的table的长度大于0的时候，新的扩容和阈值都是原来的2倍，旧的table为空的时候，默认情况下简单来讲threshold = length * loadfactor(默认为0.75)。

Q: 扩容时具体做什么呢？

A: 首先计算出新的数组长度和新的threshold(阈值). 简单来讲，旧的table不为空，新的hash table的length(newCap) 是原来的2倍（位运算左移一位），新的threshold也为原来的2倍。创建新的Node数组赋值给当前table，将原来数组中的元素安装hash &(newcap -1)重新映射到新的数组索引中。

Q:HashMap在什么条件触发链表变成红黑树？

A:添加元素的过程包含hash bin(哈希桶)的树化过程，变成红黑树的触发条件是当一个hash bin(哈希桶)的链表程度大于8，并且当前table的length是大于64 ，才开始将此此时的hash bin(哈希桶)由链表结构变成红黑树结构。

为什么要将单链表变成红黑树呢，那我们就来分析分析红黑树的特点。这个部分我单独一篇文章来讲。

Q:如何判断两个键 k1 和 k2 是相同的？

A: 在源码中判断key是否相等使用p.hash == hash && （(k = p.key) == key || (key != null && key.equals(k))） 那么也就是 k1.equals(k2) 为 true 并且 k1.hashCode() == k2.hashCode()，那么可以判断两个键是相同的，这两个条件都需要满足。

Q：HashMap类是实现了Serializable接口的，那么为何其中的table, entrySet变量都标为transient呢？

A：我们知道，table数组中元素分布的下标位置是根据元素中key的hash进行散列运算得到的，而hash运算是native的，不同平台得到的结果可能是不相同的。举一个简单的例子，假设我们在目前的平台有键值对 key1-value1,计算出key1的hash为1，计算后存在table数组中下标为1的地方，假设table被序列化了，并传输到了另外的平台，并反序列化为了原来的HashMap，key1-value1仍然存在下标1的位置，当在这个平台运行get(“key1”)的时候，可能计算出key1的hash为2，就有可能到下标为2的地方去找该元素，这样就出错了。

其他相关问题

Q:HashMap 和 Hashtable 的区别是什么？

A:哈希表（Hashtable）是线程安全的，它的每个方法基本上都是同步的，而 HashMap 不是线程安全的。此外，HashMap 允许使用一个空键和多个空值，而 Hashtable 不允许空键或空值。

Q:什么时候使用 TreeMap 而不是 HashMap？
当你需要保持键的顺序时，应该使用 TreeMap。TreeMap 实现了 SortedMap 接口，可以确保键处于排序状态，但是它的操作比 HashMap 的平均复杂度要高。

Q:如何自定义类作为 HashMap 的键？

A:如果要使用自定义对象作为键，需要重写 equals() 和 hashCode() 方法。这样才能保证当对象的逻辑内容相同的时候，它们的哈希码也是相同的。

Q:在并发环境下，如何安全地使用 HashMap？

A:在并发环境下，可以使用 Collections.synchronizedMap(new HashMap<…>()) 或者 ConcurrentHashMap 来实现线程安全的哈希映射。

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有