一、LRU算法描述

LRU全称是Least Recently Used，最近最少使用的意思，是一种常用的内存置换算法。当内存不够的时候，要把部分内存写入到磁盘中，此时就要用到LRU算法来决定把那部分内存写入到磁盘。

当把内存数据写入到磁盘的时候，肯定是把不常用的内存置换到磁盘这样才是最优的。不然把常用的内存写入磁盘，然后又频繁从磁盘读出来，明显会降低系统性能。LRU的核心思想就是把最近最少使用的内存置换到磁盘中去。

一般来说，实现LRU算法都是使用哈希表+链表来实现，这样可以使得LRU操作的时间复杂度是O(1)。具体的过程描述为：

1. 传入内存地址，通过哈希表判断内存是否已经存在于链表了。如果内存存在，把节点移到链表开头。

2. 如果内存不存在于哈希表中，有两种情况：

   • 链表没满，把节点插入链表开头。
   • 链表满了，淘汰掉链表末尾节点，当前节点插入到链表开头。

哈希表中记录的是内存和链表节点的对应关系，这样当一个内存地址传入的时候，在O(1)的时间内就能确定该内存地址是否已经存在于缓存中了。如果没有哈希表，那么每次判断内存是否存在于缓存的时候都要遍历链表查询，需要时间复杂度为O(n)。

LRU图解

假设存在一个缓存容量为5的缓存区，当前已经缓存了1、4、8、9四块内存：

访问内存块3，因为缓存中不含有这块内存，要把3加到缓存中去：

访问内存块5，因为5不存在于缓存中，要把5插入到缓存。但是目前链表已经满了，不能容纳更多的节点，所以必须把最后的节点淘汰掉，也就是去掉9：

访问内存块1，1已经存在于缓存了，把它放到链表最前面来：

二、代码描述

2.1 lru对象设计

实现LRU需要用到双向链表+哈希表：

• 哈希表保存了每个缓存节点的地址，可以直接使用STL中的map。
• STL中也有双向链表，可以直接使用这个链表结构。

一个LRU缓存对象需要包含的方法：

• get()：从缓存获取一块内存
• put()：存放一块内存到缓存

LRU对象设计：

// 缓存的数据
typedef pair<int, int> cache_val;

class lru_cache {
private:
    // 链表
    list<cache_val> l;
    // 哈希表
    map<int, list<cache_val>::iterator> m;
    // 链表的容量和长度
    size_t cap, len;
public:
    // 构造函数
    lru_cache(size_t cap) : cap(cap), len(0) {}
}

2.2 get函数实现

get函数的实现：

int get(int key) {
    cache_val cache;
    map<int, list<cache_val>::iterator>::iterator it;

    it = m.find(key);

    // 没有找到，返回-1
    if (it == m.end())
        return -1;

    // 找到了，移到最前面去
    cache = *(it->second);
    // 先删除
    m.erase(key);
    l.erase(it->second);

    // 再插入
    l.push_front(cache);
    m.insert(pair<int, list<cache_val>::iterator>(key, l.begin()));
    return it->second->second;
}

2.3 put函数实现

put`函数的实现：

void put(const int &key, const int val) {
    cache_val cache;
    map<int, list<cache_val>::iterator>::iterator it;
    it = m.find(key);

    // 找到了缓存
    if (it != m.end()) {
        // 移到链表开头
        cache = *(it->second);
        l.erase(it->second);
        l.push_front(cache);
        // 重新修改哈希表的指向
        m.erase(key);
        m[key] = l.begin();
        return;
    }

    // 下面是没有找到缓存，要插入新的节点到链表和哈希表
    // 链表的长度已经超过容量了
    if (len >= cap) {
        // 哈希表移除节点
        m.erase(l.back().first);
        // 链表移除末尾节点
        l.pop_back();
    }

    cache = pair<int, int>(key, val);
    l.push_front(cache);
    m.insert(pair<int, list<cache_val>::iterator>(key, l.begin()));

    if (len < cap)
        len++;
}

三、单元测试

测试案例：

TEST(lru_cache, leetcode) {
    lru_cache cache = lru_cache(2);

    cache.put(1, 1);
    cache.put(2, 2);
    EXPECT_EQ(1, cache.get(1));       // 返回  1

    cache.put(3, 3);    // 该操作会使得密钥 2 作废
    EXPECT_EQ(-1, cache.get(2));

    cache.put(4, 4);    // 该操作会使得密钥 1 作废
    EXPECT_EQ(-1, cache.get(1));
    EXPECT_EQ(3, cache.get(3));
    EXPECT_EQ(4, cache.get(4));
}