编辑“︁Java Linkedhashmap”︁

{{Java集合框架}}

'''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'''：

<syntaxhighlight lang="java">
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);
    }
}
</syntaxhighlight>

=== 输出 ===
<pre>
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}
</pre>

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

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

<mermaid>
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]
</mermaid>

* '''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` 方法来限制缓存大小。

<syntaxhighlight lang="java">
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);
    }
}
</syntaxhighlight>

=== 输出 ===
<pre>
Initial Cache: {A=1, B=2, C=3}
Cache after adding 'D': {A=1, C=3, D=4}
</pre>

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

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

== 性能分析 ==
* '''时间复杂度'''：
  * `get()`、`put()`、`remove()`：平均 O(1)，最坏 O(n)（哈希冲突严重时）。
* '''空间复杂度'''：
  * 比 [[HashMap]] 略高，因为需要维护双向链表。

== 与 HashMap 的比较 ==
{| class="wikitable"
|-
! 特性 !! LinkedHashMap !! HashMap
|-
| 顺序性 || 插入顺序或访问顺序 || 无顺序
|-
| 性能 || 略低于 HashMap（因维护链表） || 更高
|-
| 适用场景 || 需要有序遍历或 LRU 缓存 || 无需顺序的高效查找
|}

== 常见问题 ==
=== 1. 如何选择插入顺序或访问顺序？ ===
通过构造函数参数 `accessOrder` 控制：
* `false`（默认）：插入顺序。
* `true`：访问顺序。

=== 2. 如何实现固定大小的缓存？ ===
继承 '''LinkedHashMap''' 并重写 `removeEldestEntry` 方法（如 LRU Cache 示例）。

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

{{Java集合框架}}

[[Category:编程语言]]
[[Category:Java]]
[[Category:Java集合框架]]