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

最新推荐文章于 2025-03-22 18:33:32 发布

邱崇源

最新推荐文章于 2025-03-22 18:33:32 发布

阅读量2k

点赞数 10

分类专栏： Java面试重点文章标签： java 面试数据结构

本文链接：https://blog.csdn.net/programmerchiu/article/details/127112520

版权

本文详细解析了Java HashSet的扩容机制和何时转为红黑树。当元素数量达到12时，HashSet会扩容至原来的两倍，如16变为32。若链表元素达到8个且数组大小达到64，将转为红黑树。通过实例分析了扩容和转换过程。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

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

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

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方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,<

最低0.47元/天解锁文章