2024年4月3日发(作者：)

hashmap扩容 树化条件

HashMap扩容

HashMap是一种基于哈希表的数据结构，用于存储键值对。当

HashMap中的元素达到一定数量时，需要进行扩容以提高查找效率。

HashMap的扩容机制遵循以下规则：

负载因子（Load Factor）：当HashMap中元素的数量与桶数

组的大小之比达到预设的负载因子阈值时，触发扩容。默认情况下，

负载因子阈值为0.75。

目标容量（Target Capacity）：扩容后HashMap的新桶数组

大小为当前桶数组大小的两倍，即`2 当前容量`。

重新哈希（Rehashing）：扩容后，将所有元素重新哈希到新

的桶数组中。

树化条件

在某些情况下，HashMap会将链式法桶转换为红黑树，这称为

树化。树化的条件是：

桶中的元素数量超过阈值：如果桶中的元素数量超过预设的阈

值，将其转换为红黑树。默认情况下，阈值为8。

哈希冲突过多：如果桶中哈希冲突的元素数量超过预设的阈值，

将其转换为红黑树。默认情况下，阈值为6。

树化后，桶中的元素将以红黑树的形式存储。红黑树是一种平

衡二叉查找树，具有高效的查找和插入性能。

扩容和树化的优缺点

扩容：扩容可以提高HashMap的查找效率，减少哈希冲突。但

扩容需要重新哈希所有元素，这会降低HashMap的插入和删除性能。

树化：树化可以进一步提高桶中元素的查找效率，但会增加桶

中的存储空间开销。

HashMap的扩容和树化机制旨在平衡性能和空间效率。通过适

当的阈值设置，可以优化HashMap在不同场景下的表现。