LRU缓存和快速定位对象通常使用哪些数据结构？

Question

我打算实现一个HashTable来快速定位对象,这对我的应用程序很重要.

但是,我不喜欢扫描的想法,可能必须锁定整个表,以便找到上次访问的对象.表格可能非常大.

通常使用哪些数据结构来克服这种情况？

例如,我认为我可以将对象放入FIFO和缓存中,以便知道有多旧.但这不会支持LRU算法.

有任何想法吗？鱿鱼怎么做的？

Answer 1

链接列表适用于LRU缓存.对于链表内的索引查找(将条目移动到链接列表最近使用的结尾),请使用HashTable.最近最少使用的条目将始终位于链接列表的最后.

Answer 2

您可能会发现有关使用STL容器(或基于替代方法)的LRU缓存实现的这篇文章boost::bimap很有趣.使用STL,基本上您可以将映射(用于快速键值查找)和单独的键或迭代器列表组合到该映射中(以便于维护访问历史记录).