HashMap知识点

一、HashMap 核心定义HashMap是 Java 集合框架中Map接口的哈希表实现位于java.util包下用于存储「键值对Key-Value」允许Key和Value为null仅一个Key为null线程不安全元素无序不保证插入 / 遍历顺序。二、底层原理JDK 8 核心HashMap 底层是「数组 链表 红黑树」的复合结构核心设计是为了解决哈希冲突提升查询 / 增删效率数组哈希桶table数组类型为NodeK,V[]链表节点每个数组下标对应一个「哈希桶」桶中存储链表 / 红黑树数组默认初始容量为 16容量必须是 2 的幂便于通过hash (length-1)替代取模提升计算效率。链表解决哈希冲突当多个 Key 的哈希值映射到同一个数组下标时会以链表形式存储JDK 7 头插法JDK 8 尾插法避免扩容时链表成环链表节点Node包含 4 个属性hashKey 的哈希值、key、value、next后继节点。红黑树优化链表性能当链表长度 ≥ 8 且数组容量 ≥ 64 时链表转为红黑树降低查询时间复杂度从 O (n) 到 O (logn)当红黑树节点数 ≤ 6 时转回链表红黑树维护成本高少量节点时链表更高效。三、核心机制面试重中之重1. 哈希计算与索引定位graph LR A[Key] -- B[计算hashCode()] B -- C[扰动函数hash hashCode() ^ (hashCode() 16)] C -- D[索引计算index hash (table.length - 1)]扰动函数JDK 8 中通过hash ^ (hash 16)混合哈希码的高位和低位减少哈希冲突避免高位特征未被利用索引计算用hash (length-1)替代hash % length仅当容量为 2 的幂时等价位运算效率更高。2. 扩容机制resize触发条件元素个数size≥ 阈值threshold 容量 × 负载因子链表转红黑树前发现数组容量 64先扩容而非转树。扩容流程新容量 原容量 × 2保持 2 的幂重新计算每个节点的索引JDK 8 优化只需判断哈希值的新增位是 0 还是 1无需重新计算 hash将原数组节点迁移到新数组链表 / 红黑树拆分默认参数负载因子loadFactor默认 0.75平衡空间与时间过小扩容频繁过大哈希冲突概率高。3. 元素插入流程JDK 8graph TD A[put(Key, Value)] -- B[计算Key的hash值] B -- C[计算索引index hash (length-1)] C -- D{桶是否为空?} D --|是| E[新建Node放入桶中] D --|否| F{桶中是红黑树?} F --|是| G[红黑树插入节点] F --|否| H{Key是否已存在?} H --|是| I[替换Value] H --|否| J[链表尾部插入节点] J -- K{链表长度≥8且容量≥64?} K --|是| L[链表转红黑树] K --|否| M[插入完成]四、核心特性表格特性说明线程安全线程不安全无同步锁多线程并发修改可能导致死循环JDK 7/ 数据丢失需用ConcurrentHashMap允许 null 值Key 仅允许一个 null哈希值固定为 0Value 可多个 null有序性无序不保证插入顺序与遍历顺序一致需有序则用LinkedHashMap时间复杂度理想情况无哈希冲突增删改查 O (1)最坏情况全冲突链表 O (n)、红黑树 O (logn)初始容量 / 负载因子默认容量 16负载因子 0.75可通过构造方法指定建议初始化时指定容量避免多次扩容五、常用核心方法java运行// 1. 初始化 HashMapString, Integer map new HashMap(); // 默认容量16负载因子0.75 HashMapString, Integer map2 new HashMap(32); // 指定初始容量会自动调整为2的幂 HashMapString, Integer map3 new HashMap(32, 0.8f); // 指定容量和负载因子 // 2. 增删改查 map.put(java, 1); // 插入键值对Key存在则替换Value map.putIfAbsent(python, 2); // Key不存在时才插入 Integer val map.get(java); // 获取ValueKey不存在返回null map.remove(python); // 删除键值对 boolean exists map.containsKey(java); // 判断Key是否存在 map.replace(java, 10); // 替换ValueKey存在才生效 // 3. 遍历推荐方式 // 方式1遍历KeySet for (String key : map.keySet()) { System.out.println(key : map.get(key)); } // 方式2遍历EntrySet效率更高避免二次get for (Map.EntryString, Integer entry : map.entrySet()) { System.out.println(entry.getKey() : entry.getValue()); } // 方式3Lambda遍历 map.forEach((k, v) - System.out.println(k : v)); // 4. 其他常用 int size map.size(); // 获取元素个数 map.clear(); // 清空所有元素 SetMap.EntryString, Integer entrySet map.entrySet(); // 获取所有键值对六、面试高频考点1. JDK 7 vs JDK 8 核心差异表格维度JDK 7JDK 8底层结构数组 链表数组 链表 红黑树插入方式头插法扩容易成环尾插法避免成环哈希计算多次位运算 / 异或复杂简化为 hash ^ (hash 16)扩容后索引计算重新计算 hash → 取模按哈希值新增位判断0/1性能链表查询 O (n)红黑树查询 O (logn)2. 易错点Key 的 hashCode 和 equals 重写必须同时重写hashCode()和equals()否则可能导致 Key 重复存储规则equals()相等的 KeyhashCode()必须相等hashCode()相等的 Keyequals()不一定相等。并发问题JDK 7 多线程扩容时链表头插法可能导致死循环JDK 8 解决了死循环但仍会出现数据丢失 / 覆盖并发场景优先用ConcurrentHashMap。null Key 处理null Key 的哈希值固定为 0索引为 0因此仅能有一个 null Key。初始容量选择若预估存储 1000 个元素建议初始化容量为1000 / 0.75 ≈ 1334再向上取最近的 2 的幂2048避免扩容。3. HashMap vs Hashtable 对比表格维度HashMapHashtable线程安全不安全安全方法加 synchronizednull 支持Key/Value 可 null不支持 null性能高无锁低全表锁底层结构数组 链表 红黑树JDK8数组 链表初始容量1611扩容方式2 倍2 倍 1七、使用场景适合单线程、频繁增删改查的键值对存储场景适合对顺序无要求、追求查询效率的场景不适合并发场景用 ConcurrentHashMap、有序场景用 LinkedHashMap。总结HashMap 核心关键点JDK 8 底层是数组 链表 红黑树哈希计算用扰动函数 位运算扩容保持容量为 2 的幂红黑树阈值链表≥8 转树树≤6 转链表负载因子默认 0.75平衡空间与效率线程不安全Key 需重写 hashCode/equals并发场景用 ConcurrentHashMap。