当前位置：首页 > article >正文

Java 中 LinkedHashMap 的底层数据结构及相关分析

article 2025/3/22 2:45:56

Java 中 LinkedHashMap 的底层数据结构及相关分析

在 Java 中，LinkedHashMap 是 HashMap 的子类，它保留了键值对的插入顺序或访问顺序。本文将深入讲解 LinkedHashMap 的底层数据结构、实现原理、应用场景、优缺点、替代方案，并提供实际使用案例。

1. `LinkedHashMap` 的底层数据结构

LinkedHashMap 继承自 HashMap，其底层数据结构是在 HashMap 的基础上，增加了一个双向链表，以维护元素的插入顺序或访问顺序。其核心组成部分包括：

哈希表（数组 + 链表 + 红黑树）
- LinkedHashMap 仍然使用 HashMap 的哈希表存储键值对。
- 当哈希冲突发生时，JDK 1.8 采用链表 + 红黑树的结构来优化查找性能。
双向链表
- LinkedHashMap 通过一个双向链表维护插入顺序或访问顺序。
- 每个 Entry<K, V> 结构体不仅包含 key、value，还包含 before 和 after 指针，分别指向前一个和后一个节点。

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

2. `LinkedHashMap` 的实现原理

2.1 插入顺序维护

默认情况下，LinkedHashMap 维护插入顺序，即元素按 put 的顺序排列。例如：

LinkedHashMap<Integer, String> map = new LinkedHashMap<>();
map.put(3, "C");
map.put(1, "A");
map.put(2, "B");

System.out.println(map); // {3=C, 1=A, 2=B}

2.2 访问顺序维护

通过构造方法的 accessOrder 参数，可以启用**LRU（最近最少使用）**模式：

LinkedHashMap<Integer, String> lruCache = new LinkedHashMap<>(16, 0.75f, true);

当 accessOrder=true 时，每次访问某个键，该键会被移动到链表末尾，使最近访问的元素保持在后面。
这在缓存场景中非常有用。

示例代码：

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

lruCache.get(1); // 访问键 1，使其移动到末尾
System.out.println(lruCache); // {2=B, 3=C, 1=A}

2.3 `removeEldestEntry` 方法

LinkedHashMap 允许重写 removeEldestEntry 方法，以实现自动清理旧数据（如 LRU 缓存策略）。

示例：限制缓存最大容量为 3，超过 3 时自动移除最早插入的元素。

LinkedHashMap<Integer, String> cache = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {
        return size() > 3; // 超过 3 个元素时，删除最老的元素
    }
};
cache.put(1, "A");
cache.put(2, "B");
cache.put(3, "C");
cache.put(4, "D"); // 触发删除最老的 1=A
System.out.println(cache); // {2=B, 3=C, 4=D}

3. `LinkedHashMap` 的应用场景

LRU 缓存（Least Recently Used）
- 通过 accessOrder=true 和 removeEldestEntry 方法实现 LRU 缓存。
按插入顺序遍历数据
- 例如：日志存储，要求按照写入顺序读取。
需要有序性的 HashMap
- HashMap 无序，TreeMap 按 key 排序，而 LinkedHashMap 保证插入顺序。

4. `LinkedHashMap` 的优缺点

✅ 优点

有序性：支持插入顺序和访问顺序，适用于 LRU 缓存等场景。
遍历效率高：由于链表结构，迭代比 HashMap 高效，特别是对于大量数据。
兼容 HashMap：继承 HashMap，大部分 API 一致，易于替换。

❌ 缺点

内存占用较大：比 HashMap 额外增加了双向链表的指针开销。
插入和删除性能略低：由于维护链表结构，插入和删除比 HashMap 稍慢。
不支持并发：不是线程安全的，如需并发请使用 Collections.synchronizedMap 或 ConcurrentHashMap。

5. `LinkedHashMap` 的替代方案

替代方案	适用场景
`HashMap`	需要无序键值映射，查询性能好，且不关注插入顺序。
`TreeMap`	需要按 Key 自然排序的映射，基于红黑树，适合范围查找。
`ConcurrentHashMap`	多线程环境下的高并发映射，牺牲了顺序性，但提升了并发性能。
`LRUCache`（Guava/自定义）	需要更高效的 LRU 缓存管理，可考虑 `Guava Cache` 或 `LinkedHashMap` 自定义实现。

6. `LinkedHashMap` 典型案例

6.1 按插入顺序存储配置项

LinkedHashMap<String, String> config = new LinkedHashMap<>();
config.put("username", "admin");
config.put("password", "123456");
config.put("url", "jdbc:mysql://localhost:3306/test");

for (Map.Entry<String, String> entry : config.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}
// 输出：username -> password -> url

6.2 LRU 缓存实现

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 class Main {
    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"); // 淘汰最久未访问的 2
        System.out.println(cache); // {3=C, 1=A, 4=D}
    }
}