本文共 2327 字，大约阅读时间需要 7 分钟。

LinkedHashMap 是 Java 集成类框架中非常有用的类之一，它不仅继承自 HashMap，而且额外实现了按访问顺序存储元素的特性。这种特性使得它在实现 Least Recently Used (LRU) 缓存策略中非常有用。

简介

LinkedHashMap 是一个 hybrid 数据结构，它结合了 HashMap 和 LinkedList 的优点。它能够在哈希表（HashMap）的基础上，通过维护双向链表的结构，确保元素可以按插入顺序或者按访问顺序遍历。这种结构在存储和访问速度之间提供了更好的平衡。

继承体系

LinkedHashMap 继承自 HashMap 所有特性，包括一致性、容斥、稀疏和平衡加载等。同时，它额外引入了通过双向链表实现的元素存储顺序特性。这种特性使得它不仅可以像 HashMap 那样快速访问元素，还可以像 LinkedHashSet 那样提取元素的插入或访问顺序。

存储结构

与 HashMap 的存储结构不同，LinkedHashMap 不仅维护了传统的 ([array][table]) + [single linked list] + [红黑树] 的结构，还外加了一个双向链表来维护元素的访问顺序。这种设计使得它既能快速随机访问元素，又能顺序遍历元素，适用于场景需要同时保证快速访问和元素顺序输出。

源码解析

LinkedHashMap 的核心在于其内部类的设计和一些关键钩子的实现。

属性

• head：双向链表的头节点。
• tail：双向链表的尾节点。
• accessOrder：布尔值，表明是否根据访问顺序存储元素。默认为 false，表示按照插入顺序存储；若为 true，则表示按照访问顺序存储。这种特性是实现 LRU 策略的关键。

内部类

• Entry：内部类 extends HashMap.Node，用于存储键值对，同时维护双向链表的 before 和 after 元素。

构造方法

前四个构造方法默认 accessOrder 为 false，表示按照插入顺序存储元素。最后一个构造方法 public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) 接受 accessOrder 参数，用于指定存储顺序特性。

双向链表操作

• afterNodeInsertion：在节点插入后调用，用于移除最老的元素（用于 LRU 策略）。
• afterNodeAccess：在节点访问后调用，用于将访问到的节点移到双向链表的末尾。
• afterNodeRemoval：在节点删除后调用，用于维护双向链表结构。

LRU 缓存策略实现

要实现 LRU，主要通过以下方式：

实现示例

以下是一个简单的 LRU 测试类：

package com.coolcoding.code;import java.util.LinkedHashMap;import java.util.Map;public class LRUTest {    public static void main(String[] args) {        LRU lru = new LRU(5, 0.75f);        lru.put(1, 1);        lru.put(2, 2);        lru.put(3, 3);        lru.put(4, 4);        lru.put(5, 5);        lru.put(6, 6);        lru.put(7, 7);        System.out.println(lru.get(4));  // 输出: 4        lru.put(6, 666);        System.out.println(lru);    }}class LRU
   
     extends LinkedHashMap
    
      {    private int capacity;    public LRU(int capacity, float loadFactor) {        super(capacity, loadFactor, true);        this.capacity = capacity;    }    @Override    protected boolean removeEldestEntry(Map.Entry
     
       eldest) {        return size() > this.capacity;    }}
     
    
   

总结

LinkedHashMap 几乎完全可以替代传统的 HashMap，但它的核心特性在于其双向链表的实现。这种结构使得它能够实现按插入或访问顺序存储元素的需求，同时通过 plugin机制 (钩子) 完成 Esspecialized behavior 的实现。默认情况下，它不会移除最旧的元素，但可以通过重写 removeEldestEntry 方法实现自定义的 LRU 策略。