LRU缓存机制解析

java哥 阅读:387 2020-10-21 17:22:29 评论:0

运用你所掌握的数据结构,设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
写入数据 put(key, value) - 如果密钥已经存在,则变更其数据值;如果密钥不存在,则插入该组「密钥/数据值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。

 

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作?

 

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4

 

class LRUCache { 
private: 
    int cap; 
    // 双链表:装着 (key, value) 元组 
    list<pair<int, int>> cache; 
    // 哈希表:key 映射到 (key, value) 在 cache 中的位置 
    unordered_map<int, list<pair<int, int>>::iterator> map; 
public: 
    LRUCache(int capacity) { 
        this->cap = capacity;  
    } 
     
    int get(int key) { 
        auto it = map.find(key); 
        // 访问的 key 不存在 
        if (it == map.end()) return -1; 
        // key 存在,把 (k, v) 换到队头 
        pair<int, int> kv = *map[key]; 
        cache.erase(map[key]); 
        cache.push_front(kv); 
        // 更新 (key, value) 在 cache 中的位置 
        map[key] = cache.begin(); 
        return kv.second; // value 
    } 
     
    void put(int key, int value) { 
 
        /* 要先判断 key 是否已经存在 */  
        auto it = map.find(key); 
        if (it == map.end()) { 
            /* key 不存在,判断 cache 是否已满 */  
            if (cache.size() == cap) { 
                // cache 已满,删除尾部的键值对腾位置 
                // cache 和 map 中的数据都要删除 
                auto lastPair = cache.back(); 
                int lastKey = lastPair.first; 
                map.erase(lastKey); 
                cache.pop_back(); 
            } 
            // cache 没满,可以直接添加 
            cache.push_front(make_pair(key, value)); 
            map[key] = cache.begin(); 
        } else { 
            /* key 存在,更改 value 并换到队头 */ 
            cache.erase(map[key]); 
            cache.push_front(make_pair(key, value)); 
            map[key] = cache.begin(); 
        } 
    } 
};

 

标签:C++
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
排行榜
KIKK导航

KIKK导航

关注我们