hashmap扩容步骤

<< `HashMap` 是 Java 集合框架中的重要组成部分之一，用于存储键值对（key-value pairs）。当 `HashMap` 中的数据量超过其容量限制时，就需要进行扩容操作。下面是关于 `HashMap` 扩容机制的具体介绍。 ### HashMap 的扩容过程 1. **初始状态**： - 当创建一个新的 `HashMap` 对象时，默认的初始化容量为 16（即底层数组大小为 16），加载因子默认为 0.75。 - 公式：threshold = 容量 * 加载因子 ```java int threshold = (int)(capacity * loadFactor); ``` 初始阈值为 12 (`16 * 0.75`)，这意味着如果当前元素数量达到或超过该阈值，则触发扩容操作。 2. **扩容时机**： - 每次向 `HashMap` 插入新数据之前都会检查是否满足以下条件： 如果 `size >= threshold` （其中 size 表示实际包含的有效键值对数目），则执行扩容逻辑。 3. **扩容步骤**： - 创建新的更大的底层数组。通常情况下会将原数组长度翻倍，并重新计算 hash 值以分配到新位置上。（假设原来 capacity=16, 新容量变为 32） - 将旧表中的所有条目逐一迁移到新的大数组中去。 4. **迁移过程中可能遇到的问题及处理方式**： - 在 JDK8 及之后版本里优化了链表结构，在大量冲突的情况下使用红黑树替代普通单向链表形式；此外还有其他细节上的改进如 CAS 循环等保证线程安全等问题不再赘述。 ```java import java.util.HashMap; public class Test { public static void main(String[] args) throws Exception{ // 构造一个空的HashMap实例 HashMap<Integer,Integer> map=new HashMap<>(8,(float)0.5); System.out.println("Initial Threshold:"+map.threshold()); for(int i=0;i<9;i++){ if(i==8){ System.out.println("\nBefore putting key "+i+", table is :"); printTable(map.table); //Put will trigger resize here since current entries count reaches to the initial threshold value. map.put(i,i*10); System.out.println("\nAfter Resize operation:"); printTable(map.table); }else { map.put(i,i*10); } } } private static <K,V>void printTable(Entry<K,V>[] tab){ Entry<K,V> e; int idx=0; while(idx <tab.length ){ e=tab[idx++]; if(e!=null){ do{ System.out.printf("[%d]=%s -> ",idx-1,e.value ); e=e.next; }while(e != null ); System.out.print("null\n"); } else{System.out.printf("[%d]=null\n",idx-1);} } } } ``` 上述程序演示了一个自定义的小型测试用例展示如何打印出每次插入前后的内部哈希桶分布情况以及触发重置的过程。需要注意的是这里简化了一些实现细节方便理解原理即可。 ### 解释： - 在上面的例子中我们手动设定了较小的初始容量与较低负载因子从而加快出现扩容现象以便观察效果； - 方法 `printTable()` 展现现有表格布局状况包括每个索引处是否有节点链接形成链条等情况便于追踪整个变化轨迹。 - 第九次调用put()方法的时候因为已经达到预设门限所以开始扩展空间并将已有内容复制过去调整后的位置。

HashMap 是基于哈希表实现的，其底层数据结构是数组和链表（或红黑树）。当 HashMap 中元素数量超过了负载因子（Load Factor）和容量（Capacity）的乘积时，就需要进行扩容。 负载因子是指 HashMap 中元素数量与容量的比值，当元素数量超过负载因子与容量的乘积时，就需要进行扩容。默认情况下，负载因子是 0.75，也就是说，当 HashMap 中元素数量超过 0.75 倍的容量时，就需要扩容。 HashMap 扩容的过程主要涉及以下几个步骤： 1. 创建一个新的数组，大小为原数组的两倍； 2. 将原数组中的元素逐个重新计算哈希值，并放入新数组中的对应位置，如果新位置上已经有元素，则以链表或红黑树的形式存储； 3. 释放原数组中的空间。 扩容过程需要遍历原数组中的所有元素，重新计算哈希值，因此时间复杂度为 O(n)，其中 n 是原数组的长度。虽然扩容需要一定的时间和空间，但是它能够保证 HashMap 的性能和稳定性。