Quartz 4

LinkedHashMap

4 min read

LinkedHashMap 是 Java 集合框架中一个非常实用的 Map 实现类，它在 HashMap 的基础上维护了一个双向链表，用于记录元素的插入顺序或访问顺序。这使得 LinkedHashMap 在保持 HashMap 高效查找性能的同时，具备了可预测的迭代顺序。

一、核心特性

  1. 继承关系

    public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>

  2. 有序性

    • 默认按插入顺序（insertion-order）维护元素。
    • 也可通过构造函数启用访问顺序（access-order），即最近访问的元素排在最后（常用于 LRU 缓存）。

  3. 性能

    • 查找、插入、删除：平均时间复杂度 O(1)（与 HashMap 相同）。
    • 遍历：O(n)，且顺序可预测。

  4. 线程不安全
    与 HashMap 一样，LinkedHashMap 不是线程安全的，多线程环境下需外部同步。

二、关键构造函数

// 默认：按插入顺序
LinkedHashMap()
 
// 指定初始容量和负载因子，按插入顺序
LinkedHashMap(int initialCapacity, float loadFactor)
 
// 指定初始容量、负载因子，并指定是否按访问顺序排序
LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
  • 当 accessOrder = true 时，启用访问顺序（用于 LRU 缓存）。

三、典型应用场景

1. 保持插入顺序的 Map

Map<String, Integer> map = new LinkedHashMap<>();
map.put("apple", 1);
map.put("banana", 2);
map.put("cherry", 3);
 
// 遍历时顺序为：apple → banana → cherry
for (String key : map.keySet()) {
    System.out.println(key);
}

2. 实现 LRU（最近最少使用）缓存

通过重写 removeEldestEntry() 方法，结合 accessOrder = true，可轻松实现 LRU 缓存：

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int MAX_SIZE;
 
    public LRUCache(int maxSize) {
        super(maxSize, 0.75f, true); // accessOrder = true
        this.MAX_SIZE = maxSize;
    }
 
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > MAX_SIZE; // 超过容量时自动移除最旧元素
    }
}
 
// 使用示例
LRUCache<String, String> cache = new LRUCache<>(3);
cache.put("a", "1");
cache.put("b", "2");
cache.put("c", "3");
cache.get("a"); // 访问 "a"，将其移到链表尾部
cache.put("d", "4"); // 此时 "b" 被移除（最久未访问）

四、内部结构简析

  • 在 HashMap 的每个节点（Node）基础上，LinkedHashMap 的节点（Entry）额外维护了 before 和 after 指针，构成双向链表。
  • 无论插入还是访问（当 accessOrder=true），都会调整链表顺序。
  • 遍历时直接按链表顺序迭代，无需哈希桶遍历，因此顺序稳定。

五、与 HashMap 和 TreeMap 对比

特性HashMapLinkedHashMapTreeMap
是否有序❌ 无序✅ 插入/访问顺序✅ 自然/自定义排序
时间复杂度（get/put）O(1)O(1)O(log n)
底层结构哈希表 + 链表/红黑树哈希表 + 双向链表红黑树
是否允许 null 键✅✅❌（键不能为 null）

六、注意事项

  • 启用 accessOrder 后，任何 get()、put() 操作都会改变元素顺序。
  • removeEldestEntry() 默认返回 false，需子类重写以实现自动淘汰。
  • 遍历性能优于 HashMap（因为避免了遍历空桶），但内存开销略高（每个节点多两个指针）。

总结

LinkedHashMap = HashMap 的高效 + 可预测的迭代顺序。
它是实现有序映射和LRU 缓存的理想选择，在需要兼顾性能与顺序的场景中非常实用。

如果你正在设计缓存、配置管理、日志记录等需要“记住操作顺序”的功能，LinkedHashMap 往往是最佳拍档。

Graph View

Backlinks