LRU缓存设计

Question

最近最少使用(LRU)缓存是首先丢弃最近最少使用的项目，您如何设计和实现这样的缓存类？设计要求如下：

1)尽可能快地找到项目

2)一旦缓存未命中并且缓存已满，我们需要尽可能快地替换最近最少使用的项。

如何从设计模式和算法设计的角度来分析和实现这个问题？

Answer 1

链表+指向链表节点的指针的哈希表是实现LRU缓存的常用方法。这给出了O(1)个操作(假设一个像样的散列)。这样做的好处( O(1))：你可以通过锁定整个结构来做一个多线程的版本。您不必担心粒度锁定等问题。

简而言之，它的工作方式：

在访问值时，将链接列表中的相应节点移动到头上。

当您需要从缓存中删除一个值时，您可以从尾端删除。

将值添加到缓存时，只需将其放在链表的头部即可。

多亏了doublep，这是一个具有C++实现的站点：Miscellaneous Container Templates。

Answer 2

这是我的LRU缓存的简单示例c++实现，它结合了散列(Unordered_map)和列表。列表上的项具有访问映射的关键字，映射上的项具有列表到访问列表的迭代器。

#include <list>
#include <unordered_map>
#include <assert.h>

using namespace std;

template <class KEY_T, class VAL_T> class LRUCache{
private:
        list< pair<KEY_T,VAL_T> > item_list;
        unordered_map<KEY_T, decltype(item_list.begin()) > item_map;
        size_t cache_size;
private:
        void clean(void){
                while(item_map.size()>cache_size){
                        auto last_it = item_list.end(); last_it --;
                        item_map.erase(last_it->first);
                        item_list.pop_back();
                }
        };
public:
        LRUCache(int cache_size_):cache_size(cache_size_){
                ;
        };

        void put(const KEY_T &key, const VAL_T &val){
                auto it = item_map.find(key);
                if(it != item_map.end()){
                        item_list.erase(it->second);
                        item_map.erase(it);
                }
                item_list.push_front(make_pair(key,val));
                item_map.insert(make_pair(key, item_list.begin()));
                clean();
        };
        bool exist(const KEY_T &key){
                return (item_map.count(key)>0);
        };
        VAL_T get(const KEY_T &key){
                assert(exist(key));
                auto it = item_map.find(key);
                item_list.splice(item_list.begin(), item_list, it->second);
                return it->second->second;
        };

};

Answer 3

我在这里看到了几个不必要的复杂实现，所以我决定也提供我的实现。缓存只有两个方法，get和set。希望它有更好的可读性和理解性：

#include<unordered_map>
#include<list>

using namespace std;

template<typename K, typename V = K>
class LRUCache
{

private:
    list<K>items;
    unordered_map <K, pair<V, typename list<K>::iterator>> keyValuesMap;
    int csize;

public:
    LRUCache(int s) :csize(s) {
        if (csize < 1)
            csize = 10;
    }

    void set(const K key, const V value) {
        auto pos = keyValuesMap.find(key);
        if (pos == keyValuesMap.end()) {
            items.push_front(key);
            keyValuesMap[key] = { value, items.begin() };
            if (keyValuesMap.size() > csize) {
                keyValuesMap.erase(items.back());
                items.pop_back();
            }
        }
        else {
            items.erase(pos->second.second);
            items.push_front(key);
            keyValuesMap[key] = { value, items.begin() };
        }
    }

    bool get(const K key, V &value) {
        auto pos = keyValuesMap.find(key);
        if (pos == keyValuesMap.end())
            return false;
        items.erase(pos->second.second);
        items.push_front(key);
        keyValuesMap[key] = { pos->second.first, items.begin() };
        value = pos->second.first;
        return true;
    }
};