是否存在有序的 Map 实现类？如何保证有序？

一、有，分两种"有序"

1. 插入顺序

LinkedHashMap：维护一个双向链表，记录插入顺序。

Map<String, Integer> map = new LinkedHashMap<>();
map.put("a", 1);
map.put("b", 2);
map.put("c", 3);
// 遍历顺序：a, b, c

底层：HashMap + 双向链表。

2. 访问顺序

LinkedHashMap 可以配置为按最近访问顺序排序（LRU 缓存）：

LinkedHashMap<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true);
// 第三个参数 accessOrder = true

每次 get/put 都会把 Entry 移到链表尾部。

3. 排序（按 key 大小）

TreeMap：红黑树，按 key 的自然顺序或 Comparator 排序。

Map<String, Integer> map = new TreeMap<>();
map.put("c", 3);
map.put("a", 1);
map.put("b", 2);
// 遍历顺序：a, b, c（字典序）

二、对比

Map	有序类型	实现
HashMap	无序	数组+链表+红黑树
LinkedHashMap	插入/访问顺序	HashMap + 双向链表
TreeMap	按 key 排序	红黑树
ConcurrentSkipListMap	并发 + 按 key 排序	跳表

三、并发场景

• 需要并发有序：用 ConcurrentSkipListMap。
• 它用跳表（SkipList）实现，并发性能好，比 ConcurrentHashMap 慢但有序。

四、LRU 缓存实现

继承 LinkedHashMap，重写 removeEldestEntry：

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

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

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

高频追问

• LinkedHashMap 的 Entry 比 HashMap.Node 多 before/after 两个指针。
• TreeMap 不是线程安全的，并发用 ConcurrentSkipListMap。