Java集合-LinkedHashMap

前言

LinkedHashMap 是 Java 集合框架中的一种数据结构，它继承自 HashMap，并通过维护一个双向链表来保证元素的插入顺序或访问顺序。下面我会从其定义、特性、源码实现以及使用场景等方面展开讲解。

LinkedHashMap 是 HashMap 的子类，位于 java.util 包中。它的主要特点是：

有序性：默认按照插入顺序（insertion-order）维护键值对，也可以通过配置支持访问顺序（access-order）。
底层结构：结合了哈希表（HashMap）和双向链表，兼具快速查找（$O(1)$ 时间复杂度）和顺序遍历的能力。
线程不安全：与 HashMap 一样，LinkedHashMap 不是线程安全的，多线程环境下需要外部同步。

源码分析

LinkedHashMap 的类定义如下：

1	public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

数据结构

LinkedHashMap 在 HashMap 的基础上增加了一个双向链表，用于维护顺序。它的核心节点类是 Entry，定义如下：

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after; // 双向链表的前后指针
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

HashMap.Node 是哈希表的节点，包含 hash、key、value 和 next（用于处理哈希冲突）。
before 和 after 是 LinkedHashMap 特有的，用于连接前后节点，形成双向链表。

此外，LinkedHashMap 还维护了链表的头尾指针：

1 2	transient LinkedHashMap.Entry<K,V> head; // 链表头部 transient LinkedHashMap.Entry<K,V> tail; // 链表尾部

构造方法

LinkedHashMap 提供了多个构造方法，其中一个关键参数是 accessOrder：

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
    super(initialCapacity, loadFactor); // 调用 HashMap 的构造方法
    this.accessOrder = accessOrder;     // 是否启用访问顺序
}

accessOrder = false（默认）：按插入顺序。
accessOrder = true：按访问顺序（每次 get 或 put 会调整链表）。

核心方法

LinkedHashMap 的大部分操作（如 put、get）直接复用了 HashMap 的实现，但通过钩子方法（Hook Method）扩展了链表维护逻辑。

`put` 方法

LinkedHashMap 本身没有重写 put，而是依赖 HashMap 的 put。
在 HashMap 中，put 会调用 newNode 创建新节点，而 LinkedHashMap 重写了这个方法：

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<>(hash, key, value, e);
    linkNodeLast(p); // 将新节点添加到链表尾部
    return p;
}

linkNodeLast 方法：

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null) // 链表为空
        head = p;
    else {            // 连接新节点到尾部
        p.before = last;
        last.after = p;
    }
}

`get` 方法

默认情况下，LinkedHashMap 的 get 直接调用 HashMap 的实现。
当 accessOrder = true 时，get 会触发元素移动到链表尾部：

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder) // 如果是访问顺序模式
        afterNodeAccess(e); // 移动到尾部
    return e.value;
}

afterNodeAccess 方法：

void afterNodeAccess(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

`remove` 方法

删除时需要同时维护哈希表和链表，LinkedHashMap 重写了 afterNodeRemoval：

void afterNodeRemoval(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, 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;
}

LRU 缓存支持

LinkedHashMap 提供了一个方法 removeEldestEntry，用于实现 LRU（Least Recently Used）缓存：

1
2
3

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false; // 默认不移除
}

通过重写这个方法，可以在插入新元素时移除最老的元素。例如：

LinkedHashMap<Integer, String> lruMap = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {
        return size() > 3; // 容量超过 3 时移除最老的元素
    }
};

后记

核心特性

插入顺序：默认情况下，迭代 LinkedHashMap 时，元素按放入的顺序返回。
访问顺序：通过构造参数 accessOrder 设置为 true，可以让 LinkedHashMap 按访问顺序排列（最近访问的元素移到链表末尾，适用于 LRU 缓存场景）。
性能：查找、插入、删除操作的时间复杂度与 HashMap 一致（平均 $O(1)$），但维护链表会带来少量额外开销。

使用场景

需要顺序的映射：如按插入顺序输出键值对。
LRU 缓存实现：通过设置 accessOrder = true 并重写 removeEldestEntry，实现简单的缓存。
日志记录：记录事件并按时间顺序遍历。

总结

从源码角度看，LinkedHashMap 通过继承 HashMap 并添加双向链表，巧妙地实现了有序性。它的核心在于：

通过 Entry 类扩展节点，维护前后指针。
通过钩子方法（如 newNode、afterNodeAccess）在 HashMap 操作的基础上更新链表。
提供灵活的顺序模式（插入顺序或访问顺序）。