LRU算法简介

对于web开发而言，缓存必不可少，也是提高性能最常用的方式。无论是浏览器缓存，还是服务端的缓存(通过memcached或者redis等内存数据库)。缓存不仅可以加速用户的访问，同时也可以降低服务器的负载和压力。那么，了解常见的缓存淘汰算法的策略和原理就显得特别重要。

常见的缓存算法

LRU (Least recently used) 最近最少使用，如果数据最近被访问过，那么将来被访问的几率也更高。

LFU (Least frequently used) 最不经常使用，如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小。

FIFO (Fist in first out) 先进先出，如果一个数据最先进入缓存中，则应该最早淘汰掉。

时间局部性原理

它是按照一个非常著名的计算机操作系统基础理论得来的：最近使用的页面数据会在未来一段时期内仍然被使用,已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用。基于这个思想,会存在一种缓存淘汰机制，每次从内存中找到最久未使用的数据然后置换出来，从而存入新的数据！它的主要衡量指标是使用的时间，附加指标是使用的次数。在计算机中大量使用了这个机制，它的合理性在于优先筛选热点数据，所谓热点数据，就是最近最多使用的数据！因为，利用LRU我们可以解决很多实际开发中的问题，并且很符合业务场景。

像浏览器的缓存策略、memcached的缓存策略都是使用LRU这个算法，LRU算法会将近期最不会访问的数据淘汰掉。LRU如此流行的原因是实现比较简单，而且对于实际问题也很实用，良好的运行时性能，命中率较高。下面谈谈如何实现LRU缓存：

新数据插入到链表头部
每当缓存命中（即缓存数据被访问），则将数据移到链表头部
当链表满的时候，将链表尾部的数据丢弃

LRU Cache具备的操作

set(key,value)：如果key在hashmap中存在，则先重置对应的value值，然后获取对应的节点cur，将cur节点从链表删除，并移动到链表的头部；若果key在hashmap不存在，则新建一个节点，并将节点放到链表的头部。当Cache存满的时候，将链表最后一个节点删除即可。

get(key)：如果key在hashmap中存在，则把对应的节点放到链表头部，并返回对应的value值；如果不存在，则返回-1。

C++实现

#include<bits/stdc++.h>
using namespace std;

class LRUCache {
public:
    LRUCache(int capacity) : cap(capacity) {
    }

    int get(int key) {
        if (map.find(key) == map.end()) return -1;
        auto key_value = *map[key]; // 通过迭代器可以读取它指向的元素，*迭代器名就表示迭代器指向的元素。通过非常量迭代器还能修改其指向的元素
        cache.erase(map[key]);
        cache.push_front(key_value);
        map[key] = cache.begin(); // 返回指向容器中第一个元素的双向迭代器，迭代器在list中位置变了，所以要把新的迭代器的逻辑位置信息赋给哈希表
        return key_value.second;
    }

    void put(int key, int value) {
        if (map.find(key) == map.end()) { // 查找以 key 为键的键值对，如果找到，则返回一个指向该键值对的正向迭代器；反之，则返回一个指向容器中最后一个键值对之后位置的迭代器（如果 end() 方法返回的迭代器）
            if (cache.size() == cap) {
                map.erase(cache.back().first);
                cache.pop_back();
            }
        } else {
            cache.erase(map[key]);
        }
        cache.push_front({key, value});
        map[key] = cache.begin();
    }
private:
    int cap;
    list<pair<int, int>> cache;
    unordered_map<int, list<pair<int, int>>::iterator> map;
};

int main() {
    LRUCache *lruCache = new LRUCache(2);
    lruCache->put(2, 2);
    lruCache->put(1, 1);
    cout << lruCache->get(2) << "  ";
    lruCache->put(4, 4);
    cout << lruCache->get(1) << "  ";
    cout << lruCache->get(2) << "  ";
    cout << endl;

    // lruCache -> put(2, 2);
    // lruCache -> put(1, 1);
    // lruCache -> put(3, 3);
    // cout << lruCache -> get(2) << "  ";
    // lruCache -> put(4, 4);
    // cout << lruCache -> get(1) << "  ";
    // cout << lruCache -> get(2) << "  ";
    // cout << lruCache -> get(3) << "  ";
    // cout << lruCache -> get(4) << "  ";
    // cout << lruCache -> get(4) << "  ";
    // cout << lruCache -> get(3) << "  ";
    // cout << lruCache -> get(2) << "  ";
    // cout << lruCache -> get(4) << "  ";
    // cout << endl;
}

郭霖的博客

C++实现LRU缓存淘汰算法

LRU算法简介

常见的缓存算法

时间局部性原理

LRU Cache具备的操作

C++实现