【Java】LinkedHashMap详解：有序映射与LRU缓存实战

By - YunYang
Posted on 2026-05-07
Posted in Java

【Java】LinkedHashMap详解：有序映射与LRU缓存实战

大家好，我是云扬～今天来和大家深入聊聊 Java 集合框架中的 LinkedHashMap。作为 HashMap 的子类，它不仅继承了哈希表的高效特性，还通过双向链表实现了元素的有序管理，这让它在很多场景下比 HashMap 更实用。下面我们从原理到实战，一步步揭开 LinkedHashMap 的神秘面纱～

一、LinkedHashMap 核心特性：继承与存储结构

1. 继承关系

LinkedHashMap 直接继承自 HashMap，因此完全拥有 HashMap 的所有功能（如哈希存储、扩容机制等），同时实现了 Map 接口，保证了映射表的基本行为。其类定义如下：

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{   // 核心源码省略}

2. 存储结构：哈希表 + 双向链表

LinkedHashMap 的存储结构是 数组 + 链表 / 红黑树（哈希表） + 双向链表 的组合：

哈希表部分：与 HashMap 一致，用于快速查找、插入和删除元素，解决哈希冲突；
双向链表部分：这是 LinkedHashMap 的核心扩展，通过 before 和 after 指针维护元素的顺序（插入顺序或访问顺序）。

内部 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);
    }

二、插入顺序：有序遍历的实现

LinkedHashMap 默认按 插入顺序 维护元素，遍历时有序输出，这是它与 HashMap 最直观的区别。

1. 实现原理

通过重写 HashMap 的 newNode() 方法，在创建新节点时调用 linkNodeLast()，将新节点插入双向链表的尾部，从而保证插入顺序：

// LinkedHashMap 重写 newNode 方法
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;
}
// 将节点插入双向链表尾部
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;
    }
}

2. 代码示例：插入顺序遍历

public class LinkedHashMapInsertOrderDemo {
    public static void main(String[] args) {
        Map<String, String> linkedHashMap = new LinkedHashMap<>();
        Map<String, String> hashMap = new HashMap<>(); // 插入元素
        linkedHashMap.put("name", "云扬");
        linkedHashMap.put("age", "18");
        linkedHashMap.put("blog", "云扬のBlog");
        hashMap.put("name", "云扬");
        hashMap.put("age", "18");
        hashMap.put("blog", "云扬のBlog");
       // 遍历输出
       System.out.println("LinkedHashMap 插入顺序遍历：");
       for (Map.Entry<String, String> entry : linkedHashMap.entrySet()) {
          System.out.println(entry.getKey() + ":" + entry.getValue());
        }
       System.out.println("\nHashMap 无序遍历：");
       for (Map.Entry<String, String> entry : hashMap.entrySet()) {
          System.out.println(entry.getKey() + ":" + entry.getValue());
        }
    }
}

输出结果：

LinkedHashMap 插入顺序遍历：
name:云扬
age:18
blog:云扬のBlog

HashMap 无序遍历：
name:云扬
blog:云扬のBlog
age:18

3. 与 HashMap 的对比

特性	HashMap	LinkedHashMap
顺序	无序	有序（插入 / 访问顺序）
性能	插入 / 删除更快	略慢（需维护双向链表）
适用场景	无需顺序，追求高效	需要有序遍历的场景

三、访问顺序：动态调整元素位置

LinkedHashMap 支持按 访问顺序 排序（即每次访问元素后，将其移到双向链表尾部），只需在构造时指定 accessOrder=true。

1. 实现原理

通过重写 afterNodeAccess() 方法，在调用 get() 或 put() 访问元素后，将该节点移到链表尾部：

// 访问元素后触发，将节点移到尾部
void afterNodeAccess(Node<K,V> e) { // move node to last
    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;
    }
}

2. 代码示例：访问顺序遍历

public class LinkedHashMapAccessOrderDemo {
    public static void main(String[] args) {
         // 指定 accessOrder=true，开启访问顺序
        LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<>(16, 0.75f, true);

        linkedHashMap.put("A", "Apple");
        linkedHashMap.put("B", "Banana");
        linkedHashMap.put("C", "Cherry");

        System.out.println("初始顺序（插入顺序）：" + linkedHashMap.keySet());

        // 访问元素 B
        linkedHashMap.get("B");
        System.out.println("访问 B 后顺序：" + linkedHashMap.keySet());

        // 访问元素 A
        linkedHashMap.get("A");
        System.out.println("访问 A 后顺序：" + linkedHashMap.keySet());

    }
}

输出结果：

初始顺序（插入顺序）：[A, B, C]
访问 B 后顺序：[A, C, B]
访问 A 后顺序：[C, B, A]

可以看到，每次访问的元素都会被移到链表尾部，尾部元素始终是最近访问的元素。

四、实战：用 LinkedHashMap 实现 LRU 缓存

LRU（Least Recently Used）缓存策略是「最近最少使用淘汰算法」，而 LinkedHashMap 天生支持访问顺序，只需重写 removeEldestEntry() 方法即可实现。

1. 实现原理

afterNodeInsertion()：插入新元素后触发，检查是否需要淘汰最久未使用的元素（链表头部）；
removeEldestEntry()：判断是否淘汰最旧元素，默认返回 false（不淘汰），重写后可根据缓存大小控制。

2. 代码示例：LRU 缓存实现

public class LRUCache <K, V> extends LinkedHashMap<K, V> {
    private final int MAX_CAPACITY;  // 缓存最大容量

    // 构造方法：指定容量和访问顺序
    public LRUCache(int initialCapacity) {
        super(initialCapacity, 0.75f, true);
        this.MAX_CAPACITY = initialCapacity;
    }

    // 重写淘汰策略：当元素数量超过容量时，淘汰最久未使用的元素
    @Override
    protected boolean removeEldestEntry(Map.Entry<K,V> entry){
        return size() > MAX_CAPACITY;
    }

    // 测试
    public static void main(String[] args) {
        LRUCache<String, String> lruCache = new LRUCache<>(3);

        lruCache.put("1", "Java");
        lruCache.put("2", "MySQL");
        lruCache.put("3", "Redis");
        System.out.println("缓存初始化：" + lruCache.keySet()); // [1,2,3]

        // 访问元素 2
        lruCache.get("2");
        System.out.println("访问 2 后：" + lruCache.keySet()); // [1,3,2]

        // 插入新元素 4，触发淘汰（容量3）
        lruCache.put("4", "Spring");
        System.out.println("插入 4 后（淘汰最久未用的1）：" + lruCache.keySet()); // [3,2,4]

        // 访问元素 3，再插入新元素 5
        lruCache.get("3");
        lruCache.put("5", "Docker");
        System.out.println("插入 5 后（淘汰最久未用的2）：" + lruCache.keySet()); // [4,3,5]
    }
}

输出结果：

缓存初始化：[1, 2, 3]
访问 2 后：[1, 3, 2]
插入 4 后（淘汰最久未用的1）：[3, 2, 4]
插入 5 后（淘汰最久未用的2）：[4, 3, 5]

完美实现了 LRU 缓存的核心逻辑：当缓存满时，自动淘汰最久未使用的元素。

五、总结

LinkedHashMap 作为 HashMap 的增强版，核心优势在于「有序性」和「LRU 缓存支持」，总结如下：

继承与结构：继承 HashMap，存储结构为「哈希表 + 双向链表」；
排序方式：

插入顺序（默认）：accessOrder=false，适合需要保留插入顺序的场景；
访问顺序（accessOrder=true）：适合需要按访问频率排序的场景；

LRU 缓存：重写 removeEldestEntry() 即可快速实现，无需手动维护链表；
性能权衡：比 HashMap 多维护双向链表，插入 / 删除略慢，但遍历有序且支持特殊场景。

如果你的业务需要有序映射或简单的 LRU 缓存，LinkedHashMap 绝对是比 HashMap 更优的选择～欢迎在评论区交流你的使用场景和问题，我们下期再见！

Tags:Java

云扬のBlog