菜鸟笔记
提升您的技术认知

面试题

实现一个LRU Cache 算法LRU Cache C++三种解法java实现LRU算法及编码实现LRU策略缓存LRU算法常见缓存算法和LRU的c++实现设计循环双端队列(deque)LRU 缓存结构 (c++ 哈希双链表实现)LRU缓存机制删除单链表中的指定节点Linux 内核经典面试题拼多多社招面经:Redis是重点,讲一讲redis的内存模型线程、进程、协程的区别C++经典面试题面试官:我们只想要这样的C++工程师Linux C/C++ 学习路线链表操作汇总C++11的智能指针面试题浏览器中输入url后发生的事情常用的限流算法HTTP协议和HTTPS协议面试题网络编程面试题目总结c++后台面试题目如何实现LRU算法?如何寻找无序数组中的第K大元素?布隆过滤器 - 如何在100个亿URL中快速判断某URL是否存在?如何实现大整数相加?C++面试题及基本知识点总结C++给定出栈序列判定是否合法消息队列面试题要点redis缓存击穿,失效以及热点key解决方案网页在浏览器上的渲染过程几种限流算法lru算法例题C/C++常见面试知识点总结附面试真题----20210529更新引入MQ消息队列的作用及其优缺点MySQL面试篇社招三年后端面试题60道测开面试题,背完直接涨工资二叉树的层序遍历(两种方法实现)Bitmap 海量数据处理字符串倒序输出的五种方法C语言 输入10个数,统计出并输出正数、负数和0的个数字节三面:如何设计一个高并发系统架构,网络 面试36问,DDos攻击原理C++线程池使用 C++11 编写可复用多线程任务池

实现一个LRU Cache 算法

阅读 : 2537

LRU缓存是面试中很容易考到的一个知识点,除了要对其原理熟悉之外,也要掌握其简单实现。通过采用两个hash map + list的数据结构,可以在O(1)的时间复杂度下实现get和put操作。

class LRUCache {
private:
    int size;
    list<int> lru;   //key
    unordered_map<int, list<int>::iterator> map;  //key, iterator
    unordered_map<int, int> kv;   //key, value

    void update(int key) {
        if (kv.find(key) != kv.end())
            lru.erase(map[key]);
        lru.push_front(key);
        map[key] = lru.begin();
    }

    void evict() {
        map.erase(lru.back());
        kv.erase(lru.back());
        lru.pop_back();
    }

public:
    LRUCache(int capacity) {
        size = capacity;
    }

    int get(int key) {
        if (kv.find(key) == kv.end())
            return -1;
        update(key);
        return kv[key];
    }

    void put(int key, int value) {
        if (kv.size() == size && kv.find(key) == kv.end())
            evict();
        update(key);
        kv[key] = value;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */