具有单链表的LRU缓存

Question

大多数LRU缓存教程强调组合使用双向链表和字典。字典保存该值和对链表上相应节点的引用。

当我们执行删除操作时，我们从字典中的链表中查找节点，我们必须将其删除。

现在这里是它变得奇怪的地方。大多数教程认为，我们需要前面的节点才能从链表中删除当前节点。这样做是为了获得O（1）时间。

但是，这里有一种方法可以在O（1）时间内从单链接列表中删除节点。我们将当前节点的值设置为下一个节点，然后杀死下一个节点。

我的问题是：为什么所有这些教程都展示了如何用双向链表实现LRU缓存，而我们可以通过使用单链表来节省恒定空间？

Answer 1

交换有效载荷会有一些麻烦

• 有效负载可能很大（如缓冲区）
• 部分应用程序代码可能仍然引用有效负载（将其固定）
• 可能涉及锁或互斥锁（可由DLL/哈希节点和/或有效负载拥有）

在任何情况下，修改DLL最多影响2*2个指针，交换有效负载将需要（交换的memcpy）走哈希链（两次），这可能需要访问结构中的任何节点。

Answer 2

您是正确的，可以使用单链表而不是双链表，如下所示：

标准的方法是将hashmap指向一个双链接列表，以简化删除。要在不使用O（n）搜索的情况下使用单链接列表，请让hashmap指向链接列表中的前一个节点（您关心的节点的前一个节点，如果元素位于前面，则为null）。

Retrieve list node:
hashmap(key) ? hashmap(key)->next : list.head

Delete:
successornode = hashmap(key)->next->next
hashmap( successornode ) = hashmap(key)
hashmap(key)->next = successornode
hashmap.delete(key)

为什么双链接列表在LRU解决方案中如此常见？它更容易理解和使用。

如果优化是一个问题，那么用一个稍微不那么简单的单链表解决方案进行权衡绝对是值得的。