LRU Cache Evict方法实现
LRU Cache Evict method implementation
如果我们使用 HashMap 和 DoublyLinkedList 实现 LRU 缓存，实现具有 O(1) 时间复杂度的 evict() 方法的最佳方法是什么？
来自 Java 的 LinkedList 没有公开 Node 类型 （这是一个 private static 内部 class）.
因此您无法在 O(1) 中删除它，因为需要顺序扫描。
要获取 O(1)，您需要能够访问 Node 类型，以便可以在不扫描的情况下将其删除。
你得自己写。幸运的是，doubly linked list 相对容易编写，这是一项非常有益且有趣的任务。
如何删除给定的Node？
参考这个回答：
方法LinkedList.java -> removeNode()删除给定节点，无需顺序扫描。
此答案中的代码适用于单向链表，remove 双向链表在某些情况下甚至更简单。
提示：
- 如果给定的节点是链表的尾节点，那么你还需要前一个节点。
但是那是对于singly linked list，对于doubly linked node，节点本身包含前一个节点，所以你不必将前一个节点传递给removeNode()方法。
顺便说一句
- 为什么有益？
linked list 是最基本的结构 （array 和 bits 除外），其他一些非常基本的结构可以在此基础上构建。
例如 queue 和 stack 都可以用 linked list. 轻松实现
- 并发访问
java.util.LinkedList 不是线程安全的，你的 LRU 可能需要一些并发控制，但我不确定。
如果需要，那么java.util.concurrent.ConcurrentLinkedDeque就是一个很好的例子可以参考。
@更新LinkedHashMap
java.util.LinkedHashMap，是哈希表和双向链表的组合。
机制：
- 它扩展了
HashMap 以获得常见操作的 O(1) 复杂度。
- 并使用
doubly linked list 跟踪插入顺序。
head 是最早的项目，tail 是最新的项目。
它可以用来实现某种缓存，但我不确定它是否完全符合您的要求。
如果我们使用 HashMap 和 DoublyLinkedList 实现 LRU 缓存，实现具有 O(1) 时间复杂度的 evict() 方法的最佳方法是什么？
Java 的 LinkedList 没有公开 Node 类型 （这是一个 private static 内部 class）.
因此您无法在 O(1) 中删除它，因为需要顺序扫描。
要获取 O(1)，您需要能够访问 Node 类型，以便可以在不扫描的情况下将其删除。
你得自己写。幸运的是，doubly linked list 相对容易编写，这是一项非常有益且有趣的任务。
如何删除给定的Node？
参考这个回答：
方法LinkedList.java -> removeNode()删除给定节点，无需顺序扫描。
此答案中的代码适用于单向链表，remove 双向链表在某些情况下甚至更简单。
提示：
- 如果给定的节点是链表的尾节点，那么你还需要前一个节点。
但是那是对于singly linked list，对于doubly linked node，节点本身包含前一个节点，所以你不必将前一个节点传递给removeNode()方法。
顺便说一句
- 为什么有益？
linked list是最基本的结构 （array和bits除外），其他一些非常基本的结构可以在此基础上构建。
例如queue和stack都可以用linked list. 轻松实现
- 并发访问
java.util.LinkedList不是线程安全的，你的 LRU 可能需要一些并发控制，但我不确定。
如果需要，那么java.util.concurrent.ConcurrentLinkedDeque就是一个很好的例子可以参考。
@更新LinkedHashMap
java.util.LinkedHashMap，是哈希表和双向链表的组合。
机制：
- 它扩展了
HashMap以获得常见操作的O(1)复杂度。 - 并使用
doubly linked list跟踪插入顺序。
head是最早的项目，tail是最新的项目。
它可以用来实现某种缓存，但我不确定它是否完全符合您的要求。