基本概念
HashMap是 Java 中最常用的 Map 实现类，它基于哈希表实现，提供了快速的查找、插入和删除操作。
核心特性
1.数据结构（Java 8 之前 vs Java 8+）
Java 8 之前：数组 + 链表
// 内部结构示意 table: Entry<K,V>[] 每个 Entry: [hash|key|value|next] → 链表节点Java 8+：数组 + 链表/红黑树
// 当链表长度 >= 8 且数组长度 >= 64 时，链表转为红黑树 table: Node<K,V>[] // Node 可能是链表节点或树节点 // 树化条件：链表长度 >= TREEIFY_THRESHOLD(8) && 数组长度 >= MIN_TREEIFY_CAPACITY(64)2.重要参数
static final int DEFAULT_INITIAL_CAPACITY = 16; // 默认初始容量 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认负载因子 static final int TREEIFY_THRESHOLD = 8; // 树化阈值 static final int UNTREEIFY_THRESHOLD = 6; // 链化阈值 static final int MIN_TREEIFY_CAPACITY = 64; // 最小树化容量核心源码解析
内部节点类
// Java 8 的 Node 类（链表节点） static class Node<K,V> implements Map.Entry<K,V> { final int hash; // 哈希值 final K key; // 键 V value; // 值 Node<K,V> next; // 下一个节点 // TreeNode 是 Node 的子类（红黑树节点） static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; boolean red; } }关键方法实现
1.hash() 方法 - 计算哈希值
static final int hash(Object key) { int h; // 让高位也参与哈希运算，减少哈希冲突 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }2.put() 方法流程
public V put(K key, V value) { // 计算哈希值 int hash = hash(key); // 1. 如果表为空，先初始化 if (table == EMPTY_TABLE) { inflateTable(threshold); } // 2. 计算索引位置 int i = indexFor(hash, table.length); // 3. 处理哈希冲突 // ... }完整 put 流程示例：
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 1. 如果 table 为空，进行初始化 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 2. 计算索引位置 (n-1) & hash if ((p = tab[i = (n - 1) & hash]) == null) // 3. 如果该位置为空，直接插入 tab[i] = newNode(hash, key, value, null); else { // 4. 处理哈希冲突 Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // 4.1 键相同，替换值 e = p; else if (p instanceof TreeNode) // 4.2 红黑树插入 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { // 4.3 链表遍历 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // 链表长度达到阈值，可能树化 if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 5. 如果存在相同键，更新值 if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } // 6. 修改次数增加 ++modCount; // 7. 检查是否需要扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }扩容机制（resize）
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; // 1. 计算新容量和新阈值 if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 容量翻倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // 阈值翻倍 } // 2. 创建新数组 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; // 3. 重新哈希，将旧数据迁移到新数组 if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) // 单个节点直接重新计算位置 newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) // 红黑树分裂 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // 链表分裂（优化：不需要重新计算hash） Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; // 判断节点应该放在原位置还是新位置 if ((e.hash & oldCap) == 0) { // 原索引位置 if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { // 新索引位置（原索引 + oldCap） if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }线程安全性问题
并发修改异常示例
public class HashMapConcurrentIssue { public static void main(String[] args) throws InterruptedException { Map<Integer, String> map = new HashMap<>(); Thread t1 = new Thread(() -> { for (int i = 0; i < 10000; i++) { map.put(i, "Value" + i); } }); Thread t2 = new Thread(() -> { for (int i = 0; i < 10000; i++) { map.put(i, "Value" + i); } }); t1.start(); t2.start(); t1.join(); t2.join(); // 可能出现：死循环、数据丢失、size不准等问题 System.out.println("Size: " + map.size()); } }性能优化技巧
1.初始化时指定容量
// 避免频繁扩容 Map<String, String> map = new HashMap<>(100); // 初始容量100 Map<String, String> map2 = new HashMap<>(100, 0.8f); // 容量100，负载因子0.82.使用合适的键类型
// 好的键类型：String、Integer等不可变类 class BadKey { int id; @Override public int hashCode() { return 1; // ❌ 所有键哈希值相同，导致严重冲突 } } class GoodKey { int id; @Override public int hashCode() { return Objects.hash(id); // ✅ 均匀分布 } }实战示例
public class HashMapAnalysis { // 自定义对象作为键 static class Student { String id; String name; public Student(String id, String name) { this.id = id; this.name = name; } // 必须正确实现 equals 和 hashCode @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Student student = (Student) o; return Objects.equals(id, student.id); } @Override public int hashCode() { return Objects.hash(id); } } public static void main(String[] args) { // 性能测试 Map<Integer, String> map = new HashMap<>(); long start = System.currentTimeMillis(); for (int i = 0; i < 1000000; i++) { map.put(i, "Value" + i); } long end = System.currentTimeMillis(); System.out.println("插入100万条数据耗时: " + (end - start) + "ms"); // 获取不存在的键 String value = map.get(9999999); // O(1) 时间复杂度 System.out.println("获取值: " + value); // 使用自定义对象作为键 Map<Student, Integer> studentScores = new HashMap<>(); studentScores.put(new Student("001", "Alice"), 95); studentScores.put(new Student("002", "Bob"), 88); System.out.println("Alice的分数: " + studentScores.get(new Student("001", "Alice"))); // 95 } }总结要点
底层结构：数组 + 链表/红黑树（JDK 8+）
扩容机制：容量翻倍，负载因子默认0.75
哈希计算：
(n-1) & hash计算索引线程不安全：多线程环境下需要同步
允许null键和null值
时间复杂度：
查找、插入、删除平均 O(1)
最坏情况 O(n) 或 O(log n)（树化后）
HashMap 是工程中非常高效的数据结构，理解其内部实现有助于编写更优化的代码。
进阶问题
hashMap的key计算用的hash表是什么结构？
HashMap 的哈希表结构详解
哈希表的底层结构
1.基本结构：数组 + 链表/红黑树
// HashMap 的核心字段 transient Node<K,V>[] table; // 哈希桶数组 transient int size; // 元素数量 int threshold; // 扩容阈值（容量 * 负载因子） final float loadFactor; // 负载因子（默认0.75）2.数组设计：长度总是 2 的幂
// HashMap 源码中的容量计算 static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }示例：
初始容量：15 计算后容量：16 (2⁴) 初始容量：17 计算后容量：32 (2⁵)为什么这种结构适合 HashMap？
1.高效的索引计算
// 传统取模运算（效率低） int index = hashCode % arrayLength; // HashMap 的优化运算（效率高） int index = (arrayLength - 1) & hashCode; // 示例： hashCode = 1010101010101010101010101010101 (32位) arrayLength = 16 = 0000000000000000000000000010000 (二进制) arrayLength - 1 = 15 = 0000000000000000000000000001111 (二进制) // 计算过程： 1010101010101010101010101010101 & 0000000000000000000000000001111 = 0000000000000000000000000000101 = 5 (索引位置)优点：
位运算(&)比取模运算(%)快得多
数组长度为2的幂时，
(n-1) & hash等价于hash % n
2.均匀分布减少哈希冲突
// HashMap 的 hash() 方法 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } // 示例： hashCode = 00001111000011110000111100001111 h >>> 16 = 00000000000000000000111100001111 异或结果 = 00001111000011110000000000000000 // 高位参与运算为什么需要扰动函数：
让高位参与运算，充分利用32位
减少哈希冲突，提高分布均匀性
3.动态扩容机制
// 扩容触发条件 if (size > threshold) { // threshold = capacity * loadFactor resize(); } // 扩容示例： 初始容量：16, 负载因子：0.75 扩容阈值：12 (16 * 0.75) 当元素数量 > 12 时触发扩容 新容量：32，新阈值：24扩容优化（JDK 8+）：
// 旧节点要么在原位置，要么在原位置+旧容量 // 通过 (e.hash & oldCap) == 0 判断 if ((e.hash & oldCap) == 0) { // 留在原索引位置 newTab[j] = loHead; } else { // 移动到新索引位置：j + oldCap newTab[j + oldCap] = hiHead; }4.链表转红黑树优化
// 树化条件 static final int TREEIFY_THRESHOLD = 8; // 链表长度阈值 static final int MIN_TREEIFY_CAPACITY = 64; // 最小树化容量 // 退化条件 static final int UNTREEIFY_THRESHOLD = 6; // 树退化为链表阈值性能对比：
链表查找：O(n)
红黑树查找：O(log n)
结构优势分析
1.时间复杂度优势
| 操作 | 平均情况 | 最坏情况 |
|---|---|---|
| 查找 | O(1) | O(log n) |
| 插入 | O(1) | O(log n) |
| 删除 | O(1) | O(log n) |
2.内存效率
// 数组的连续内存分配 Node<K,V>[] table = new Node[16]; // 对比其他结构： // 1. 数组：连续内存，CPU缓存友好 // 2. 链表：分散内存，指针开销 // 3. 红黑树：节点开销更大，但查询更快3.实际示例分析
public class HashMapStructureDemo { public static void main(String[] args) { HashMap<String, Integer> map = new HashMap<>(16); // 添加一些测试数据 map.put("A", 1); map.put("B", 2); map.put("C", 3); map.put("D", 4); map.put("E", 5); // 查看内部结构 printHashMapStructure(map); } static void printHashMapStructure(HashMap<?, ?> map) { try { Field tableField = HashMap.class.getDeclaredField("table"); tableField.setAccessible(true); Object[] table = (Object[]) tableField.get(map); System.out.println("HashMap 容量: " + (table != null ? table.length : 0)); for (int i = 0; i < table.length; i++) { Object node = table[i]; if (node != null) { System.out.print("索引 " + i + ": "); printNodeChain(node); } } } catch (Exception e) { e.printStackTrace(); } } static void printNodeChain(Object node) { Class<?> nodeClass = node.getClass(); StringBuilder sb = new StringBuilder(); try { // 遍历链表或树 while (node != null) { Field keyField = nodeClass.getDeclaredField("key"); keyField.setAccessible(true); Object key = keyField.get(node); Field nextField = nodeClass.getDeclaredField("next"); nextField.setAccessible(true); sb.append(key).append(" -> "); node = nextField.get(node); } sb.append("null"); System.out.println(sb.toString()); } catch (Exception e) { // 可能是树节点 System.out.println("[TreeNode Structure]"); } } }4.哈希冲突处理策略
// 完美哈希（理想情况）：每个键映射到唯一索引 键1 -> 索引2 键2 -> 索引5 键3 -> 索引1 // 实际冲突处理：链地址法 索引3: 键A -> 键D -> 键G // 链表 索引6: 键B -> 键E -> 键F -> 键H -> 键I -> 键J -> 键K -> 键L // 长度≥8时转为红黑树 // 扩容减少冲突： 扩容前：容量16，12个元素，冲突较多 扩容后：容量32，12个元素，冲突减少为什么选择这种结构？
1.历史演变
JDK 1.7 之前：
纯数组 + 链表
多线程下可能产生死循环（扩容时头插法）
JDK 1.8+：
数组 + 链表/红黑树
尾插法避免死循环
性能更好
2.设计权衡
// 设计考虑因素 - 查找速度 vs 内存开销 - 插入速度 vs 删除速度 - 平均性能 vs 最坏性能 // HashMap 的平衡点： 1. 数组：快速随机访问 2. 链表：解决冲突，动态扩展 3. 红黑树：避免极端退化 4. 负载因子0.75：空间时间平衡点3.与其他数据结构的对比
// HashMap vs TreeMap HashMap：哈希表，O(1)平均查找，无序 TreeMap：红黑树，O(log n)查找，有序 // HashMap vs LinkedHashMap HashMap：不保证顺序 LinkedHashMap：维护插入顺序或访问顺序 // HashMap vs ConcurrentHashMap HashMap：非线程安全，性能高 ConcurrentHashMap：线程安全，分段锁/乐观锁总结
HashMap 的哈希表结构之所以适合作为 key 的存储结构，是因为：
数组结构：提供 O(1) 的随机访问能力
链表解决冲突：简单高效地处理哈希冲突
红黑树优化：防止极端退化，保证最坏情况性能
2的幂长度：优化索引计算，位运算代替取模
扰动函数：提高哈希分布均匀性
动态扩容：平衡空间和时间效率
这种设计在平均情况下提供了接近常数时间的性能，同时在空间利用率和代码复杂度之间找到了良好的平衡点。
)
