HashMap 原理

Map 家族：键值映射#

Map 与 Collection 并列，保存键值对。常见实现：

• HashMap：最常用，不保证顺序
• LinkedHashMap：保持插入顺序
• TreeMap：按键排序
• Hashtable：老的线程安全实现
• ConcurrentHashMap：并发场景 → 专篇

1
Map<String, Integer> scores = new HashMap<>();
2
scores.put("Tom", 90);
3
System.out.println(scores.get("Tom"));

键不能重复；同一键再次 put 会覆盖旧值。

HashMap 和 Hashtable 的区别#

1
Map<String, Integer> scores = new HashMap<>();
2
scores.put(null, 0);
3

4
Map<String, Integer> table = new Hashtable<>();
5
// table.put(null, 1); // NullPointerException

并发读写优先 ConcurrentHashMap，而不是 Hashtable。

HashMap 原理：结构、哈希与版本差异#

数组 + 链表（JDK 8 起链表过长会树化为红黑树），链地址法解决冲突。

hash 扰动（JDK 8）：(h = key.hashCode()) ^ (h >>> 16)。下标：index = (table.length - 1) & hash，要求 table 长度为 2 的幂。

树化：数组太小时会先 resize 扩容，不是一到 8 就树化。

适合做 key 的类型：String、Integer 等不可变且已实现 equals/hashCode 的类型。自定义 key 必须同时重写两者。

HashMap 的 put 与扩容流程#

1. table 为空 → resize()（默认容量 16，负载因子 0.75）
2. 计算 hash，i = (n - 1) & hash
3. 桶空 → 放 Node
4. 桶非空：key 相同 → 覆盖；TreeNode → 树插入；否则链表尾插
5. 链表长度达 8 → 可能 treeifyBin
6. ++size > threshold → 扩容为 2 倍

扩容（JDK 8）：节点留在原索引或移到 原索引 + oldCap，由 (e.hash & oldCap) == 0 判断。

1
map.put("Tom", 90);
2
map.put("Tom", 95); // 覆盖 value

Map.get 可能返回 null#

键不存在时 get 返回 null，拆箱成 int 前注意 NPE。

误以为 HashMap 线程安全#

多线程读写同一 HashMap 可能数据不一致；用 ConcurrentHashMap 或加锁。

自定义 key 未重写 equals/hashCode#

逻辑相等的键可能查不到或无法覆盖。