Map 详解
掌握 HashMap 原理、TreeMap、LinkedHashMap 与 LRU
Map 详解
Map 是键值对的集合——通过 key 快速查找 value，就像查字典。HashMap 是最常用的实现，理解它的内部原理对写出高性能代码至关重要。
学完本章你将： 掌握 HashMap 原理、LinkedHashMap 顺序控制、TreeMap 排序。
HashMap 基础操作
java
Map<String, Integer> map = new HashMap<>();
map.put("Alice", 25); // 添加
map.put("Bob", 30);
map.get("Alice"); // 25，获取
map.getOrDefault("Charlie", 0); // 0，不存在给默认值
map.remove("Bob"); // 删除
map.putIfAbsent("Alice", 100); // 不存在才添加（Alice 已存在，不覆盖）
map.computeIfPresent("Alice", (k, v) -> v + 1); // 存在就 +1
map.computeIfAbsent("Dave", k -> 18); // 不存在就计算默认值
map.forEach((k, v) -> System.out.println(k + ": " + v));HashMap 内部原理 —— 数组 + 链表 + 红黑树
HashMap 的"快"来自于把 key 的 hashCode 映射到数组下标。但不同 key 可能映射到同一下标（hash 冲突），所以每个位置实际是个链表（或红黑树）。
put("Alice", 25) 的执行流程：
1. 计算 "Alice".hashCode() → 比如 1234567
2. 1234567 % 数组长度(默认16) → 下标 7
3. 放到数组[7]的位置（如果已有元素，追加到链表末尾）为什么链表会变成红黑树？ 当同一个位置的链表长度超过 8 且数组长度超过 64 时，链表自动转为红黑树，查找复杂度从 O(n) 降为 O(log n)。这就是为什么正确重写 hashCode 很重要——如果所有 key 的 hashCode 都一样，HashMap 会退化成一个长链表，性能从 O(1) 变成 O(n)。
扩容： 当元素数超过 容量 × 0.75（负载因子），数组扩容为原来的 2 倍，所有元素重新计算位置。
LinkedHashMap —— 记住顺序
HashMap 不保证遍历顺序。LinkedHashMap 用双向链表维护了元素的插入顺序（或访问顺序）。
java
// 插入顺序
Map<String, Integer> linked = new LinkedHashMap<>();
linked.put("C", 3);
linked.put("A", 1);
linked.put("B", 2);
System.out.println(linked); // {C=3, A=1, B=2} —— 按插入顺序！
// 访问顺序 —— 实现 LRU 缓存
Map<String, Integer> lru = new LinkedHashMap<>(16, 0.75f, true);
lru.put("A", 1);
lru.put("B", 2);
lru.get("A"); // A 被"访问"，自动排到最后
// 最久未访问的在最前面TreeMap —— 自动排序
TreeMap 基于红黑树，key 按自然顺序（或自定义 Comparator）自动排序。支持范围查询。
java
Map<String, Integer> tree = new TreeMap<>();
tree.put("Banana", 2);
tree.put("Apple", 1);
tree.put("Cherry", 3);
System.out.println(tree); // {Apple=1, Banana=2, Cherry=3} —— 字母序
// 范围查询：Apple（含）到 Cherry（不含）
SortedMap<String, Integer> sub = ((TreeMap<String, Integer>) tree)
.subMap("Apple", "Cherry"); // {Apple=1, Banana=2}怎么选？
| 需求 | 用哪个 |
|---|---|
| 快速增删查，无所谓顺序 | HashMap（95% 场景） |
| 需要记住插入顺序 | LinkedHashMap |
| 需要按 key 排序或范围查询 | TreeMap |
| 线程安全 | ConcurrentHashMap |