LRU缓存设计

Question

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

1)尽可能快地找到项目

2)一旦缓存未命中并且缓存已满,我们需要尽快替换最近最少使用的项目.

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

Answer 1

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

简而言之,它的工作方式:

在访问值时,将链接列表中的相应节点移动到头部.

当您需要从缓存中删除值时,您将从尾端删除.

向缓存添加值时,只需将其放在链表的头部即可.

感谢doublep,这里是带有C++实现的站点:杂项容器模板.

Answer 2

这是我对LRU缓存的简单示例c ++实现,结合了hash(unordered_map)和list.列表中的项目具有访问映射的键,而映射上的项目具有列表访问列表的迭代器.

#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;
    }
};