1

如果我们使用and来实现LRU缓存，那么实现具有时间复杂度的方法的最佳方法是什么？HashMapDoublyLinkedListevict()O(1)

4

1 回答 1

0

LinkedListfromJava没有暴露Node类型（这是一个private static内部类）。

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

要获取O(1)，您需要能够访问该Node类型，以便无需扫描即可将其删除。

你必须自己写。幸运的是，adoubly linked list相对容易编写，而且是一项非常有益且有趣的任务。

如何删除给定的Node？

参考这个答案：https ://stackoverflow.com/a/54593530

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

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

提示：

  • 如果给定节点是链表中的结束节点，那么您也需要前一个节点。
    但这是 for singly linked list，对于 a doubly linked node，节点本身包含前一个节点，因此您不必将前一个节点传递给该removeNode()方法。

顺便提一句

  • 为什么是有益的？
    linked list是最基本的结构（除了arrayand 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是最新的项目。

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

于 2019-03-03T19:25:00.047 回答