在 Java 集合框架中，LinkedHashMap 是 HashMap 的“有序版本”。它继承了 HashMap 的所有特性，同时通过维护一个双向链表来记录元素的插入顺序或访问顺序。这使得 LinkedHashMap 既能保证 O(1) 的存取性能，又能按顺序遍历。

本文将深入剖析 LinkedHashMap 的底层实现、核心机制、典型应用场景，并通过源码分析和流程图帮助你彻底掌握这个“有序哈希表”。

1. LinkedHashMap 概述

1.1 继承体系

1.2 核心特性

1.3 两种顺序模式

2. 底层数据结构

2.1 核心结构图

2.2 节点定义

// LinkedHashMap 的节点（继承自 HashMap.Node）
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);
    }
}

一个节点同时存在于两个结构中：

3. 两种顺序模式详解

3.1 插入顺序模式（默认）

// 默认构造器：accessOrder = false
LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
map.put("A", 1);
map.put("B", 2);
map.put("C", 3);

// 遍历顺序：A → B → C（插入顺序）
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey());
}

双向链表状态变化：

3.2 访问顺序模式（LRU 缓存）

// 指定 accessOrder = true
LinkedHashMap<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true);
map.put("A", 1);
map.put("B", 2);
map.put("C", 3);

map.get("B");  // 访问 B，B 移到尾部

// 遍历顺序：A → C → B（最近访问的 B 在最后）
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey());
}

访问顺序变化过程：

4. 核心源码解析

4.1 节点创建时的链表维护

// HashMap 中的 newNode 方法（LinkedHashMap 重写）
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
    Entry<K,V> p = new Entry<>(hash, key, value, next);
    linkNodeLast(p);  // 关键：将新节点链接到双向链表尾部
    return p;
}

// 将节点添加到双向链表尾部
private void linkNodeLast(Entry<K,V> p) {
    Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

4.2 访问顺序维护（核心）

// LinkedHashMap 重写的 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;
}

// 将节点移动到链表尾部
void afterNodeAccess(Node<K,V> e) {
    Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        Entry<K,V> p = (Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        // 从链表中移除 p
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        // 将 p 添加到尾部
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

4.3 删除时的链表维护

// 从双向链表中移除节点
void afterNodeRemoval(Node<K,V> e) {
    Entry<K,V> p = (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;
}

5. 实现 LRU 缓存

5.1 核心：removeEldestEntry 方法

// 默认返回 false，不移除最老元素
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

// 重写此方法可实现 LRU 缓存淘汰

5.2 完整 LRU 缓存实现

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxCapacity;
    
    public LRUCache(int maxCapacity) {
        // 初始容量、负载因子、accessOrder=true（访问顺序）
        super(maxCapacity, 0.75f, true);
        this.maxCapacity = maxCapacity;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // 当大小超过最大容量时，移除最老的元素
        return size() > maxCapacity;
    }
    
    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3);
        cache.put(1, "A");
        cache.put(2, "B");
        cache.put(3, "C");
        System.out.println(cache.keySet());  // [1, 2, 3]
        
        cache.get(2);  // 访问 2，2 变为最近使用
        cache.put(4, "D");  // 触发淘汰，移除最老的 1
        
        System.out.println(cache.keySet());  // [3, 2, 4]
    }
}

5.3 LRU 淘汰流程

6. 遍历性能

6.1 遍历方式对比

LinkedHashMap<String, Integer> map = new LinkedHashMap<>();

// ✅ 高效：利用双向链表顺序遍历
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    // 时间复杂度 O(n)，直接遍历链表
}

// ✅ 高效：keySet 同样维护顺序
for (String key : map.keySet()) {
    // 按顺序遍历
}

6.2 与 HashMap 遍历对比

7. 与其他 Map 的对比

8. 典型应用场景

8.1 场景一：保持插入顺序

// 需要按添加顺序存储配置项
LinkedHashMap<String, String> config = new LinkedHashMap<>();
config.put("db.url", "jdbc:mysql://localhost:3306/test");
config.put("db.user", "root");
config.put("db.password", "123456");
config.put("cache.size", "100");

// 按顺序输出配置（便于阅读）
for (Map.Entry<String, String> entry : config.entrySet()) {
    System.out.println(entry.getKey() + "=" + entry.getValue());
}

8.2 场景二：LRU 缓存

// 实现一个简单的 LRU 缓存
public class SimpleCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;
    
    public SimpleCache(int maxSize) {
        super(maxSize, 0.75f, true);
        this.maxSize = maxSize;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }
}

// 使用示例
SimpleCache<String, Data> cache = new SimpleCache<>(1000);
Data data = cache.computeIfAbsent(key, k -> loadFromDatabase(k));

8.3 场景三：构建 JSON 对象

// 保持字段顺序的 JSON 构建器
public class OrderedJsonBuilder {
    private LinkedHashMap<String, Object> map = new LinkedHashMap<>();
    
    public OrderedJsonBuilder put(String key, Object value) {
        map.put(key, value);
        return this;
    }
    
    public String build() {
        return new JSONObject(map).toString();
    }
}

// 输出字段按添加顺序
new OrderedJsonBuilder()
    .put("name", "张三")
    .put("age", 25)
    .put("city", "北京")
    .build();
// {"name":"张三","age":25,"city":"北京"}

9. 性能与内存分析

9.1 内存占用对比

// 存储 100 万个元素
HashMap:    约 72MB（16字节节点 + 引用）
LinkedHashMap: 约 104MB（额外 32 字节 before/after）
额外开销：约 45%

9.2 性能测试

结论：LinkedHashMap 的 put/get 略慢（维护链表开销），但遍历更快（跳过空桶）。

10. 常见面试追问

Q1：LinkedHashMap 如何保证有序？

A：通过维护一个双向链表。每个节点除了哈希桶的 next 指针外，还有 before 和 after 指针，连接成全局链表，记录插入或访问顺序。

Q2：accessOrder 模式有什么实际用途？

A：实现 LRU（Least Recently Used）缓存。当设置为 true 时，每次访问会将节点移到尾部，最早访问的节点自然沉到头部，结合 removeEldestEntry 可实现自动淘汰。

Q3：LinkedHashMap 和 TreeMap 的区别？

A：

• LinkedHashMap：按插入顺序或访问顺序，基于哈希表，O(1)
• TreeMap：按自然顺序或自定义 Comparator，基于红黑树，O(log n)

Q4：LinkedHashMap 是线程安全的吗？

A：不是。多线程环境需要使用 Collections.synchronizedMap 包装或使用 ConcurrentHashMap（但 ConcurrentHashMap 不保证顺序）。

11. 核心要点总结

12. 一句话记忆

LinkedHashMap = HashMap + 双向链表，按序存储访问快；accessOrder 可选 LRU，重写淘汰方法实现缓存。

口诀：

链表哈希相结合，插入访问顺序确。
before after 双指针，全局链表穿成列。
遍历只走有数据，性能优于哈希表。
访问顺序模式妙，最近使用在末梢。
重写淘汰老元素，LRU 缓存轻松造。

如果你彻底搞懂了 LinkedHashMap 的原理和应用，欢迎点赞、收藏、转发！有任何疑问，评论区一起交流~