C++ LRU

LRU：最近最少使用缓存，实现 LRUCache 类：

• LRUCache(int capacity) ：以正整数作为容量capacity，初始化LRU缓存。
• int get(int key)：如果关键字 key 存在于缓存中，则返回关键字的值，否则返回-1。
• void put(int key, int value)：如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。
  函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

总是希望最近使用的、最频繁使用的数据存储在比较靠前的位置。于是，LRU 缓存要具备以下特点：

• 插入某个数据时，它应该被放到 Cache 的最前面
• 查询某个数据之后，它应该被挪到 Cache 的最前面
• 插入数据时，如果 Cache 的容量不够时，把 Cache 尾部的数据移出

一个常见的LRU缓存的实现思路是使用哈希表和双向链表结合的方法：

1. 哈希表: 存储键和指向其在双向链表中节点的指针，用于O(1)时间复杂度内查找键。
2. 双向链表: 存储键值对，链表的顺序由元素的使用顺序决定。最近使用的元素被放置在链表的前端，而最少使用的元素则被放置在链表的尾端。

如果考虑线程安全性，就需要用到锁，C++中的mutex，配合std::lock_guard使用。

#include<iostream>
#include <string.h>
#include<mutex>

namespace _LRU{

// 设计一个不限类型的线程安全的LRU，还不让使用STL
template<typename K, typename V>
class Node{
public:
    K key;
    V value;
    Node* prev;
    Node* next;

    Node(K k, V v):key(k),value(v),prev(nullptr),next(nullptr){}

};

template<typename K, typename V>
class LRUCache{
public:
    LRUCache(int cap) : capacity(cap),size(0){
        head = new Node<K,V>(K(),V());
        tail = new Node<K,V>(K(),V()); 
        /*head = new Node<K,V>(0,0);
        tail = new Node<K,V>(0,0);*/
        head->next = tail;
        tail->prev = head;
        // 初始化哈希表
        hashTable = new NodePointer[capacity]();
    }

    ~LRUCache(){
        NodePointer cur = head;
        while(cur){
            NodePointer next = cur->next;
            delete cur;
            cur = next;
        }
        delete []hashTable;
    }

    // 插入或更新节点
    void put(K key, V value){
        std::lock_guard<std::mutex> lock(mutex);
        unsigned int index = hash(key);
        
        // 如果键已经存在，更新值并移动到头部
        if(hashTable[index]){
            hashTable[index]->value = value;
            moveToHead(hashTable[index]);
        }else{
            NodePointer newNode = new Node<K,V>(key,value);
            hashTable[index] = newNode;
            moveToHead(newNode);
            // 如果超出容量，移除LRU节点
            size++;
            if(size>capacity){
                removeLRU();
                size--;
            }
        }
    }

    // 获取节点的值
    V get(K key) {
        std::lock_guard<std::mutex> lock(mutex);
        unsigned int index = hash(key);

        NodePointer node = hashTable[index];
        while (node) {
            if (node->key == key) {
                moveToHead(node);
                return node->value;
            }
            node = node->next;
        }
        return V();
    }
private:
    int capacity;
    int size;
    using NodePointer = Node<K,V>*;
    NodePointer head;// 虚拟头节点
    NodePointer tail;
    NodePointer* hashTable; //散列表
    std::mutex mutex;
    
    unsigned int hash(K key) {
        // 最简单的散列函数
        return std::hash<K>{}(key) % capacity;
    }

    void moveToHead(NodePointer node) {
        //if (node == head)return;
        // 从当前位置移除节点
        // 如果是新节点，就不要做这个操作了
        if(node->prev){
            node->prev->next = node->next;
        }
        if(node->next){
            node->next->prev = node->prev;
        }
        
        // 移动node节点到头部
        node->next = head->next;
        head->next->prev = node;
        node->prev = head;
        head->next = node;
    }

    // 移除最少使用的节点（LRU节点）
    void removeLRU(){
        NodePointer lru = tail->prev;
        if(lru == head) return;
        // 从链表移除LRU节点
        lru->prev->next = tail;
        tail->prev = lru->prev;

        // 在hash表中删除该节点
        unsigned int index = hash(lru->key);
        hashTable[index] = nullptr;
        delete lru;
    }
};


};

int main(){
    _LRU::LRUCache<int, int> cache(3);// 容量为3，hash算法也是以3为分母

    cache.put(1, 1);
    cache.put(2, 2);
    std::cout << cache.get(1) << std::endl; // 1

    cache.put(3, 3); 
    std::cout << cache.get(2) << std::endl; // 2

    cache.put(4, 4); // 插入4,4以后，和1,1冲突，hash表key=1的value变为4 
    std::cout << cache.get(1) << std::endl; // 4
    std::cout << cache.get(3) << std::endl; // 3 
    std::cout << cache.get(4) << std::endl; // 0 //找不到，为0
    std::cout << cache.get(2) << std::endl; // 2
    cache.put(5, 5); // 插入5,5 和2,2冲突，hash表key=2的value变为5 
    std::cout << cache.get(5) << std::endl; // 0 //找不到，为0
    std::cout << cache.get(2) << std::endl; // 5
    return 0;
}

参考列表
https://leetcode.cn/problems/lru-cache/description/
https://www.jianshu.com/p/f82a90bd3a22