LinkedHashMap lru实现原理是什么？

### **1. LinkedHashMap 的内部数据结构** `LinkedHashMap` 是基于 `HashMap` 实现的，它扩展了 `HashMap` 的功能，增加了一条维护顺序的双向链表。这个链表的作用是记录元素的插入顺序或访问顺序。 #### 数据结构组成 - **哈希表部分**：继承自 `HashMap`，通过键快速查找值，时间复杂度是 \(O(1)\)。 - **双向链表部分**：在 `HashMap` 的基础上，扩展了 `Entry` 类，增加两个指针 `before` 和 `after`。 ```java static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; // 用于维护双向链表 } ``` - `before`：指向当前节点的前一个节点。 - `after`：指向当前节点的后一个节点。 #### 构造方法 在创建 `LinkedHashMap` 时，可以选择是否按访问顺序排列： ```java public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; } ``` - `accessOrder = true`：按访问顺序排列。 - `accessOrder = false`：按插入顺序排列。 ### **2. 双向链表的维护** #### 插入节点 当向 `LinkedHashMap` 插入新元素时： 1. 新节点被插入到链表的尾部。 2. 链表的指针被更新： - 新节点的 `before` 指向当前链表尾部的节点。 - 新节点的 `after` 为 `null`。 - 当前尾部节点的 `after` 更新为新节点。 #### 访问节点（`accessOrder = true`） 当访问某个节点（如调用 `get` 方法）时： 1. `LinkedHashMap` 会将该节点从当前链表的位置移除。 2. 将该节点重新插入到链表的尾部。 3. 链表的指针调整如下： - 旧位置前后的节点重新连接。 - 访问的节点插入到尾部。 伪代码： ```java void afterNodeAccess(Node<K,V> e) { // 节点被访问后移动到尾部 if (accessOrder) { // 1. 从链表中移除节点 e e.before.after = e.after; if (e.after != null) { e.after.before = e.before; } // 2. 将节点 e 插入到尾部 e.before = tail; e.after = null; if (tail != null) { tail.after = e; } tail = e; } } ``` #### 淘汰节点（LRU 实现） 当调用 `put` 或 `get` 方法后，`LinkedHashMap` 会检查链表头部的节点是否需要被移除： 1. 通过调用 `removeEldestEntry` 方法决定是否淘汰。 2. 如果需要淘汰： - 移除链表头部节点。 - 从哈希表中删除对应的键值对。 ### **3. 具体操作流程** #### `put` 操作 1. 检查键是否已存在： - 如果存在，更新值，并将节点移动到链表尾部（仅当 `accessOrder = true` 时）。 - 如果不存在，创建新节点并插入到链表尾部，同时插入到哈希表中。 2. 调用 `removeEldestEntry`，判断是否需要移除最老的元素。 #### `get` 操作 1. 查找键对应的节点： - 如果找到且 `accessOrder = true`，将该节点移动到链表尾部。 - 如果未找到，返回 `null`。 ### **4. 示例代码解析** 以下是实现一个固定大小的 LRU 缓存的完整代码，并分析其核心步骤。 #### 代码实现 ```java import java.util.LinkedHashMap; import java.util.Map; public class LRUCache<K, V> extends LinkedHashMap<K, V> { private final int maxSize; public LRUCache(int maxSize) { super(16, 0.75f, true); // accessOrder = true，按访问顺序排序 this.maxSize = maxSize; } @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > maxSize; // 当容量超过 maxSize 时移除最老的元素 } public static void main(String[] args) { LRUCache<Integer, String> cache = new LRUCache<>(3); cache.put(1, "A"); // 插入元素 1 cache.put(2, "B"); // 插入元素 2 cache.put(3, "C"); // 插入元素 3 System.out.println(cache); // 输出：{1=A, 2=B, 3=C} cache.get(1); // 访问元素 1，将其移到链表尾部 cache.put(4, "D"); // 插入元素 4，容量超过限制，移除最老的元素 2 System.out.println(cache); // 输出：{3=C, 1=A, 4=D} } } ``` #### 输出结果 ``` {1=A, 2=B, 3=C} {3=C, 1=A, 4=D} ``` #### 操作步骤 1. 初始状态： ``` 双向链表：1 <-> 2 <-> 3 哈希表：{1, 2, 3} ``` 2. 调用 `get(1)`： - 将键 1 的节点从链表中移除并插入到尾部。 ``` 双向链表：2 <-> 3 <-> 1 哈希表：{1, 2, 3} ``` 3. 调用 `put(4, "D")`： - 插入键 4。 - 超过最大容量，调用 `removeEldestEntry`，移除链表头部（键 2）。 ``` 双向链表：3 <-> 1 <-> 4 哈希表：{1, 3, 4} ``` ### **5. 总结实现细节** 1. `LinkedHashMap` 通过双向链表记录顺序（插入顺序或访问顺序）。 2. 每次访问或插入时，会根据 `accessOrder` 移动节点。 3. 淘汰逻辑通过 `removeEldestEntry` 控制，移除链表头部的最老节点。 4. 哈希表提供 O(1) 的查找性能，双向链表保证顺序操作效率高。 这种设计使得 `LinkedHashMap` 实现 LRU 策略的性能高效，且代码简单易用。