1. 项目背景详细介绍

缓存（Cache）是一种用于临时存储热点数据以加快访问速度的技术。在缓存策略中，最常见的是：

• LRU（Least Recently Used）：淘汰最近最少使用的元素

• MRU（Most Recently Used）：淘汰最近使用过的元素

MRU 缓存策略适合某些特定场景，例如：

• 当某些数据访问频繁但只在短时间内有用

• 数据一旦被访问过，就可能很快不再使用

通过实现 MRUCache，可以深入理解缓存淘汰策略的设计与数据结构选择。

---

2. 项目需求详细介绍

1. 固定容量：缓存容量固定，超过容量时触发淘汰。

2. 缓存操作：支持 get(key) 和 put(key, value)。

3. 淘汰策略：MRU，即最近访问的元素被优先淘汰。

4. 时间复杂度：get 和 put 操作应接近 O(1)。

5. 泛型支持：缓存 key 和 value 可为任意类型。

6. 异常处理：访问不存在的 key 时返回 null 或自定义异常。

---

3. 相关技术详细介绍

• HashMap：存储 key 与节点映射，快速访问元素。

• 双向链表：维护元素访问顺序，方便删除和插入。

• 泛型：支持任意类型 key/value。

• 淘汰逻辑：MRU 缓存需要在每次访问后标记为最近使用，淘汰链表尾部节点（最近使用）。

• 时间复杂度分析：

  • get(key)：O(1)

  • put(key,value)：O(1)
    通过 HashMap + 双向链表实现。

---

4. 实现思路详细介绍

1. 数据结构设计

   • HashMap<K, Node<K,V>>：快速查找 key 对应节点

   • Node<K,V>：双向链表节点，包含 key、value、prev、next

   • 双向链表维护访问顺序，头部表示最久未访问，尾部表示最近访问

2. 访问元素 get(key)

   • 查找 key 对应节点

   • 将节点移动到链表尾部（表示最近访问）

3. 插入元素 put(key,value)

   • 如果 key 已存在，更新 value 并移动到链表尾部

   • 如果 key 不存在，创建新节点插入尾部

   • 如果超过容量，删除尾部节点（MRU 节点）

4. 淘汰策略

   • MRU：淘汰链表尾部节点，即最近访问过的节点

   • LRU 与 MRU 实现类似，只是淘汰位置不同

---

5. 完整实现代码

// 文件: MRUCache.java
// 最近最不常用缓存实现
import java.util.HashMap;

public class MRUCache<K, V> {
    private final int capacity;
    private HashMap<K, Node<K, V>> map;
    private Node<K, V> head; // 双向链表头（最久未访问）
    private Node<K, V> tail; // 双向链表尾（最近访问，MRU）

    // 双向链表节点
    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V> prev;
        Node<K, V> next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    // 构造方法
    public MRUCache(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("容量必须大于0");
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = null;
        this.tail = null;
    }

    // 获取元素
    public V get(K key) {
        Node<K, V> node = map.get(key);
        if (node == null) return null;
        moveToTail(node); // 访问后移动到尾部（最近访问）
        return node.value;
    }

    // 插入或更新元素
    public void put(K key, V value) {
        Node<K, V> node = map.get(key);
        if (node != null) {
            node.value = value;
            moveToTail(node);
        } else {
            node = new Node<>(key, value);
            if (map.size() >= capacity) {
                removeTail(); // 删除 MRU 节点
            }
            appendToTail(node);
            map.put(key, node);
        }
    }

    // 移动节点到尾部
    private void moveToTail(Node<K, V> node) {
        if (node == tail) return;
        removeNode(node);
        appendToTail(node);
    }

    // 删除节点
    private void removeNode(Node<K, V> node) {
        if (node.prev != null) node.prev.next = node.next;
        else head = node.next;

        if (node.next != null) node.next.prev = node.prev;
        else tail = node.prev;
    }

    // 尾部添加节点
    private void appendToTail(Node<K, V> node) {
        node.prev = tail;
        node.next = null;
        if (tail != null) tail.next = node;
        tail = node;
        if (head == null) head = node;
    }

    // 删除尾部节点（MRU）
    private void removeTail() {
        if (tail == null) return;
        map.remove(tail.key);
        removeNode(tail);
    }

    // 打印缓存内容（从头到尾）
    public void printCache() {
        Node<K, V> current = head;
        while (current != null) {
            System.out.print("(" + current.key + ":" + current.value + ") ");
            current = current.next;
        }
        System.out.println();
    }
}

// 文件: MRUCacheTest.java
// 测试类
class MRUCacheTest {
    public static void main(String[] args) {
        MRUCache<Integer, String> cache = new MRUCache<>(3);

        cache.put(1, "A");
        cache.put(2, "B");
        cache.put(3, "C");
        cache.printCache(); // (1:A) (2:B) (3:C)

        cache.get(2);
        cache.printCache(); // (1:A) (3:C) (2:B) 最近访问 2 移动到尾部

        cache.put(4, "D"); // 超过容量，删除 MRU 节点 2
        cache.printCache(); // (1:A) (3:C) (4:D)
    }
}

6. 代码详细解读

• Node<K,V>：双向链表节点，存储 key/value 以及前后指针

• map：HashMap 存储 key -> Node 映射，快速查找节点

• get(K key)：访问节点后移动到尾部（最近使用）

• put(K key,V value)：更新或添加节点，超过容量删除尾部 MRU

• moveToTail(node)：将节点移动到链表尾部

• removeNode(node)：从链表中删除节点

• appendToTail(node)：尾部添加节点

• removeTail()：删除尾部节点并从 map 中移除

• printCache()：调试用，打印缓存当前状态

---

7. 项目详细总结

本项目实现了 MRUCache，核心特点：

1. 双向链表 + HashMap 实现 O(1) 查找和更新

2. MRU 淘汰策略，适合特定访问模式

3. 支持泛型 key/value，通用性强

4. 提供调试打印功能，可观察缓存状态

MRU 与 LRU 结构类似，只是淘汰策略不同。

---

8. 项目常见问题及解答

Q1：为什么用双向链表？
A1：便于删除和移动节点，保证 O(1) 时间复杂度。

Q2：MRU 与 LRU 区别？
A2：MRU 删除最近使用的节点，LRU 删除最久未使用的节点。

Q3：容量超过时为什么删除尾部节点？
A3：链表尾部是最近访问的节点，符合 MRU 淘汰策略。

Q4：get 操作是否会改变淘汰顺序？
A4：是的，访问节点会移动到尾部，标记为最近使用。

---

9. 扩展方向与性能优化

1. 多线程支持：在 put/get 方法中加锁保证线程安全

2. 支持 LRU/MRU 可切换策略：通过接口或策略模式切换

3. 缓存持久化：结合文件或数据库存储热点数据

4. 容量动态调整：根据访问量自动调整缓存容量

5. 弱引用支持：使用 WeakHashMap，防止内存溢出