最近最少使用（LRU）高速缓存将首先丢弃最近最少使用的项目。如何设计和实现这种高速缓存类？设计要求如下：
1）尽快找到商品
2）一旦缓存未命中且缓存已满，我们需要尽快替换最近最少使用的项目。
如何从设计模式和算法设计上分析和实现这个问题？
链表+指向链表节点的指针的哈希表是实现LRU缓存的常用方法。这给出了O（1）操作（假设一个不错的哈希值）。这样做的优势（为O（1））：您只需锁定整个结构即可创建多线程版本。您不必担心粒度锁定等。
简而言之，它的工作方式：
访问值时，将链接列表中的相应节点移到头部。
当您需要从缓存中删除一个值时，可以从尾端删除。
将值添加到缓存时，只需将其放在链接列表的开头即可。
感谢doublep，这是一个具有C ++实现的站点：其他容器模板。
