01 题目介绍

题目描述:
leetcode 146 LRU缓存机制中等难度

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

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

要求: O(1) 时间复杂度完成这两种操作

02 题目分析

概念
LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。

重点
1 最近被访问的数据,其优先级最高;
2 优先级低的数据最先被清除;

时间复杂度
O(1)

03 可行方案

1 链表结构

使用链表结构保存缓存数据。
每当执行put操作时,遍历链表判断该数据是否为新数据:
若为新数据,则在链表头部新建节点并存放新数据;当链表长度超过缓存大小时,将链表尾部节点删除。
若为旧数据,则说明缓存数据命中,更新该缓存数据,并将命中的链表节点移到链表头部。

每当执行get操作时,通过遍历链表进行缓存数据的寻找:
若命中,则根据密钥(key)返回数据值(value),并将数据所在的链表节点置于链表头部;
若未命中,则说明该数据不在缓存中,返回-1。

问题:链表在使用的时候,为了确定是否命中,需要对链表结构进行遍历。时间复杂度为o(n),n为链表长度。未满足题目要求。

2 双向链表与哈希表结合

利用双向链表保存缓存数据,利用哈希表解决需要遍历寻找命中的问题。
双向链表中存放的是缓存数据;哈希表中的value值对应于双向链表中的节点地址。

每当执行put操作时,先判断插入的键值对中的key是否存在与哈希表中:
若key已经存在,说明该数据命中缓存,则根据key对应的节点地址找到该缓存数据节点,更新该节点的数据值,并将该节点置于双向链表的头部,同时更新key所对应的节点地址。
若key不存在,说明该数据在缓存中未发生命中,则在双向链表头部创建新的节点存放新的数据,并在哈希表中添加新的key值与链表头部地址相对应。若链表长度大于缓存大小,则删除链表尾部节点以及对应的哈希表中的键值对。

每当执行get操作时,先判断插入的的键值对中的key是否存在与哈希表中:
若key已经存在,则可通过key值对应的链表中节点的地址,就可取得缓存数据;同时将该节点置于链表的头部并更新key对应的节点地址。
若对应的key不存在于哈希表中,即未发生命中,返回-1。

04 最终实现

说明

list 是C++ STL中容器,底层实现为双向循环链表,任意位置插入和删除时间复杂度0(1)。
unordered_map 同为C++ STL中容器,底层实现为哈希表。

C++代码:

class LRUCache {
public:
    int size;
    list<pair<int, int>> cache; 
    unordered_map<int, list<pair<int,int>>::iterator> map;

    LRUCache(int capacity) {
        size = capacity;
    }

    int get(int key) {
        auto it = map.find(key);  
        if(it == map.end())  //判断key是否存在于哈希表中
            return -1;      
        auto temp = *map[key];  
        cache.erase(map[key]);  //删除命中节点
        cache.push_front(temp);  //在链表头部创建新的数据节点 
        map[key] = cache.begin();  //更新key所对应的节点地址
        return temp.second;         
    }

    void put(int key, int value) {
        auto it = map.find(key);
        if(it == map.end())
        {
            if(cache.size()==size)  //若缓存已满
            {
                auto temp = cache.back();  //获得链表尾部节点
                map.erase(temp.first);  //删除尾部节点对应哈希表键值对
                cache.pop_back();  //删除尾部节点
            }        
            cache.push_front(make_pair(key,value));  //在链表头部插入新的数据节点
            map[key] = cache.begin();  //更新key值对应的节点地址,指向链表头部
        }
        else
        {       
            cache.erase(map[key]);
            cache.push_front(make_pair(key,value));
            map[key] = cache.begin();
        }
    }
};

/**
 * 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);
 */

评析:
这种方案的实现实际上是最简单的一种LRU思想的表现,但是其利用效率不高。在某些情况下,会导致在重复位置的插入和删除,导致更新效率低下;同时由于哈希表本身的结构也会导致其插入和查询的效率不稳定。不过理解上述的实现能够对数据结构的结合和LRU算法有比较明确的了解。