LinkedHashMap是什么？它有哪些特点？

八股文_Java集合面试题 0 2

参考回答**

LinkedHashMap 是 java.util 包中提供的一个集合类，继承自 HashMap，并实现了 Map 接口。它是一个基于哈希表和双向链表的实现，在保证 HashMap 快速访问的同时，能够维护元素的插入顺序或访问顺序。

LinkedHashMap 的主要特点

有序性：
- 与 HashMap 不同，LinkedHashMap 可以维护元素的顺序。
- 默认情况下，它按 插入顺序 保存键值对。
- 也可以按 访问顺序 保存键值对（通过构造参数 accessOrder = true 设置）。
底层结构：
- LinkedHashMap 基于 哈希表 和 双向链表。
- 哈希表提供快速的键值对存储和查找（时间复杂度为 O(1)）。
- 双向链表维护元素的插入顺序或访问顺序。
允许 null 键和值：
- 和 HashMap 一样，LinkedHashMap 允许最多一个 null 键和多个 null 值。
性能：
- 在查找和插入方面，LinkedHashMap 的性能与 HashMap 基本相当。
- 由于需要维护顺序，LinkedHashMap 的内存开销略高于 HashMap。
线程不安全：
- 和 HashMap 一样，LinkedHashMap 是 非线程安全的。
- 如果需要在多线程环境中使用，可以通过 Collections.synchronizedMap() 包装成线程安全版本。
可重写移除机制：
- LinkedHashMap 提供了一个方法 removeEldestEntry()，可以通过重写该方法来实现自动删除最旧的元素，常用于实现 LRU 缓存（Least Recently Used 缓存）。

LinkedHashMap 的构造方法

LinkedHashMap 提供了以下构造方法：

默认构造方法：

LinkedHashMap<K, V> map = new LinkedHashMap<>();

创建一个默认的空 LinkedHashMap，按插入顺序存储元素。

指定初始容量和负载因子的构造方法：

LinkedHashMap<K, V> map = new LinkedHashMap<>(initialCapacity, loadFactor);

支持访问顺序的构造方法：

LinkedHashMap<K, V> map = new LinkedHashMap<>(initialCapacity, loadFactor, accessOrder);

accessOrder = true：按访问顺序存储元素（最近访问的元素会移动到最后）。
accessOrder = false：按插入顺序存储元素。

示例代码

1. 按插入顺序存储元素

import java.util.LinkedHashMap;

public class LinkedHashMapInsertOrder {
    public static void main(String[] args) {
        LinkedHashMap<Integer, String> map = new LinkedHashMap<>();
        map.put(1, "One");
        map.put(2, "Two");
        map.put(3, "Three");

        System.out.println(map); // 输出：{1=One, 2=Two, 3=Three}
    }
}

2. 按访问顺序存储元素

import java.util.LinkedHashMap;

public class LinkedHashMapAccessOrder {
    public static void main(String[] args) {
        LinkedHashMap<Integer, String> map = new LinkedHashMap<>(16, 0.75f, true);

        map.put(1, "One");
        map.put(2, "Two");
        map.put(3, "Three");

        // 访问元素 2 和 1
        map.get(2);
        map.get(1);

        System.out.println(map); // 输出：{3=Three, 2=Two, 1=One}
    }
}

3. 实现 LRU 缓存

LinkedHashMap 的 removeEldestEntry() 方法允许开发者根据需要移除最旧的元素。通过重写该方法，可以轻松实现 LRU 缓存。

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

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

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true); // accessOrder = 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, "One");
        cache.put(2, "Two");
        cache.put(3, "Three");

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

        // 访问元素 1 和 2
        cache.get(1);
        cache.get(2);

        // 插入新元素
        cache.put(4, "Four");

        System.out.println("Updated Cache: " + cache); // 输出：{3=Three, 1=One, 4=Four}
    }
}

LinkedHashMap 的底层实现

继承自 HashMap：
- LinkedHashMap 的底层仍然是基于 HashMap，但在 HashMap 的基础上增加了一个 双向链表 用于维护顺序。
双向链表：
- 每个节点除了存储键值对（key-value）和哈希值外，还包含两个额外的指针（before 和 after），分别指向前一个节点和后一个节点。
主要改动：
- 在插入、删除、遍历时，LinkedHashMap 会同时操作链表，维护顺序。

LinkedHashMap 的优缺点

优点：

有序性：
- 可以维护插入顺序或访问顺序，适合需要按顺序操作的场景。
性能：
- 在大多数操作中性能与 HashMap 类似，时间复杂度为 O(1)。
易扩展：
- 提供 removeEldestEntry() 方法，可轻松实现缓存功能（如 LRU 缓存）。

缺点：

内存开销较高：
- 由于需要维护双向链表，每个节点需要额外存储两个指针（before 和 after），相比 HashMap 占用更多内存。
线程不安全：
- 与 HashMap 一样，LinkedHashMap 在多线程环境中需要显式同步。

应用场景

按顺序存储数据：
- 如需要维护数据的插入顺序或访问顺序时，LinkedHashMap 是理想选择。
实现缓存：
- 使用 removeEldestEntry() 方法，可以实现基于插入顺序或访问顺序的缓存策略，如 LRU 缓存。
需要有序的遍历：
- 在需要对键值对进行有序遍历时，LinkedHashMap 提供了优于 HashMap 的解决方案。

总结

定义：
- LinkedHashMap 是 HashMap 的子类，能够维护插入顺序或访问顺序。
特点：
- 底层基于哈希表 + 双向链表。
- 默认按插入顺序存储元素，也可按访问顺序存储。
适用场景：
- 需要有序存储或遍历的场景（如 LRU 缓存、按访问顺序排列的数据结构）。
注意事项：
- 内存开销比 HashMap 略高。
- 线程不安全，如需多线程支持，可以通过 Collections.synchronizedMap() 包装。

LinkedHashMap 是在需要 顺序性 和 快速访问 场景下的理想选择，它在性能和功能上结合了 HashMap 和双向链表的优点。