LRU算法原理及其实现

一、LRU是什么

        LRU算法的全称是“Least Recently Used”，即“最近最少使用”算法。LRU算法的基本思想是，当缓存空间已满时，优先淘汰最近最少使用的缓存数据，以腾出更多的缓存空间。因此，LRU算法需要维护一个缓存访问历史记录，以便确定哪些缓存数据是最近最少使用的。

        LRU算法的实现可以采用多种数据结构，其中最常见的是使用一个双向链表和一个哈希表。双向链表用于维护缓存数据的访问顺序，哈希表用于快速查找缓存数据。具体来说，当新的数据被访问时，先在哈希表中查找该数据是否已经存在于缓存中，如果存在，则将该数据移动到双向链表的头部，表示该数据是最近访问的数据；如果不存在，则需要将该数据添加到缓存中，并将其添加到双向链表的头部。当缓存空间已满时，需要淘汰双向链表中最后一个节点，同时在哈希表中删除对应的缓存数据。

二、使用场景

        考虑这样一个场景，单位维护了一个资源下载网站。某天产品找到你，让你根据用户下载量对资源进行排序，同时定期删除不经常使用的资源，释放服务器压力，应该怎么做？

        简单，数据库加个计数和最近使用时间字段，返回接口根据这两个字段做个排序，然后再写个定时任务删除冗余资源就完事了，开干！

        哗哗哗写完后，自信提交。

        测试跑过来说，你这功能写的不行啊，我们才这么几个人用，搜索资源就开始卡了，真给你上线不得把服务器干翻？

        啊，真烦，功能实现了不就行了嘛，真是没事找事。

三、LRU实现

3.1 LRU缓存实体定义

struct List
{
    int val;
    List *pre, *nxt;
    List(int x, List *y, List *z)
    {
        val = x, pre = y, nxt = z;
    }
} *head;
int idx;
map<int, List *> mp;

再优化下，使用 unordered_map<KEY，std::list<VALUE>::iterator> 代替

3.2 CURD实现

    // 存储缓存的值的列表
    std::list<VALUE> values_;
    // 存储键到值列表中对应迭代器的映射
    std::unordered_map<KEY, typename std::list<VALUE>::iterator, HASH> posInfo_;

   // 插入键值对到缓存中
    void setKey(const KEY& key, const VALUE& data) {
        std::lock_guard<std::mutex> guard(mutex_);
        auto it = posInfo_.find(key);
        if (it!= posInfo_.end()) {
            // 键已存在，先删除旧值
            values_.erase(it->second);
            posInfo_.erase(it);
        }
        // 将新值插入到缓存列表头部，并更新键到迭代器的映射
        values_.push_front(data);
        posInfo_[key] = values_.begin();
    }

    // 根据键获取值
    bool getKey(const KEY& key, VALUE& data) {
        auto it = posInfo_.find(key);
        if (it == posInfo_.end()) {
            return false;
        }
        // 将对应的值移动到缓存列表头部，并更新键到迭代器的映射
        moveToFront(it);
        data = *(it->second);
        return true;
    }

    // 检查键是否存在于缓存中
    bool existKey(const KEY& key) {
        return posInfo_.find(key)!= posInfo_.end();
    }

    // 根据键删除值
    void delKey(const KEY& key) {
        auto it = posInfo_.find(key);
        if (it == posInfo_.end()) {
            return;
        }
        // 删除对应的值
        values_.erase(it->second);
        posInfo_.erase(it);
    }

    // 将对应的值移动到缓存列表头部，并更新键到迭代器的映射
    void moveToFront(const typename std::unordered_map<KEY, typename         
    std::list<VALUE>::iterator, HASH>::iterator& it) {
        values_.splice(values_.begin(), values_, it->second);
        it->second = values_.begin();
    }

3.3 数据淘汰

    // 存储被淘汰的值的向量
    std::vector<VALUE> elimiValues_;    
    // 根据给定函数进行淘汰处理
    void eliminate(std::function<bool(const VALUE&)> func, std::vector<VALUE>* _return = nullptr) {
        if (_return) {
            // 将被淘汰的值存储在 _return 指向的向量中，并返回
            std::swap(*_return, elimiValues_);
        } else {
            // 清空存储被淘汰值的向量
            elimiValues_.clear();
        }

        while (!values_.empty()) {
            VALUE last = values_.back();
            if (!func(last)) {
                break;
            }
            // 根据淘汰条件逐个淘汰缓存中的值
            KEY key = value.get_key_from_val(last);
            values_.pop_back();
            posInfo_.erase(key);
            if (_return) {
                _return->push_back(last);
            }
        }
    }

3.4 优化

我们的业务是个多线程场景，此外要考虑LRUCache 缓存满的场景。因此，简单调整下代码，再增加个数据淘汰策略。

3.4.1淘汰算法

    // 淘汰策略枚举
    enum class EN_ELIMINATE_POLICY {
        EP_THROW_DIRECT,    // 直接丢弃被淘汰的数据
        EP_PENDING_DISPOSAL // 将被淘汰的数据放入待处理区
    };

    // 处理缓存已满时的淘汰操作
    void handleEviction() {
        const VALUE& val = values_.back();
        if (policy_ == EN_ELIMINATE_POLICY::EP_PENDING_DISPOSAL) {
            elimiValues_.push_back(val);
        }
        KEY lastkey = getKeyFromValue(val);
        values_.pop_back();
        posInfo_.erase(lastkey);
    }

3.4.2 业务修改示例

    // 当前的淘汰策略
    EN_ELIMINATE_POLICY policy_;
    // 互斥锁，用于保证线程安全
    std::mutex mutex_;
  
    // 插入键值对到缓存中
    void setKey(const KEY& key, const VALUE& data) {
        std::lock_guard<std::mutex> guard(mutex_);
        auto it = posInfo_.find(key);
        if (it!= posInfo_.end()) {
            // 键已存在，先删除旧值
            values_.erase(it->second);
            posInfo_.erase(it);
        } else if (MAXSIZE > 0 && posInfo_.size() >= MAXSIZE) {
            // 缓存已满，根据淘汰策略处理被淘汰的值
            handleEviction();
        }
        // 将新值插入到缓存列表头部，并更新键到迭代器的映射
        values_.push_front(data);
        posInfo_[key] = values_.begin();
    }

四、总结

        LRU是个很常见的置换淘汰算法，在资源管理和缓存方面有很多应用，例如著名的redis中就有其相关应用

另附 ：完整源码