没有网站可以做落地页,php做不了大型网站吗,室内设计效果图素材,科技型中小企业服务网在Java的HashMap实现中#xff0c;链表转换为红黑树的条件包括链表长度和HashMap的容量#xff08;桶数组大小#xff09;。具体规则如下#xff1a;
链表长度阈值#xff1a;当单个桶中的链表长度达到8时#xff0c;该链表会被转换为红黑树。最小树化容量#xff1a;H…在Java的HashMap实现中链表转换为红黑树的条件包括链表长度和HashMap的容量桶数组大小。具体规则如下
链表长度阈值当单个桶中的链表长度达到8时该链表会被转换为红黑树。最小树化容量HashMap的总容量桶数组大小必须至少为64。如果容量小于64即使链表长度达到8也不会进行树化而是会选择扩容。
基于这些规则分别研究转换情况
一、链表长度超过 8数组大小小于 64
如果链表长度超过了长度阈值 8。如果数组大小等于16小于最小树化容量64。
在这种情况下即使链表长度超过了8由于总容量小于64链表不会转为红黑树而是会进行扩容操作。
代码示例
下面是一个示例代码展示当链表长度等于9且数组大小等于16时HashMap会如何处理
import java.lang.reflect.Field;
import java.util.HashMap;
import java.util.Map;public class HashMapTreeifyExample {public static void main(String[] args) throws Exception {// 初始化容量为16的HashMapMapInteger, String map new HashMap(16);// 插入元素确保某个桶中的链表长度达到9for (int i 0; i 9; i) {map.put(i, value i);}// 通过反射获取HashMap的内部结构Class? mapType map.getClass();Field tableField mapType.getDeclaredField(table);tableField.setAccessible(true);Object[] table (Object[]) tableField.get(map);// 输出当前的容量System.out.println(当前的容量: table.length);// 检查每个桶的元素数量和类型for (Object node : table) {if (node ! null) {Class? nodeType node.getClass();if (nodeType.getSimpleName().equals(TreeNode)) {System.out.println(链表已经转换为红黑树。);} else {System.out.println(仍然是链表节点。);}}}}
}代码解释 初始化容量为16的HashMap 我们创建了一个初始容量为16的HashMap。 插入元素 插入9个元素确保某个桶中的链表长度达到9。 通过反射获取HashMap的内部结构 使用反射技术访问HashMap的内部数组桶数组。 检查桶中的节点类型 遍历桶检查每个桶中的节点是链表节点还是红黑树节点并输出当前容量。
预期结果
因为链表长度为9超过了8但由于容量16小于64HashMap不会将链表转换为红黑树。反而HashMap会选择扩容将容量增加到32然后重新分配所有元素。
结论
在此示例中由于链表长度为9超过了8但HashMap的容量只有16小于64因此不会进行树化操作而是会选择扩容。扩容后所有元素会被重新分配到新的桶数组中。
二、链表长度没有超过 8数组大小大于 64
如果链表长度等于 5没有超过长度阈值 8。如果数组大小等于80大于最小书画容量 64。
链表会在其长度达到 8 时才会转换为红黑树。因此如果链表长度等于 5那么它不会转为红黑树无论数组即HashMap的桶数组大小是多少。
代码示例
下面的代码展示了HashMap在链表长度为5时的行为
import java.lang.reflect.Field;
import java.util.HashMap;
import java.util.Map;public class HashMapTreeifyExample {public static void main(String[] args) throws Exception {MapInteger, String map new HashMap(80); // 初始化容量为80// 插入导致单个桶中链表长度达到5的键值对for (int i 0; i 5; i) {map.put(i, value i);}// 通过反射获取HashMap的内部结构Class? mapType map.getClass();Field tableField mapType.getDeclaredField(table);tableField.setAccessible(true);Object[] table (Object[]) tableField.get(map);// 遍历桶检查是否有红黑树节点for (Object node : table) {if (node ! null) {Class? nodeType node.getClass();if (nodeType.getSimpleName().equals(TreeNode)) {System.out.println(链表已经转换为红黑树。);} else {System.out.println(仍然是链表节点。);}}}}
}代码解释 初始化容量为80的HashMap 我们创建了一个初始容量为80的HashMap。 插入元素 插入5个元素确保某个桶中的链表长度达到5。 通过反射获取HashMap的内部结构 使用反射技术访问HashMap的内部数组桶数组。 检查桶中的节点类型 遍历桶检查每个桶中的节点是链表节点还是红黑树节点并输出当前容量。
预期结果
链表长度为 5 时所有节点仍然是链表节点不会转换为红黑树。
结论
只有当单个桶中的链表长度达到8并且HashMap的容量大于等于64时链表才会转换为红黑树。链表长度为5时不会进行转换。
三、红黑树转换为链表
在HashMap实现中红黑树会在一定条件下转换回链表。这主要是为了在删除元素后保持合适的数据结构以优化性能和空间使用。红黑树转换为链表的条件如下 树形化的红黑树节点数量小于6当红黑树节点的数量减少到6或更少时红黑树会被转换回链表。这是因为在少量节点的情况下链表的插入和删除操作比红黑树更高效。 最小树化容量这是一个辅助条件用于确保只有在HashMap的容量桶数组大小足够大时才会执行链表到红黑树的转换和反转换。默认情况下这个值是64。但是转回链表的主要依据还是节点数量。
代码示例
下面是一个示例代码展示红黑树在元素删除后如何转换回链表
import java.lang.reflect.Field;
import java.util.HashMap;
import java.util.Map;public class HashMapDemoteTreeExample {public static void main(String[] args) throws Exception {// 初始化容量为64的HashMapMapInteger, String map new HashMap(64);// 插入足够多的元素确保某个桶中的链表长度达到8转化为红黑树for (int i 0; i 8; i) {map.put(i, value i);}// 通过反射获取HashMap的内部结构Class? mapType map.getClass();Field tableField mapType.getDeclaredField(table);tableField.setAccessible(true);Object[] table (Object[]) tableField.get(map);// 检查红黑树节点System.out.println(插入元素后检查节点类型);checkAndPrintNodeType(table);// 删除部分元素触发从红黑树到链表的转换map.remove(7);map.remove(6);map.remove(5);// 重新获取HashMap的内部结构table (Object[]) tableField.get(map);// 检查是否已经从红黑树转回链表System.out.println(删除元素后检查节点类型);checkAndPrintNodeType(table);}private static void checkAndPrintNodeType(Object[] table) throws Exception {for (Object node : table) {if (node ! null) {Class? nodeType node.getClass();if (nodeType.getSimpleName().equals(TreeNode)) {System.out.println(红黑树节点。);} else {System.out.println(链表节点。);}}}}
}代码解释 初始化容量为64的HashMap 创建一个初始容量为64的HashMap以确保足够的容量进行树化操作。 插入元素 插入8个元素确保某个桶中的链表长度达到8触发从链表到红黑树的转换。 通过反射获取HashMap的内部结构 使用反射技术访问HashMap的内部数组桶数组。 检查节点类型 在插入元素后检查桶中的节点类型验证红黑树节点的存在。 删除部分元素 删除足够的元素减少红黑树的节点数量到6以下触发从红黑树到链表的转换。 再次检查节点类型 在删除元素后重新检查桶中的节点类型验证红黑树是否转换回链表。
预期结果
在插入8个元素后某些桶中的节点应该会从链表转换为红黑树节点。在删除元素后某些红黑树节点会转换回链表节点。
结论
当HashMap的红黑树节点数量减少到6或以下时红黑树会被转换回链表。这种转换是为了在节点数量较少时优化数据结构的性能和空间使用。
四、数组的扩容
HashMap的扩容是其内部机制之一用于确保在存储大量元素时性能不会显著下降。HashMap通过调整内部数组桶数组的大小来管理其负载因子和冲突的数量。
扩容机制 触发条件 HashMap在插入元素时如果元素数量超过了当前容量乘以负载因子默认值是0.75就会触发扩容操作。例如默认情况下当HashMap的容量为16时如果元素数量超过16 * 0.75 12就会触发扩容。 扩容过程 扩容时HashMap的容量会变为原来的两倍。创建一个新的桶数组新的容量是旧容量的两倍。重新散列rehash所有现有的键值对将它们放入新的桶中。 性能影响 扩容是一个相对昂贵的操作因为它需要重新计算所有键的哈希值并将它们重新插入到新的桶数组中。因此频繁的扩容会影响性能选择合适的初始容量可以减少扩容次数。
代码示例
以下是一个示例代码展示了HashMap在插入元素时如何扩容
import java.lang.reflect.Field;
import java.util.HashMap;
import java.util.Map;public class HashMapResizeExample {public static void main(String[] args) throws Exception {// 初始化容量为16的HashMapMapInteger, String map new HashMap(16);// 插入13个元素触发扩容for (int i 0; i 13; i) {map.put(i, value i);}// 通过反射获取HashMap的内部结构Class? mapType map.getClass();Field tableField mapType.getDeclaredField(table);tableField.setAccessible(true);Object[] table (Object[]) tableField.get(map);// 输出扩容前后的容量System.out.println(扩容后的容量: table.length); // 应该是32// 检查每个桶的元素数量for (int i 0; i table.length; i) {if (table[i] ! null) {System.out.print(桶 i 中的元素: );printBucket(table[i]);System.out.println();}}}// 打印桶中的元素private static void printBucket(Object node) throws Exception {Class? nodeClass node.getClass();Field keyField nodeClass.getDeclaredField(key);Field valueField nodeClass.getDeclaredField(value);Field nextField nodeClass.getDeclaredField(next);keyField.setAccessible(true);valueField.setAccessible(true);nextField.setAccessible(true);while (node ! null) {Object key keyField.get(node);Object value valueField.get(node);System.out.print([ key value ] );node nextField.get(node);}}
}详细解释 初始化 我们初始化一个HashMap初始容量为16。 插入元素 插入13个元素这会超过默认的负载因子0.75所允许的12个元素从而触发扩容。 扩容后的检查 使用反射获取HashMap的内部结构特别是桶数组。输出扩容后的容量应该是32因为容量会翻倍。打印每个桶中的元素验证重新散列的正确性。
可以看到HashMap的扩容机制如何在插入大量元素时调整内部结构以确保高效的性能。
