Java面试重点--HashSet扩容和转成红黑树机制

分手后的思念是犯贱 2024-04-02 03:14 72阅读 0赞

### 建议看完这两篇文章，再观看此文 ###

### [Java面试重点–HashSet底层代码全面解析（1）][Java_HashSet_1] ###

### [Java面试重点–HashSet底层代码全面解析（2）][Java_HashSet_2] ###

### 先说明HashSet扩容和转成红黑树机制结论 ###

##### 1、HashSet扩容结论 #####

HashSet底层是Hashmap即数组+链表，添加元素时，table数组扩容为16，加载因子为0.75，所以临界值为16 \* 0.75 = 12，意思是添加12个元素后，table数组将继续扩容至原来的2倍即32，临界值也会变为32 \* 0.75 = 24，以此类推。

##### 2、HashSet转成红黑树机制结论 #####

当一条链表的元素得到8个之后，并且table数组的大小达到64，链表就转成红黑树，如果table数组未到64，table数组将扩容至原来的2倍，直至大小达到64链表转成红黑树为止。

### 分析HashSet扩容底层源码 ###

##### 举一个例子：在HashSet集合中添加20个元素 #####

import java.util.HashSet;
    
    public class HashSet_ {
        
        public static void main(String[] args) {
        
            HashSet hashSet = new HashSet();
            for (int i = 1; i <= 20; i++) {
        
                hashSet.add(i);
            }
            System.out.println(hashSet);
        }
    }

###### 添加第一个元素 ######

1、Debug进入add方法

public boolean add(E e) {
        
            return map.put(e, PRESENT)==null;
        }

2、进入put方法

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

3、进入putVal方法

hash表示 key 对应的 hash 值，key就是传入的1，value就是PRESENT是一个常量。  
table 就是 HashMap 底层数组，类型是 Node\[\]，因为还没有存放元素，所以是null，满足if条件，执行 n = (tab = resize()).length;  
4、进入resize()方法：

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) {
        
            if (oldCap >= MAXIMUM_CAPACITY) {
        
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
            }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {
                       // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        threshold = newThr;
        @SuppressWarnings({
        "rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        return newTab;
    }

将table赋给oldTab，所以oldTab = null，oldCap = 0，threshold表示临界值为table数组长度的0.75倍，因为table数组长度为0，所以threshold = 0，oldThr = 0，所以会进入到else语句。  
DEFAULT\_INITIAL\_CAPACITY = 16是一个常量，所以 newCap = 16，表示table数组的新容量=16，DEFAULT\_LOAD\_FACTOR = 0.75是一个常量，表示加载因子，所以newThr = （int）(16 \* 0.75) = 12，所以 threshold = 12，然后新建了一个长度16的Node数组 newTab，所以table就变成了一个长度16的Node数组，返回newTab。  
小结：resize()方法是一个数组扩容方法，如果当前 table 是 null, 或者 大小=0，就第一次扩容到 16 个空间，如果已经加入的元素占数组空间的0.75倍时，数组就准备扩容。

###### 添加第13个元素 ######

1、进入putVal方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
        
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            ++modCount;
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }

\++size = 13， threshold = 12,满足 if (++size > threshold)，所以执行resize()方法。  
2、进入resize()方法：

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) {
        
                if (oldCap >= MAXIMUM_CAPACITY) {
        
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    newThr = oldThr << 1; // double threshold
            }
            threshold = newThr;
            @SuppressWarnings({
        "rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
            table = newTab;

table不为空，空间=16，所以oldTab也不为空，oldTab.length = oldCap = 16。threshold = 12，所以oldThr = 12。  
所以满足if (oldCap > 0)，但不满足if (oldCap >= MAXIMUM\_CAPACITY)，因为MAXIMUM\_CAPACITY = 1073741824。  
满足else if ((newCap = oldCap << 1) < MAXIMUM\_CAPACITY && oldCap >= DEFAULT\_INITIAL\_CAPACITY)，因为DEFAULT\_INITIAL\_CAPACITY = 16。  
oldCap << 1表示oldCap左移一位，相当于oldCap \* 2 = 32 =newCap，newThr = oldThr << 1 = 24。  
threshold临界值 = 24，newTab数组空间变为32，table数组空间变为32。

##### 举一个例子：在HashSet集合中添加20个hash值相同的元素 #####

import java.util.HashSet;
    
    public class HashSet_ {
        
        public static void main(String[] args) {
        
            HashSet hashSet = new HashSet();
            for (int i = 1; i <= 20; i++) {
        
                hashSet.add(new B(i));
            }
            System.out.println(hashSet);
        }
    }
    class B {
        
        private int n;
    
        public B(int n) {
        
            this.n = n;
        }
    
        @Override
        public int hashCode() {
        
            return 200;
        }
    }

因为hash值相同，所以可以加在同一链表上。  
![80bcc61e6f27431c941b8eb35f6362d2.png_pic_center][]size = 8，说明在同一链表上添加了8个元素，table表大小=16，不符合转成红黑树条件。  
![6668a9c4baf14b189e4a519e27b1338a.png_pic_center][]在链表中再添加一个元素，table数组将扩容至原来的2倍 = 32，不符合转成红黑树条件。  
![d1225789715a4bbea9f8edd455c439df.png_pic_center][]在链表中再添加一个元素，table数组将扩容至原来的2倍 = 64，符合转成红黑树条件。  
![c78c69f3041c4b4b8165aa42a7ff52e0.png_pic_center][]我们可以发现元素已经从Node类型变成了TreeNode类型，即转成了红黑树。

[Java_HashSet_1]: https://blog.csdn.net/programmerchiu/article/details/126907825?spm=1001.2014.3001.5502
[Java_HashSet_2]: https://blog.csdn.net/programmerchiu/article/details/127028496?spm=1001.2014.3001.5502
[80bcc61e6f27431c941b8eb35f6362d2.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/02/b2bb7272f2a74c9bb4a2f81b1546d5e2.png
[6668a9c4baf14b189e4a519e27b1338a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/02/2aceeadda24e4039ae0028d5a57aa2ba.png
[d1225789715a4bbea9f8edd455c439df.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/02/d50071c0042c496a8fbf49bac8389a0d.png
[c78c69f3041c4b4b8165aa42a7ff52e0.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/02/f0495ad5b39b422ebe0d49fb08c910cf.png