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()方法的时候因为已经达到预设门限所以开始扩展空间并将已有内容复制过去调整后的位置。