解释一下Map集合如何按照访问顺序进行排序？

八股文_Java集合面试题 0 53

参考回答**

在 Java 中，Map 集合如果需要按照访问顺序排序，可以使用 LinkedHashMap。LinkedHashMap 是 HashMap 的一个子类，它除了按照键值对插入顺序排序，还支持按照访问顺序（access order）排序。

LinkedHashMap 的 访问顺序排序 是通过构造函数中的 accessOrder 参数来实现的。当 accessOrder 为 true 时，LinkedHashMap 会将最近访问的元素移动到链表的尾部，从而按照访问的顺序存储键值对。

实现方式

1. 创建按访问顺序排序的 LinkedHashMap

通过 LinkedHashMap 的构造函数指定 accessOrder = true 来实现访问顺序排序。例如：

Map<Integer, String> map = new LinkedHashMap<>(16, 0.75f, true);

2. 操作和排序规则

每次调用 get() 方法或 put() 方法访问某个键时，该键值对会被移动到链表的尾部。
迭代 LinkedHashMap 时，元素将按照最近访问的顺序排列。

代码示例

以下是一个完整的代码示例，展示如何按照访问顺序排序：

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

public class LinkedHashMapAccessOrderExample {
    public static void main(String[] args) {
        // 创建按访问顺序排序的 LinkedHashMap
        Map<Integer, String> map = new LinkedHashMap<>(16, 0.75f, true);

        // 插入键值对
        map.put(1, "A");
        map.put(2, "B");
        map.put(3, "C");

        System.out.println("初始顺序:");
        printMap(map);

        // 访问键 1 和键 3
        map.get(1);
        map.get(3);

        System.out.println("访问键 1 和键 3 后的顺序:");
        printMap(map);

        // 添加新键值对
        map.put(4, "D");

        System.out.println("插入新键值对后的顺序:");
        printMap(map);
    }

    // 打印 Map 内容
    private static void printMap(Map<Integer, String> map) {
        for (Map.Entry<Integer, String> entry : map.entrySet()) {
            System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
        }
        System.out.println();
    }
}

运行结果

初始顺序:
Key: 1, Value: A
Key: 2, Value: B
Key: 3, Value: C

访问键 1 和键 3 后的顺序:
Key: 2, Value: B
Key: 1, Value: A
Key: 3, Value: C

插入新键值对后的顺序:
Key: 2, Value: B
Key: 1, Value: A
Key: 3, Value: C
Key: 4, Value: D

说明

初始顺序为插入的顺序（1 -> 2 -> 3）。
访问了键 1 和键 3 后，它们被移动到尾部（2 -> 1 -> 3）。
插入新键 4 后，新键直接添加到尾部。

详细讲解与原理

1. LinkedHashMap 的结构

LinkedHashMap 通过一个双向链表维护插入顺序或访问顺序。
每次访问或插入元素时，链表会动态调整顺序。

LinkedHashMap 的节点继承自 HashMap.Node，并新增了 before 和 after 指针，用于维护顺序：

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after; // 双向链表的指针
}

2. accessOrder 参数的作用

accessOrder = false：按照插入顺序排列（默认行为）。
accessOrder = true：按照访问顺序排列。

当 accessOrder = true 时，每次访问（get() 或 put()）会调用 LinkedHashMap.afterNodeAccess() 方法，将被访问的节点移动到链表的尾部。

3. 核心方法解析

afterNodeAccess()

用于在访问某个节点时更新顺序。

如果 accessOrder = true，则将访问的节点移动到链表的尾部。

源码：

void afterNodeAccess(Node<K,V> e) { 
   LinkedHashMap.Entry<K,V> last;
   if (accessOrder && (last = tail) != e) {
       LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
       p.after = null;
       if (b == null)
           head = a;
       else
           b.after = a;
       if (a != null)
           a.before = b;
       else
           last = b;
       if (last == null)
           head = p;
       else {
           p.before = last;
           last.after = p;
       }
       tail = p;
       ++modCount;
   }
}

迭代顺序

双向链表保证了迭代时按照链表顺序遍历键值对。
修改链表顺序后，entrySet()、keySet() 和 values() 方法都会按照新的顺序返回元素。

扩展知识

1. LRU 缓存的实现

LinkedHashMap 的按访问顺序排序特性常用于实现 LRU（Least Recently Used）缓存。通过重写 removeEldestEntry() 方法，可以自动移除最近最少使用的元素。

示例：

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, "A");
        cache.put(2, "B");
        cache.put(3, "C");
        System.out.println("初始缓存: " + cache);

        cache.get(1); // 访问键 1
        cache.put(4, "D"); // 插入新键 4，触发移除最老的键 2
        System.out.println("更新缓存: " + cache);
    }
}

输出：

初始缓存: {1=A, 2=B, 3=C}
更新缓存: {3=C, 1=A, 4=D}

总结

要实现按访问顺序排序，可以使用 LinkedHashMap，并通过 accessOrder = true 启用访问顺序模式。
访问顺序排序常用于实现 LRU 缓存和其他需要动态排序的场景。
LinkedHashMap 内部通过双向链表维护顺序，是一种高效且灵活的 Map 实现。