常用于LRU缓存和快速定位对象的数据结构有哪些？

Question

我计划实现一个哈希表来快速定位对象，这对我的应用程序非常重要。

然而，我不喜欢扫描整个表并潜在地需要锁定整个表格以定位最后被访问的对象的想法。表可能相当大。

常用的数据结构有哪些可以克服这个问题？

例如，我认为我可以将对象放入FIFO和缓存中，以知道某些内容的年龄。但这不支持LRU算法。

有什么想法吗？Squid是如何实现的？

- hookenz

---

很棒的问题。一个经常需要的数据结构，其实现比看起来更加棘手... - Drew Hall

Answer 1

链表适用于LRU缓存。为了在链表内进行索引查找（将条目移动到链表的最近使用末端），请使用HashTable。最不经常使用的条目始终在链表的末尾。

- k_b

---

我不太同意这里 - 遍历这个列表会很麻烦。 - Puppy

@DeadMG：你一定需要遍历这个列表吗？ - Oliver Charlesworth

@DeadMG：不需要遍历列表。 - k_b

如果你的链表是双向的，那么就不需要遍历它。只需使用以下代码：justUsed->prev->next = justUsed->next; justUsed->next->prev = justUsedPrev; justUsed->next = head; justUsed->prev = null; head = justUsed。然而，如果你的链表是单向的，当将justUsed移动到头部时，你必须遍历列表以找到justUsed前面的节点来修补空洞。 - JoJo

Answer 2

您可能会发现这篇文章关于使用STL容器实现LRU缓存（或基于boost::bimap的替代方案）很有趣。使用STL，基本上您需要使用一个映射（用于快速查找键值对）和一个单独的键或迭代器列表来维护访问历史。

- timday