好的，我们来系统地聊一聊 Java 集合框架中的 LinkedHashMap，它是 HashMap 的一个子类，但有自己的特点。

1. 基本概念

LinkedHashMap 继承自 HashMap，内部依旧是基于 哈希表 存储键值对，但额外维护了一条 双向链表 来记录元素的插入顺序或访问顺序。

因此，它既有 HashMap 的 O(1) 查找效率，又能保持一定的顺序性。

2. 特点

特性说明
有序默认按 插入顺序 遍历；也可以按 访问顺序 排列（LRU 缓存基础）。
允许 null 键和值同 HashMap 一样，允许一个 null 键，多个 null 值。
线程不安全多线程需手动同步或用 Collections.synchronizedMap 包装。
性能比 HashMap 略慢（多维护链表指针），但差异很小。

3. 构造方法

// 1. 默认构造
LinkedHashMap<K,V> map = new LinkedHashMap<>();

// 2. 指定初始容量和负载因子
LinkedHashMap<K,V> map = new LinkedHashMap<>(initialCapacity, loadFactor);

// 3. 指定是否按访问顺序排序
LinkedHashMap<K,V> map = new LinkedHashMap<>(16, 0.75f, true);
  • accessOrder = false（默认）：按插入顺序迭代
  • accessOrder = true：按访问顺序迭代（最近访问的放到最后）

4. 内部结构

LinkedHashMap 在 HashMap 的基础上，每个 Entry 节点多了两个指针：

Entry<K,V> before; // 前一个节点
Entry<K,V> after;  // 后一个节点

这两个指针形成一个双向链表，贯穿所有元素，从而保证顺序。

5. 常用方法

put(K key, V value)       // 添加或替换键值对
get(Object key)           // 根据键取值
remove(Object key)        // 删除键值对
clear()                   // 清空
containsKey(Object key)
containsValue(Object value)
size()
isEmpty()

6. 按访问顺序的应用 —— LRU 缓存

LinkedHashMap 有一个可以重写的方法：

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

当 accessOrder = true 且重写此方法时，就能实现 自动删除最老访问的元素。

示例：

import java.util.*;

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

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return size() > capacity;
    }

    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");
        cache.get(1); // 访问 1
        cache.put(4, "D"); // 超出容量，移除最久未访问的 key=2
        System.out.println(cache);
    }
}

输出：

{3=C, 1=A, 4=D}

7. 小结

  • 底层结构：哈希表 + 双向链表
  • 顺序性：支持插入顺序和访问顺序
  • 主要用途：保持有序的 Map、实现 LRU 缓存
  • 缺点：比 HashMap 稍微占用更多内存，速度略慢

好嘞！我用文字和 ASCII 来帮你形象展示一下 LinkedHashMap 的底层结构。

LinkedHashMap 底层结构示意（文字+ASCII）

Hash Table (数组)                     Doubly Linked List (维护顺序)

+---------+                         +---------+ <--> +---------+ <--> +---------+
| Bucket0 | ---> Entry(key1,value1) | Entry1  | <--> | Entry2  | <--> | Entry3  |
+---------+                         +---------+     +---------+     +---------+
| Bucket1 | ---> Entry(key4,value4)
+---------+
| Bucket2 | ---> Entry(key2,value2)
+---------+
| Bucket3 | ---> null
+---------+
  • Hash Table：是一个数组，里面每个元素是一个链表的头节点（Entry），负责快速通过哈希值定位键值对。
  • Entry节点：包含了 key、value、next（哈希链表的下一个Entry）和额外的两个指针before、after，用于双向链表维护顺序。
  • Doubly Linked List：通过 before 和 after 指针，把所有 Entry 按插入顺序（或访问顺序）连接起来，方便遍历时保持顺序。

Entry 类关键字段（简化版）

class Entry<K,V> {
    K key;
    V value;
    Entry<K,V> next;    // 哈希冲突时的链表下一个节点
    Entry<K,V> before;  // 双向链表前一个节点
    Entry<K,V> after;   // 双向链表后一个节点
}

工作流程简述

  1. 新增元素时，根据 key 的 hash 值找到对应桶，挂载在该桶的链表尾部。
  2. 同时，把该 Entry 加入双向链表尾部（维护插入顺序）。
  3. 查询元素时先通过 hash 定位，再遍历桶内链表找到对应 Entry。
  4. 遍历时通过双向链表，从头到尾按插入顺序输出。