Java Linkedhashmap

Java LinkedHashMap 是 Java 集合框架中的一个重要类，它继承自 HashMap，并实现了 Map 接口。与 HashMap 不同的是，LinkedHashMap 维护了一个双向链表来记录元素的插入顺序或访问顺序，因此它可以按照插入顺序或访问顺序进行迭代。这使得 LinkedHashMap 在需要有序遍历的场景中非常有用。

概述

LinkedHashMap 是 HashMap 的一个子类，它保留了插入顺序或访问顺序（取决于构造函数的参数）。默认情况下，LinkedHashMap 按照插入顺序维护元素，但也可以通过构造函数设置为按照访问顺序（最近最少使用，LRU）维护元素。

主要特点

• 有序性：可以按照插入顺序或访问顺序迭代元素。
• 性能：提供接近 HashMap 的常数时间性能（O(1)）的基本操作（如 `get` 和 `put`）。
• 可预测的迭代顺序：迭代顺序与插入顺序或访问顺序一致。
• 允许 null 键和 null 值：与 HashMap 类似。

构造函数

LinkedHashMap 提供了多个构造函数：

• `LinkedHashMap()`：创建一个默认容量（16）和加载因子（0.75）的空 LinkedHashMap，按照插入顺序排序。
• `LinkedHashMap(int initialCapacity)`：创建一个指定初始容量的空 LinkedHashMap，按照插入顺序排序。
• `LinkedHashMap(int initialCapacity, float loadFactor)`：创建一个指定初始容量和加载因子的空 LinkedHashMap，按照插入顺序排序。
• `LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)`：创建一个指定初始容量、加载因子和排序模式的 LinkedHashMap。如果 `accessOrder` 为 `true`，则按照访问顺序排序；否则按照插入顺序排序。
• `LinkedHashMap(Map<? extends K, ? extends V> m)`：创建一个包含指定映射的 LinkedHashMap，按照插入顺序排序。

基本操作示例

以下是一个简单的示例，展示如何使用 LinkedHashMap：

import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapExample {
    public static void main(String[] args) {
        // 创建一个 LinkedHashMap，默认按插入顺序排序
        LinkedHashMap<String, Integer> linkedHashMap = new LinkedHashMap<>();

        // 添加元素
        linkedHashMap.put("One", 1);
        linkedHashMap.put("Two", 2);
        linkedHashMap.put("Three", 3);

        // 输出顺序与插入顺序一致
        System.out.println("LinkedHashMap (Insertion Order): " + linkedHashMap);

        // 访问元素 "One"，不会改变顺序（默认情况下）
        linkedHashMap.get("One");

        // 输出顺序仍为插入顺序
        System.out.println("After accessing 'One': " + linkedHashMap);

        // 创建一个按访问顺序排序的 LinkedHashMap
        LinkedHashMap<String, Integer> accessOrderMap = new LinkedHashMap<>(16, 0.75f, true);
        accessOrderMap.put("One", 1);
        accessOrderMap.put("Two", 2);
        accessOrderMap.put("Three", 3);

        // 输出初始顺序
        System.out.println("LinkedHashMap (Access Order Initial): " + accessOrderMap);

        // 访问元素 "One"，会将其移到末尾（最近访问）
        accessOrderMap.get("One");

        // 输出顺序变化
        System.out.println("After accessing 'One': " + accessOrderMap);
    }
}

输出

LinkedHashMap (Insertion Order): {One=1, Two=2, Three=3}
After accessing 'One': {One=1, Two=2, Three=3}
LinkedHashMap (Access Order Initial): {One=1, Two=2, Three=3}
After accessing 'One': {Two=2, Three=3, One=1}

解释

1. 默认情况下，LinkedHashMap 按照插入顺序维护元素，因此迭代顺序与插入顺序一致。 2. 即使访问了某个元素（如 `get("One")`），顺序也不会改变（除非构造函数中设置了 `accessOrder=true`）。 3. 当 `accessOrder=true` 时，每次访问元素（`get` 或 `put`）都会将该元素移到链表的末尾，表示它是最近被访问的。

内部实现

LinkedHashMap 在 HashMap 的基础上增加了一个双向链表来维护顺序。每个节点除了存储键值对外，还包含前驱和后继指针：

graph LR A[HashMap Entry] -->|next| B[HashMap Entry] A -->|before/after| C[LinkedHashMap Entry] C -->|before| D[LinkedHashMap Entry] C -->|after| E[LinkedHashMap Entry]

• HashMap 的节点结构：`Node<K,V>`（包含 `key`, `value`, `hash`, `next`）。
• LinkedHashMap 的节点结构：`Entry<K,V>`（继承自 `Node<K,V>`，并增加 `before` 和 `after` 指针）。

实际应用场景

1. 缓存实现（LRU Cache）

LinkedHashMap 的按访问顺序排序特性使其非常适合实现 LRU（Least Recently Used）缓存。可以通过重写 `removeEldestEntry` 方法来限制缓存大小。

import java.util.LinkedHashMap;
import java.util.Map;

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

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

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

    public static void main(String[] args) {
        LRUCache<String, Integer> cache = new LRUCache<>(3);
        cache.put("A", 1);
        cache.put("B", 2);
        cache.put("C", 3);

        System.out.println("Initial Cache: " + cache);

        // 访问 "A"，使其成为最近使用的
        cache.get("A");

        // 添加新元素，触发移除最久未使用的 "B"
        cache.put("D", 4);

        System.out.println("Cache after adding 'D': " + cache);
    }
}

输出

Initial Cache: {A=1, B=2, C=3}
Cache after adding 'D': {A=1, C=3, D=4}

解释

1. `LRUCache` 继承自 LinkedHashMap，并设置 `accessOrder=true`。 2. 当缓存大小超过 `maxSize` 时，最久未使用的条目会被自动移除。

2. 记录操作顺序

在需要记录用户操作顺序的场景中（如撤销/重做功能），可以使用 LinkedHashMap 来维护操作的历史记录。

性能分析

• 时间复杂度：

 * `get()`、`put()`、`remove()`：平均 O(1)，最坏 O(n)（哈希冲突严重时）。

• 空间复杂度：

 * 比 HashMap 略高，因为需要维护双向链表。

与 HashMap 的比较

特性	LinkedHashMap	HashMap
顺序性	插入顺序或访问顺序	无顺序
性能	略低于 HashMap（因维护链表）	更高
适用场景	需要有序遍历或 LRU 缓存	无需顺序的高效查找

常见问题

1. 如何选择插入顺序或访问顺序？

通过构造函数参数 `accessOrder` 控制：

• `false`（默认）：插入顺序。
• `true`：访问顺序。

2. 如何实现固定大小的缓存？

继承 LinkedHashMap 并重写 `removeEldestEntry` 方法（如 LRU Cache 示例）。

总结

LinkedHashMap 是一个功能强大的有序映射实现，适用于需要有序遍历或 LRU 缓存的场景。它结合了 HashMap 的高效性和链表的顺序性，是 Java 集合框架中不可或缺的一部分。