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