面试题：Java LinkedHashMap访问顺序的底层原理与拓展应用

1. LinkedHashMap实现访问顺序的底层数据结构

LinkedHashMap 继承自 HashMap，在 HashMap 的基础上增加了双向链表的结构来维护插入顺序或访问顺序。每个节点不仅包含 HashMap 节点的基本信息（如键值对、哈希值、下一个节点引用等），还额外包含了前驱和后继节点的引用，以形成双向链表。

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

2. 关键方法分析

get方法

在访问顺序模式下，当调用 get 方法获取一个存在的键值对时，LinkedHashMap 会将对应的节点移到双向链表的尾部，表示该节点是最近访问的。

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}
void afterNodeAccess(Node<K,V> e) { // move node to last
    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;
    }
}

put方法

在插入新键值对时，如果 LinkedHashMap 已满（达到容量 * 加载因子），会先调用 removeEldestEntry 方法判断是否需要移除最久未使用的节点（在双向链表头部）。插入新节点后，若处于访问顺序模式，新插入的节点会被移到双向链表的尾部。

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

3. 基于访问顺序的LRU缓存淘汰策略拓展应用

设计思路

利用 LinkedHashMap 的访问顺序特性，当缓存满时，移除双向链表头部的节点（最久未使用）。通过重写 removeEldestEntry 方法，在插入新节点且缓存已满时，决定是否移除最久未使用的节点。

Java代码实现

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);
        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.keySet()); // 输出: [1, 2, 3]

        cache.get(2);
        System.out.println(cache.keySet()); // 输出: [1, 3, 2]

        cache.put(4, "D");
        System.out.println(cache.keySet()); // 输出: [3, 2, 4]
    }
}

在上述代码中，LRUCache 继承自 LinkedHashMap，并在构造函数中设置 accessOrder 为 true，表示使用访问顺序。重写 removeEldestEntry 方法，当缓存大小超过设定的容量时，移除最久未使用的节点。main 方法演示了 LRUCache 的基本使用。

星途面试题库