实现一个带 LRU 淘汰策略的高效缓存：底层数据结构选择（Map + LinkedList）

讲座主题：高效缓存设计与LRU淘汰策略——基于Map与双向链表的实现

各位技术同仁，大家好！

在当今高性能计算和大规模数据处理的时代，如何高效管理数据、提升系统响应速度，是每个开发者和架构师必须面对的核心挑战之一。缓存技术，作为优化数据访问路径、减少后端负载的关键手段，其重要性不言而喻。今天，我们将深入探讨一种广受欢迎且高效的缓存淘汰策略——LRU（Least Recently Used，最近最少使用），并通过剖析其底层数据结构（Map与双向链表）的协同工作机制，亲手实现一个功能完善、性能卓越的LRU缓存。

一、 缓存的本质与LRU策略的必要性

1.1 什么是缓存及其重要性

缓存，顾名思义，是存储数据的临时区域，旨在通过将经常访问的数据存储在访问速度更快、离使用者更近的地方，来提高后续访问的速度。它广泛应用于各种场景，从CPU的L1/L2/L3缓存，到操作系统文件缓存，再到数据库查询缓存、Web服务器的页面缓存，以及分布式系统中的Redis、Memcached等。

缓存带来的核心价值体现在以下几个方面：

• 提升性能：显著减少数据获取时间，降低延迟。
• 减轻后端负载：减少对数据库、远程服务或计算密集型操作的直接请求，保护后端资源。
• 节省带宽：减少网络传输的数据量。

然而，缓存并非万能药。它也伴随着一些固有的挑战：

• 缓存命中率：如何确保缓存中存储的是“有价值”的数据，以最大化命中率？
• 缓存一致性：当原始数据发生变化时，如何保证缓存数据的及时更新？
• 缓存淘汰：当缓存空间不足时，应该移除哪些数据以腾出空间给新数据？这是我们今天讨论的重点。

1.2 缓存淘汰策略与LRU的崛起

由于缓存空间通常是有限的，当缓存满载且需要存储新的数据项时，就必须选择性地移除一些旧数据。这个选择过程遵循的规则，就是缓存淘汰策略。常见的策略包括：

• FIFO (First In, First Out)：最先进入缓存的数据最先被淘汰。简单粗暴，但可能淘汰掉仍然活跃的数据。
• LFU (Least Frequently Used)：访问频率最低的数据被淘汰。需要维护访问计数，且对突发流量不敏感。
• LRU (Least Recently Used)：最近最少使用的数据被淘汰。其核心思想是：如果一个数据项最近被访问过，那么它在未来也很有可能被再次访问；反之，如果一个数据项很长时间没有被访问，那么它在未来被访问的可能性也较低。

LRU策略凭借其直观且高效的特性，在实际应用中表现出色，成为最广泛采用的缓存淘汰算法之一。它的有效性来源于“局部性原理”——程序在一段时间内倾向于访问那些最近访问过的数据和指令。

实现LRU策略的关键在于：我们不仅要存储数据，还要能够追踪每个数据项的“新鲜度”或“访问时间”，并在需要淘汰时，快速找到并移除最不新鲜的那个。

二、 核心数据结构的选择与原理

要高效地实现LRU缓存，我们需要一种数据结构，它能同时满足以下两个关键需求：

1. 快速查找：给定一个键，能够在O(1)平均时间复杂度内找到对应的值。
2. 快速更新访问顺序：当数据被访问或插入时，能够以O(1)时间复杂度将其标记为“最新”，同时在需要淘汰时，快速找到并移除“最旧”的数据。

满足这两个需求的完美组合，正是我们今天要聚焦的——Map（哈希表）与双向链表。

2.1 为何选择Map（哈希表）？

Map，在Java中通常是HashMap，提供了一种键值对的存储机制。其核心优势在于：

• O(1)平均时间复杂度：对于put（插入/更新）、get（查找）和remove（删除）操作，HashMap都能在平均O(1)时间复杂度内完成。这是通过哈希函数将键映射到内部数组的索引来实现的。在理想情况下（哈希冲突少），这些操作的效率极高。
• 存储键值对：缓存天然就是键值对存储的场景，Map完美契合这一需求。

在我们的LRU缓存中，Map将负责存储key到缓存数据项的映射。但这里有一个关键点：Map存储的不是简单的key到value的映射，而是key到我们自定义的“链表节点”的映射。这是因为我们需要通过这个节点来操作链表，从而更新其在链表中的位置。

以下是HashMap的基本使用示例：

import java.util.HashMap;
import java.util.Map;

public class HashMapExample {
    public static void main(String[] args) {
        // 创建一个HashMap，存储String类型的键和Integer类型的值
        Map<String, Integer> scores = new HashMap<>();

        // 插入键值对
        scores.put("Alice", 95);
        scores.put("Bob", 88);
        scores.put("Charlie", 92);

        System.out.println("Alice's score: " + scores.get("Alice")); // 查找
        System.out.println("Map contains Bob? " + scores.containsKey("Bob")); // 检查是否存在

        // 更新值
        scores.put("Alice", 98);
        System.out.println("Alice's updated score: " + scores.get("Alice"));

        // 移除键值对
        scores.remove("Bob");
        System.out.println("Map contains Bob after removal? " + scores.containsKey("Bob"));

        System.out.println("Current map: " + scores);
    }
}

2.2 为何选择双向链表？

双向链表（Doubly Linked List）是维护数据项访问顺序的关键。它的核心特性是：

• O(1)时间复杂度插入和删除：在已知节点的情况下，将一个节点从链表中移除，或在特定位置（如头部或尾部）插入一个节点，都只需要修改少数几个指针，因此可以在O(1)时间复杂度内完成。
• 维护顺序：链表的天然结构决定了其节点是有序的。我们可以将最近访问的节点放在链表头部，将最不经常访问的节点放在链表尾部。
• 双向性：每个节点不仅知道其下一个节点（next），也知道其前一个节点（prev）。这使得我们可以在O(1)时间复杂度内，无论从头部还是尾部，或者从链表中的任意已知节点，进行前向或后向遍历和操作。如果使用单向链表，从链表中删除一个节点时，需要知道其前一个节点，这通常需要从头遍历，导致O(N)的时间复杂度。

在LRU缓存中，双向链表将扮演“访问顺序管理器”的角色。链表的头部将代表最近访问的数据，而尾部则代表最久未访问的数据。

为了方便链表的头尾操作，我们通常会引入两个虚拟节点（或称为哨兵节点）：head和tail。

• head节点：其next指针永远指向链表中第一个真实的数据节点（即最近访问的节点）。
• tail节点：其prev指针永远指向链表中最后一个真实的数据节点（即最久未访问的节点）。

这两个虚拟节点的存在，极大地简化了链表为空、只有一个节点等边界条件的处理，避免了大量的if-else判断。

以下是双向链表节点Node的定义，它将成为我们LRU缓存中存储数据和维护链表关系的载体：

/**
 * 双向链表节点类，用于存储缓存的键值对，并维护链表的前后关系。
 * @param <K> 键的类型
 * @param <V> 值的类型
 */
class Node<K, V> {
    K key;
    V value;
    Node<K, V> prev; // 指向前一个节点
    Node<K, V> next; // 指向下一个节点

    /**
     * 构造函数，创建一个新的节点。
     * @param key 缓存项的键
     * @param value 缓存项的值
     */
    public Node(K key, V value) {
        this.key = key;
        this.value = value;
        this.prev = null; // 初始化时，前后指针为空
        this.next = null;
    }

    @Override
    public String toString() {
        return "(" + key + ", " + value + ")";
    }
}

2.3 Map与双向链表的协同工作机制

现在，让我们清晰地理解Map和双向链表是如何协同工作的：

1. 数据存储与快速查找：

   • Map<K, Node<K, V>> cacheMap;：HashMap负责存储键K到对应Node对象的映射。
   • 当我们需要根据key查找数据时，直接通过cacheMap.get(key)即可在O(1)平均时间复杂度内获取到对应的Node对象。

2. 访问顺序维护与快速淘汰：

   • Node<K, V> head; 和 Node<K, V> tail;：这两个虚拟节点构成了双向链表的头尾。
   • 每次get(key)或put(key, value)操作导致数据被访问或更新时：
     • 首先，从cacheMap中获取到对应的Node。
     • 然后，将这个Node从当前位置移除（O(1)）。
     • 接着，将这个Node添加到链表的头部（O(1)），表示它现在是最新访问的。
   • 当缓存容量达到上限需要淘汰时：
     • 我们直接移除链表尾部的前一个节点（即tail.prev）。这个节点就是最久未使用的。
     • 同时，从cacheMap中移除这个被淘汰节点对应的键值对。这两个操作同样是O(1)。

这种设计巧妙地将HashMap的快速查找能力与双向链表的快速维护顺序能力结合起来，使得LRU缓存的get和put操作都能达到O(1)的平均时间复杂度，这是其高效性的核心所在。

三、 LRU缓存的架构设计

基于上述核心数据结构，我们可以勾勒出LRUCache类的基本架构。它将封装Map和双向链表，并提供外部调用的get和put方法。

import java.util.HashMap;
import java.util.Map;

/**
 * LRUCache 类，实现带LRU淘汰策略的高效缓存。
 * 使用HashMap提供O(1)的查找速度，使用双向链表维护访问顺序和O(1)的插入/删除。
 * @param <K> 缓存键的类型
 * @param <V> 缓存值的类型
 */
public class LRUCache<K, V> {
    private final int capacity; // 缓存的最大容量
    private final Map<K, Node<K, V>> cacheMap; // 存储键到节点的映射，用于快速查找

    // 虚拟头节点和尾节点，简化链表操作
    private final Node<K, V> head;
    private final Node<K, V> tail;

    /**
     * 构造函数，初始化LRU缓存。
     * @param capacity 缓存的最大容量，必须大于0。
     */
    public LRUCache(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("Cache capacity must be greater than 0.");
        }
        this.capacity = capacity;
        this.cacheMap = new HashMap<>();

        // 初始化虚拟头尾节点，并互相连接
        head = new Node<>(null, null); // 虚拟头节点，key和value无实际意义
        tail = new Node<>(null, null); // 虚拟尾节点
        head.next = tail;
        tail.prev = head;
    }

    // -------------------------------------------------------------------------
    // 辅助方法：操作双向链表
    // -------------------------------------------------------------------------

    /**
     * 将一个节点添加到链表头部（即head节点之后）。
     * 这个节点将成为最近访问的节点。
     * @param node 要添加的节点。
     */
    private void addNode(Node<K, V> node) {
        // 新节点的next指向原head.next（即当前第一个真实节点）
        node.next = head.next;
        // 新节点的prev指向head
        node.prev = head;

        // 原head.next的prev指向新节点
        head.next.prev = node;
        // head的next指向新节点
        head.next = node;
    }

    /**
     * 从链表中移除一个节点。
     * @param node 要移除的节点。
     */
    private void removeNode(Node<K, V> node) {
        // 移除节点的操作，实际上是将其前一个节点和后一个节点直接连接起来
        node.prev.next = node.next;
        node.next.prev = node.prev;

        // 清除被移除节点的指针，帮助GC
        node.prev = null;
        node.next = null;
    }

    /**
     * 将一个已存在的节点移动到链表头部。
     * 用于LRU策略中，当节点被访问时更新其新鲜度。
     * @param node 要移动的节点。
     */
    private void moveToHead(Node<K, V> node) {
        removeNode(node); // 先从当前位置移除
        addNode(node);    // 再添加到头部
    }

    /**
     * 移除链表尾部节点（即最久未使用的节点）。
     * 用于缓存满时进行淘汰。
     * @return 被移除节点的键，如果链表为空（只有虚拟头尾节点），则返回null。
     */
    private K removeTail() {
        // 如果链表只有虚拟头尾节点，说明没有真实数据节点
        if (head.next == tail) {
            return null; // 缓存为空
        }
        Node<K, V> nodeToRemove = tail.prev; // 获取尾部的前一个节点（最久未使用的节点）
        removeNode(nodeToRemove); // 从链表中移除
        return nodeToRemove.key; // 返回被移除节点的键
    }

    // -------------------------------------------------------------------------
    // 核心公共方法：get 和 put
    // -------------------------------------------------------------------------

    /**
     * 从缓存中获取指定键的值。
     * 如果键存在，则将对应节点移到链表头部，并返回其值。
     * @param key 缓存项的键。
     * @return 缓存项的值，如果键不存在则返回null。
     */
    public V get(K key) {
        Node<K, V> node = cacheMap.get(key);
        if (node == null) {
            return null; // 键不存在于缓存中
        }
        // 键存在，将其移动到链表头部，表示最近被使用
        moveToHead(node);
        return node.value;
    }

    /**
     * 向缓存中添加或更新一个键值对。
     * 如果键已存在，则更新其值，并将其移到链表头部。
     * 如果键不存在：
     *   1. 创建新节点，添加到链表头部和HashMap中。
     *   2. 如果缓存容量已满，则淘汰链表尾部的节点。
     * @param key 缓存项的键。
     * @param value 缓存项的值。
     */
    public void put(K key, V value) {
        Node<K, V> node = cacheMap.get(key);

        if (node != null) {
            // 键已存在：更新值，并将其移动到链表头部
            node.value = value;
            moveToHead(node);
        } else {
            // 键不存在：
            // 1. 检查容量，如果已满，则淘汰最久未使用的节点
            if (cacheMap.size() >= capacity) {
                K removedKey = removeTail(); // 移除链表尾部的节点
                if (removedKey != null) {
                    cacheMap.remove(removedKey); // 从HashMap中也移除
                    System.out.println("Cache full, evicting: " + removedKey);
                }
            }

            // 2. 创建新节点，并添加到缓存
            Node<K, V> newNode = new Node<>(key, value);
            cacheMap.put(key, newNode); // 添加到HashMap
            addNode(newNode);           // 添加到链表头部
        }
    }

    /**
     * 获取当前缓存中元素的数量。
     * @return 缓存大小。
     */
    public int size() {
        return cacheMap.size();
    }

    /**
     * 打印缓存的当前状态（链表顺序）。
     * 辅助调试用。
     */
    public void printCache() {
        System.out.print("Cache (most recent -> least recent): ");
        Node<K, V> current = head.next;
        while (current != tail) {
            System.out.print(current + " ");
            current = current.next;
        }
        System.out.println();
    }

    // -------------------------------------------------------------------------
    // 内部节点类定义 (为了代码完整性，再次列出，实际可定义在外部或LRUCache内部)
    // -------------------------------------------------------------------------

    /**
     * 双向链表节点类。
     * （在实际项目中，通常定义为LRUCache的私有静态内部类或直接嵌套）
     * 为了本讲座的结构清晰，我们将其定义在外部，并在LRUCache中引用。
     * 在完整的单一文件中，可以直接作为LRUCache的私有静态内部类。
     */
    /*
    static class Node<K, V> {
        K key;
        V value;
        Node<K, V> prev;
        Node<K, V> next;

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

        @Override
        public String toString() {
            return "(" + key + ", " + value + ")";
        }
    }
    */
}

为了保持讲座的逻辑连贯性，我们已经将Node类的定义放在了前面，并在LRUCache中引用。现在，我们将详细展开LRUCache中各个核心辅助方法以及get和put方法的具体实现逻辑。

四、 双向链表节点Node的实现

虽然前面已经给出了Node类的定义，但为了代码的完整性和自包含性，在最终的完整代码中，它通常被定义为LRUCache的一个私有静态内部类。这里我们再次强调其结构和作用。

/**
 * 双向链表节点类，用于存储缓存的键值对，并维护链表的前后关系。
 * 作为LRUCache的内部结构，通常定义为private static。
 * @param <K> 键的类型
 * @param <V> 值的类型
 */
class Node<K, V> {
    K key;
    V value;
    Node<K, V> prev; // 指向前一个节点
    Node<K, V> next; // 指向下一个节点

    /**
     * 构造函数，创建一个新的节点。
     * @param key 缓存项的键
     * @param value 缓存项的值
     */
    public Node(K key, V value) {
        this.key = key;
        this.value = value;
        this.prev = null; // 初始化时，前后指针为空
        this.next = null;
    }

    @Override
    public String toString() {
        return "(" + key + ", " + value + ")";
    }
}

这个Node类是连接HashMap和双向链表的桥梁。HashMap存储的不再是原始的value，而是封装了key、value以及prev/next指针的Node对象。通过存储Node对象，我们可以在O(1)时间内找到数据，并通过Node对象直接在链表中进行O(1)的增删改操作。

五、 核心辅助操作的实现

这几个辅助方法是操作双向链表的基础，它们确保了链表结构总是正确的，并且所有操作都能在O(1)时间复杂度内完成。

5.1 addNode(Node<K, V> node): 将节点添加到链表头部

此方法用于将一个节点（无论是新创建的还是从链表其他位置移动过来的）插入到虚拟头节点head之后，使其成为链表中最新的元素。

逻辑分解：

1. 新节点的next指针指向当前head的next节点（即原链表的第一个真实节点）。
2. 新节点的prev指针指向head节点。
3. 原head的next节点的prev指针更新为新节点。
4. head的next指针更新为新节点。

通过这四步指针操作，新节点被“夹”在head和原head.next之间，成为新的链表头。

    /**
     * 将一个节点添加到链表头部（即head节点之后）。
     * 这个节点将成为最近访问的节点。
     * @param node 要添加的节点。
     */
    private void addNode(Node<K, V> node) {
        // 步骤1: 将新节点的next指向原head.next（即当前第一个真实节点）
        node.next = head.next;
        // 步骤2: 将新节点的prev指向head
        node.prev = head;

        // 步骤3: 原head.next（即当前第一个真实节点）的prev指向新节点
        head.next.prev = node;
        // 步骤4: head的next指向新节点
        head.next = node;
    }

5.2 removeNode(Node<K, V> node): 从链表中移除指定节点

此方法用于将一个节点从双向链表中移除。由于双向链表的特性，我们只需要知道要移除的节点本身，就可以完成移除操作，无需从头遍历。

逻辑分解：

1. 要移除节点的prev节点的next指针，更新为指向要移除节点的next节点。
2. 要移除节点的next节点的prev指针，更新为指向要移除节点的prev节点。
3. （可选但推荐）将被移除节点的prev和next指针置为null，帮助垃圾回收。

    /**
     * 从链表中移除一个节点。
     * @param node 要移除的节点。
     */
    private void removeNode(Node<K, V> node) {
        // 步骤1: 将被移除节点的前一个节点的next指针指向被移除节点的next节点
        node.prev.next = node.next;
        // 步骤2: 将被移除节点的后一个节点的prev指针指向被移除节点的prev节点
        node.next.prev = node.prev;

        // 步骤3 (可选但推荐): 清除被移除节点的指针，帮助GC
        node.prev = null;
        node.next = null;
    }

5.3 moveToHead(Node<K, V> node): 将节点移至链表头部

这是LRU策略的核心操作之一。当一个缓存项被访问时，无论它是通过get还是put操作，我们都应该将其标记为“最近使用”，即将其移动到链表头部。

逻辑分解：

1. 调用removeNode(node)，将该节点从其当前位置移除。
2. 调用addNode(node)，将该节点添加到链表头部。

    /**
     * 将一个已存在的节点移动到链表头部。
     * 用于LRU策略中，当节点被访问时更新其新鲜度。
     * @param node 要移动的节点。
     */
    private void moveToHead(Node<K, V> node) {
        removeNode(node); // 先从当前位置移除
        addNode(node);    // 再添加到头部
    }

5.4 removeTail(): 移除链表尾部节点

当缓存容量达到上限，需要淘汰最久未使用的元素时，我们通过此方法移除链表尾部的前一个节点。

逻辑分解：

1. 检查链表是否为空（即head.next是否直接指向tail）。如果为空，则无可移除节点，返回null。
2. 获取tail.prev，这就是最久未使用的真实数据节点。
3. 调用removeNode()方法将其从链表中移除。
4. 返回被移除节点的key，以便于从cacheMap中也移除对应的映射。

    /**
     * 移除链表尾部节点（即最久未使用的节点）。
     * 用于缓存满时进行淘汰。
     * @return 被移除节点的键，如果链表为空（只有虚拟头尾节点），则返回null。
     */
    private K removeTail() {
        // 如果链表只有虚拟头尾节点，说明没有真实数据节点
        if (head.next == tail) {
            return null; // 缓存为空
        }
        Node<K, V> nodeToRemove = tail.prev; // 获取尾部的前一个节点（最久未使用的节点）
        removeNode(nodeToRemove); // 从链表中移除
        return nodeToRemove.key; // 返回被移除节点的键
    }

通过这些辅助方法，我们构建了强大的链表操作基础，使得后续get和put的核心逻辑变得简洁而高效。

六、 get方法的详细实现

get方法是LRU缓存读取数据的入口。它的核心职责是：

1. 根据key查找数据。
2. 如果找到数据，则更新其在链表中的位置（移到头部）。
3. 返回数据。

逻辑分解：

1. 首先，通过cacheMap.get(key)尝试从HashMap中获取对应的Node对象。
2. 如果node为null，说明key不存在于缓存中，直接返回null。
3. 如果node不为null，说明找到了数据。根据LRU策略，这个数据现在是“最近使用”的，所以需要调用moveToHead(node)将其移动到链表的头部。
4. 最后，返回node中存储的value。

    /**
     * 从缓存中获取指定键的值。
     * 如果键存在，则将对应节点移到链表头部，并返回其值。
     * @param key 缓存项的键。
     * @return 缓存项的值，如果键不存在则返回null。
     */
    public V get(K key) {
        Node<K, V> node = cacheMap.get(key);
        if (node == null) {
            // 缓存中不存在该键
            return null;
        }
        // 键存在，将其移动到链表头部，表示最近被使用
        moveToHead(node);
        return node.value;
    }

get操作的时间复杂度：

• cacheMap.get(key)：O(1)平均时间复杂度。
• moveToHead(node)：由removeNode和addNode组成，都是O(1)时间复杂度。
  因此，get方法的整体平均时间复杂度为O(1)。

七、 put方法的详细实现

put方法是LRU缓存写入或更新数据的入口。它的逻辑相对复杂，需要处理两种情况：键已存在和键不存在。当键不存在时，还要考虑缓存容量是否已满，进而触发淘汰机制。

逻辑分解：

1. 尝试查找键：首先，通过cacheMap.get(key)尝试查找key是否已存在于缓存中。

2. 情况一：键已存在 (node != null)

   • 更新值：如果key已存在，说明要更新该缓存项的值。直接修改node.value = value。
   • 更新新鲜度：因为数据被访问（更新也是一种访问），所以调用moveToHead(node)将其移动到链表头部。

3. 情况二：键不存在 (node == null)

   • 容量检查与淘汰：
     • 在添加新节点之前，需要检查当前缓存的大小cacheMap.size()是否已达到capacity。
     • 如果cacheMap.size() >= capacity，说明缓存已满，需要执行淘汰策略。调用removeTail()方法移除链表尾部的节点。removeTail()会返回被移除节点的key。
     • 使用这个key从cacheMap中移除对应的键值对：cacheMap.remove(removedKey)。
     • 为了调试和演示，可以打印一条淘汰信息。
   • 创建新节点并添加：
     • 创建一个新的Node<K, V> newNode = new Node<>(key, value)。
     • 将新节点添加到cacheMap中：cacheMap.put(key, newNode)。
     • 将新节点添加到链表头部：addNode(newNode)。

    /**
     * 向缓存中添加或更新一个键值对。
     * 如果键已存在，则更新其值，并将其移到链表头部。
     * 如果键不存在：
     *   1. 创建新节点，添加到链表头部和HashMap中。
     *   2. 如果缓存容量已满，则淘汰链表尾部的节点。
     * @param key 缓存项的键。
     * @param value 缓存项的值。
     */
    public void put(K key, V value) {
        Node<K, V> node = cacheMap.get(key);

        if (node != null) {
            // 情况一：键已存在
            // 更新节点的值
            node.value = value;
            // 将节点移动到链表头部，表示最近被使用
            moveToHead(node);
        } else {
            // 情况二：键不存在
            // 1. 检查缓存容量，如果已满，则淘汰最久未使用的节点
            if (cacheMap.size() >= capacity) {
                K removedKey = removeTail(); // 移除链表尾部的节点（最久未使用的）
                if (removedKey != null) {
                    cacheMap.remove(removedKey); // 从HashMap中也移除对应项
                    System.out.println("Cache full, evicting: " + removedKey);
                }
            }

            // 2. 创建新节点
            Node<K, V> newNode = new Node<>(key, value);
            // 将新节点添加到HashMap
            cacheMap.put(key, newNode);
            // 将新节点添加到链表头部
            addNode(newNode);
        }
    }

put操作的时间复杂度：

• cacheMap.get(key)：O(1)平均时间复杂度。
• moveToHead(node)：O(1)时间复杂度。
• removeTail()：O(1)时间复杂度。
• cacheMap.remove(removedKey)：O(1)平均时间复杂度。
• cacheMap.put(key, newNode)：O(1)平均时间复杂度。
• addNode(newNode)：O(1)时间复杂度。
  因此，put方法的整体平均时间复杂度为O(1)。

八、 性能分析与复杂性

通过Map与双向链表的巧妙结合，我们实现的LRU缓存具有非常优秀的性能特性：

8.1 时间复杂度

操作	时间复杂度 (平均)	说明	get操作	O(1)平均时空复杂度	HashMap的get操作为O(1)平均，双向链表操作（removeNode和addNode）为O(1)。 `
get(key)	O(1) 平均	HashMap查找为O(1)，链表操作（removeNode和addNode）为O(1)。所有操作都是常数时间。