最近最少使用（LRU）高速缓存是首先丢弃最近最少使用的项 你如何设计和实现这样一个缓存类？设计要求如下：

Least Recently Used (LRU) Cache is to discard the least recently used items first How do you design and implement such a cache class? The design requirements are as follows:

1）找到该项目以最快的速度，我们可以

1) find the item as fast as we can

2）一旦一个高速缓存未命中和高速缓存已满，需要尽可能快替换最近最少使用的项成为可能。

2) Once a cache misses and a cache is full, we need to replace the least recently used item as fast as possible.

如何分析和设计模式和算法设计方面实现了这个问题？

How to analyze and implement this question in terms of design pattern and algorithm design?

推荐答案

一个链表指针链表的节点+散列表是实现LRU缓存通常的方式。这给了O（1）操作（假设一个体面的哈希值）。利用这个的（为O（1））：您可以通过只锁定整个结构做了多线程版本。你不必担心颗粒状锁等。

A linked list + hashtable of pointers to the linked list nodes is the usual way to implement LRU caches. This gives O(1) operations (assuming a decent hash). Advantage of this (being O(1)): you can do a multithreaded version by just locking the whole structure. You don't have to worry about granular locking etc.

简单地说，它的工作方式：

Briefly, the way it works:

在一个值的访问，您将在链接列表中的相应节点的头部。

On an access of a value, you move the corresponding node in the linked list to the head.

当你需要删除缓存中的值，从尾部删除。

When you need to remove a value from the cache, you remove from the tail end.

在一个值添加到缓存中，你只要将其放置在链表的头。

When you add a value to cache, you just place it at the head of the linked list.

由于doublep，这里是现场用C ++实现：其他容器模板

Thanks to doublep, here is site with a C++ implementation: Miscellaneous Container Templates.