LinkedHashMap 与 TreeMap 底层原理

LinkedHashMap 继承自 HashMap，在哈希表之上额外维护一条双向链表来保持顺序；TreeMap 基于红黑树实现，key 天然有序。理解它们，需要深入到源码层面的节点结构、钩子方法和树旋转操作。

LinkedHashMap 的底层结构

节点设计：一个节点，两种结构

public class LinkedHashMap<K,V> extends HashMap<K,V> {
    transient LinkedHashMap.Entry<K,V> head; // 双向链表头（最老元素）
    transient LinkedHashMap.Entry<K,V> tail; // 双向链表尾（最新元素）
    final boolean accessOrder; // false=插入顺序，true=访问顺序

    // 继承 HashMap.Node，多了两个链表指针
    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;  // 双向链表的前驱和后继
    }
}

核心设计思想：每个 Entry 节点同时存在于两个结构中——HashMap 的桶（通过 next 指针形成桶内链表）+ 全局双向链表（通过 before/after 指针维护顺序）。这意味着查找走哈希表 O(1)，遍历走双向链表保证有序。

HashMap 桶数组: [0]→null  [1]→A  [2]→B→C  [3]→null  [4]→D
                              ↓        ↓  ↓              ↓
全局双向链表:   head ↔ A ↔ B ↔ C ↔ D ↔ tail
                 （按插入顺序串联所有节点）

注意区分：next 是桶内的单向链表指针（继承自 HashMap.Node），before/after 是全局双向链表指针。两套指针互不干扰。

钩子方法：LinkedHashMap 接管 HashMap 的三个回调

LinkedHashMap 不重写 put()、get() 等主方法，而是重写 HashMap 预留的三个钩子方法（callback），在 HashMap 的操作流程中"插一脚"来维护双向链表：

// HashMap 中定义为空实现，留给子类重写
void afterNodeAccess(Node<K,V> p) { }    // 节点被访问后
void afterNodeInsertion(boolean evict) { } // 新节点插入后
void afterNodeRemoval(Node<K,V> p) { }   // 节点被删除后

afterNodeAccess —— 访问顺序的核心

当 accessOrder = true 时，每次访问（get()、put() 更新已有 key）一个节点后，会将该节点移动到双向链表的尾部：

// LinkedHashMap 中的实现（简化）
void afterNodeAccess(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        // 1. 把节点 e 从链表原位置摘除
        LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e;
        LinkedHashMap.Entry<K,V> b = p.before, a = p.after;
        p.after = null;
        if (b == null) head = a;     // e 是头节点
        else b.after = a;
        if (a != null) a.before = b; // e 不是尾节点
        else last = b;

        // 2. 把节点 e 追加到链表尾部
        if (last == null) head = p;
        else { p.before = last; last.after = p; }
        tail = p;
        ++modCount;
    }
}

直觉理解：链表尾部 = 最近访问，链表头部 = 最久未访问。每次访问一个元素，就把它"拎到队尾"。

afterNodeInsertion —— LRU 淘汰的触发点

新节点插入后被调用，内部检查是否需要移除最老的元素：

void afterNodeInsertion(boolean evict) {
    LinkedHashMap.Entry<K,V> first;
    // removeEldestEntry() 默认返回 false
    // 子类重写后可返回 true 来触发淘汰
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true); // 删除链表头节点
    }
}

afterNodeRemoval —— 同步删除链表节点

节点从 HashMap 中删除后，同步从双向链表中摘除：

void afterNodeRemoval(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e;
    LinkedHashMap.Entry<K,V> b = p.before, a = p.after;
    p.before = p.after = null;
    if (b == null) head = a;
    else b.after = a;
    if (a == null) tail = b;
    else a.before = b;
}

设计模式：这是典型的模板方法模式。HashMap 定义算法骨架（put/get/remove），LinkedHashMap 通过重写钩子方法扩展行为，无需修改父类代码。

两种排序模式

// 模式一：插入顺序（默认）
Map<String, Integer> insertionOrder = new LinkedHashMap<>();
insertionOrder.put("B", 2);
insertionOrder.put("A", 1);
insertionOrder.put("C", 3);
// 遍历顺序：B → A → C（按插入先后）

// 模式二：访问顺序 —— LRU 缓存的关键
Map<String, Integer> accessOrder = new LinkedHashMap<>(16, 0.75f, true);
accessOrder.put("B", 2);
accessOrder.put("A", 1);
accessOrder.put("C", 3);
accessOrder.get("B"); // 访问 B，B 被移到尾部
// 遍历顺序：A → C → B（B 最近被访问，排到最后）

用 LinkedHashMap 实现 LRU 缓存

LRU（Least Recently Used）缓存在容量满时淘汰最久未使用的元素。LinkedHashMap 天然支持：

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;

    public LRUCache(int maxSize) {
        super(maxSize, 0.75f, true); // accessOrder=true 是关键
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize; // 超过容量就淘汰最老元素
    }
}

工作流程：

操作 put("A", 1):  链表: head→A→tail
操作 put("B", 2):  链表: head→A→B→tail
操作 put("C", 3):  链表: head→A→B→C→tail  （假设 maxSize=3，刚好满）
操作 get("A"):     链表: head→B→C→A→tail  （A 被访问，移到尾部）
操作 put("D", 4):  链表: head→C→A→D→tail  （超容量，head 的 B 被淘汰）

生产高频：LeetCode 146 要求手写 LRU 缓存，LinkedHashMap 是最简洁的实现（但在底层系统实现中通常需要你使用 HashMap + 手写双向链表）。

LinkedHashMap 的迭代器

LinkedHashMap 重写了迭代器，直接遍历双向链表而非扫描哈希桶：

// HashMap 的 entrySet 遍历：需要扫描整个桶数组，跳过空桶
// LinkedHashMap 的 entrySet 遍历：沿着 head→tail 链表走，每个节点都有值

abstract class LinkedHashIterator {
    LinkedHashMap.Entry<K,V> next;

    LinkedHashIterator() {
        next = head; // 从链表头开始
    }

    final LinkedHashMap.Entry<K,V> nextNode() {
        LinkedHashMap.Entry<K,V> e = next;
        next = e.after; // 沿 after 指针前进
        return e;
    }
}

性能差异：HashMap 遍历的时间复杂度是 O(capacity + size)（需要扫描空桶），LinkedHashMap 是 O(size)（直接走链表）。当桶数组很大但元素很少时，LinkedHashMap 的遍历快得多。

TreeMap 的底层结构

红黑树基础

TreeMap 的底层是一棵红黑树（Red-Black Tree），一种自平衡的二叉搜索树。红黑树通过颜色标记和旋转操作，保证树的高度始终接近 O(log n)，避免二叉搜索树退化为链表。

红黑树的五条性质：

性质 4 和 5 共同保证了：最长路径不超过最短路径的 2 倍。最短路径全是黑色节点，最长路径是红黑交替，因此红黑树不会严重不平衡。

节点设计

public class TreeMap<K,V> implements NavigableMap<K,V> {
    private transient Entry<K,V> root;              // 红黑树根节点
    private final Comparator<? super K> comparator; // 自定义比较器（可选）

    static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left;    // 左子树（比当前 key 小）
        Entry<K,V> right;   // 右子树（比当前 key 大）
        Entry<K,V> parent;  // 父节点
        boolean color = BLACK; // 默认黑色
    }
}

TreeMap 的 put 流程

public V put(K key, V value) {
    Entry<K,V> t = root;

    // 1. 树为空 → 新节点直接作为根
    if (t == null) {
        root = new Entry<>(key, value, null);
        size = 1;
        return null;
    }

    // 2. 从根开始，二分查找插入位置
    int cmp;
    Entry<K,V> parent;
    Comparator<? super K> cpr = comparator;
    do {
        parent = t;
        cmp = cpr != null ? cpr.compare(key, t.key)
                          : ((Comparable<? super K>)key).compareTo(t.key);
        if (cmp < 0)      t = t.left;   // key 小于当前节点，走左子树
        else if (cmp > 0) t = t.right;  // key 大于当前节点，走右子树
        else              return t.setValue(value); // key 相等，覆盖旧值
    } while (t != null);

    // 3. 创建新节点，挂到 parent 的左或右
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0) parent.left = e;
    else         parent.right = e;

    // 4. 新节点默认是 RED，可能破坏红黑树性质 → 修复
    fixAfterInsertion(e);
    size++;
    return null;
}

为什么新节点默认是红色？ 因为插入黑色节点一定会违反性质 5（黑色高度不一致），而插入红色节点只在父节点也是红色时才违反性质 4。红色节点"影响最小"。

红黑树的旋转操作

旋转是红黑树维持平衡的核心手段，分为左旋和右旋，两者互为镜像。

左旋（rotateLeft）

以节点 P 为轴，将 P 的右孩子 R "提上来"：

    P                R
   / \              / \
  X   R    →       P   Y
     / \          / \
    RL  Y        X  RL

private void rotateLeft(Entry<K,V> p) {
    Entry<K,V> r = p.right;
    p.right = r.left;          // R 的左子树 RL 变成 P 的右子树
    if (r.left != null) r.left.parent = p;
    r.parent = p.parent;       // R 顶替 P 的位置
    if (p.parent == null)      root = r;
    else if (p.parent.left == p) p.parent.left = r;
    else                       p.parent.right = r;
    r.left = p;                // P 变成 R 的左孩子
    p.parent = r;
}

右旋（rotateRight）

以节点 P 为轴，将 P 的左孩子 L "提上来"——左旋的镜像操作：

      P              L
     / \            / \
    L   Y    →     X   P
   / \                / \
  X  LR             LR   Y

fixAfterInsertion —— 插入后的修复

新插入的红色节点可能导致连续红节点（违反性质 4），需要通过变色和旋转修复。fixAfterInsertion 是一个 while 循环，沿着树自底向上处理：

新节点 x（红色）的父节点也是红色？
├─ 叔叔节点是红色（Case 1）
│   → 父和叔变黑，祖父变红，x 指向祖父继续循环
│   （颜色往上推，可能需要继续修复）
│
└─ 叔叔节点是黑色（或 NIL）
    ├─ x 是父节点的"内侧"孩子（Case 2）
    │   → 先对父节点旋转，转化为 Case 3
    │
    └─ x 是父节点的"外侧"孩子（Case 3）
        → 父变黑，祖父变红，对祖父旋转
        → 修复完成

Case 1 示例（叔叔是红色，只需变色）：

      G(黑)                G(红)  ← x 上移到这里
     / \                  / \
   P(红) U(红)    →    P(黑) U(黑)
   /                   /
  x(红)              x(红)

Case 3 示例（叔叔是黑色，需要旋转）：

      G(黑)               P(黑)
     / \                 / \
   P(红) U(黑)   →    x(红) G(红)
   /                         \
  x(红)                      U(黑)

无论多复杂的情况，fixAfterInsertion 最多做 2 次旋转 + 若干次变色（变色最多 O(log n) 次）。这保证了插入操作的整体复杂度是 O(log n)。

TreeMap 的常用 API

TreeMap 实现了 NavigableMap 接口，提供丰富的范围查询操作：

TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "c"); map.put(1, "a"); map.put(5, "e"); map.put(2, "b");

// 边界查询
map.firstKey();              // 1（最小 key）
map.lastKey();               // 5（最大 key）
map.firstEntry();            // 1=a（最小键值对）
map.lastEntry();             // 5=e（最大键值对）

// 邻近查询
map.lowerKey(3);             // 2（严格小于 3 的最大 key）
map.higherKey(3);            // 5（严格大于 3 的最大 key）
map.floorKey(3);             // 3（小于等于 3 的最大 key）
map.ceilingKey(3);           // 3（大于等于 3 的最小 key）

// 范围查询
map.subMap(2, 5);            // {2=b, 3=c}（[2, 5)，左闭右开）
map.subMap(2, true, 5, true); // {2=b, 3=c, 5=e}（[2, 5]，双闭）
map.headMap(3);              // {1=a, 2=b}（< 3）
map.tailMap(3);              // {3=c, 5=e}（≥ 3）

// 逆序
map.descendingMap();         // {5=e, 3=c, 2=b, 1=a}

HashMap vs LinkedHashMap vs TreeMap

Map 选型指南

需要键值对存储？
├─ 不关心顺序 → HashMap（最快，默认选择）
├─ 需要保持插入顺序 → LinkedHashMap
├─ 需要按 key 排序 → TreeMap
├─ 需要范围查询（subMap/headMap/tailMap）→ TreeMap
├─ 需要线程安全 → ConcurrentHashMap
└─ 需要 LRU 缓存 → LinkedHashMap（accessOrder=true）

常见生产故障考点

Q：LinkedHashMap 和 HashMap 的性能差距大吗？

几乎没有。put/get/remove 都是 O(1)，额外的链表维护只是常数级的 before/after 指针操作。唯一代价是每个节点多占约 16 字节（两个引用指针）。遍历时 LinkedHashMap 甚至更快，因为直接走链表，不需要扫描空桶。

Q：TreeMap 的 key 可以是 null 吗？为什么？

不可以。TreeMap 的所有操作都依赖 compareTo() 或 Comparator.compare() 来比较 key，而 null.compareTo(xxx) 会抛 NullPointerException。

Q：红黑树 vs AVL 树，为什么 Java 选红黑树？

AVL 树是严格平衡的（左右子树高度差 ≤ 1），查找更快；但插入和删除时需要更多旋转来维持严格平衡。红黑树是"近似平衡"的，插入最多 2 次旋转、删除最多 3 次旋转，在增删频繁的场景下总体性能更优。Java 集合（HashMap 树化、TreeMap）都面临频繁增删，选红黑树是合理的工程权衡。