java - LRU Cache Evict方法实现

Question

如果我们使用HashMap 和DoublyLinkedList 实现LRU 缓存，实现evict()< 的最佳方法是什么 时间复杂度为 O(1) 的方法？

Answer 1

Java 的

LinkedList 没有公开 Node 类型 (这是一个 private static内部类)。

所以你不能在 O(1) 中删除它，因为需要顺序扫描。

要获得 O(1)，您需要能够访问 Node 类型，以便可以在不扫描的情况下将其删除。

你必须自己写。幸运的是，双向链表 相对容易编写，而且这是一项非常有益且有趣的任务。

---

如何删除给定的节点？

引用这个答案:https://stackoverflow.com/a/54593530

LinkedList.java 方法 -> removeNode() 移除给定节点，无需顺序扫描。

此答案中的代码适用于单链表，在某些情况下，双向链表的 remove 甚至更简单。

提示:

• 如果给定的节点是链表的尾节点，那么还需要前一个节点。
  但这是针对单向链表，对于双向链表，节点本身包含前一个节点，因此您不必将前一个节点传递给 removeNode() 方法。

---

顺便说一下

• 为什么有益？
  链表是最基本的结构(除了array和bits)，其他一些非常基本的结构可以构建基于.
  例如，queue 和 stack 都可以使用 linked list 轻松实现。
• 并发访问
  java.util.LinkedList 不是线程安全的，您的 LRU 可能需要一些并发控制，但我不确定。
  如果需要，java.util.concurrent.ConcurrentLinkedDeque 是一个很好的引用示例。

---

@Update LinkedHashMap

java.util.LinkedHashMap，是哈希表和双向链表的组合。

机制:

• 它扩展了 HashMap 以获得普通操作的 O(1) 复杂度。
• 并使用双向链表来跟踪插入顺序。
  head 是最旧的项目，tail 是最新的项目。

它可以用来实现某种缓存，但我不确定它是否完全符合您的要求。