04 HashMap和LinkedHashMap有啥区别

首先LinkedHashMap继承于HashMap，所以LinkedHashMap也是HashMap的子类。

1. hashmap的数据结构是数组+单向链表+红黑树，而linkedhashmap的数据结构是数组+双向链表。
2. HashMap的迭代顺序是随机的，LinkedHashMap的迭代顺序是插入顺序
3. 两者查询/插入平均时间复杂度均为 O(1)，但 LinkedHashMap 因维护链表，实际性能略低
4. 哈希冲突严重时，HashMap 可能退化为 O(n)，LinkedHashMap 因链表遍历开销更大

扩展：LinkedHashMap 可通过 accessOrder 参数 切换模式：

默认 false：按插入顺序迭代。
设为 true：按访问顺序排序（最近访问的排在链表尾部），适合实现 LRU 缓存淘汰策略

1

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

高级用法：自动删除最旧条目

LinkedHashMap 可以通过重写 removeEldestEntry() 方法实现自动删除最旧的条目（常用于固定大小的缓存）：

1
2
3
4
5
6
7
8
9
10
11
12

Map<String, Integer> cache = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
        return size() > 3; // 当大小超过 3 时，删除最旧的条目
    }
};

cache.put("A", 1);
cache.put("B", 2);
cache.put("C", 3);
cache.put("D", 4); // 自动删除 "A"
System.out.println(cache); // 输出 {B=2, C=3, D=4}