想进大厂、想提升底层功力、想搞懂LRU缓存，这一篇就够了！

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

class LRUCache
{
//01-定义数据结构
private:
    int MaxCapacity; // 缓冲区的最大容量
    int size;        // 缓冲区使用的大小
    struct DoubleListNode {
        int key;
        int value;
        DoubleListNode* prev;
        DoubleListNode* next;
        DoubleListNode(int k,int v) : key(k), value(v),   prev(nullptr), next(nullptr) {}

    };

    map<int,DoubleListNode*> cache; // 缓存，key为数据的key，value为双向链表节点
    DoubleListNode* phead; // 头结点
    DoubleListNode* ptail; // 尾结点

//02 定义算法
public:
    LRUCache(int capacity)
    {
        MaxCapacity = capacity;

        size = ;

        phead =new DoubleListNode(, ); // 初始化头结点

        ptail = new DoubleListNode(, ); // 初始化尾结点

        phead->next =ptail; // 头结点的下一个指向尾结点

        ptail->prev =phead; // 尾结点的前一个指向头结点

        //这样设计好处，不用判断是否空节点

    }

    int get(int key)
    {
      if (cache.find(key) == cache.end())
      {
        return-1; // 如果key不存在，返回-1

      } else {
        DoubleListNode *node = cache[key]; // 获取节点

        deleteNode(node);

        insertToHead(node);

        return node->value; // 返回节点的值
      } //思考如何避免频繁的移动节点

    }

    void put(int key, int value) {

     //判断key存在

      if (cache.find(key) != cache.end()) {

            DoubleListNode *node = cache[key]; // 获取节点

            node->value = value; // 更新节点的值

            deleteNode(node);

            insertToHead(node);

            return ;

      }
      //超过最大容量,删除不经常使用的节点

      //链表最后最后一个节点是不经常使用的节点

      if (size >= MaxCapacity) {

        DoubleListNode *pcur = ptail->prev; // 获取尾结点的前一个节点

        deleteNode(pcur);

        cache.erase(pcur->key);

        delete pcur; // 删除节点

        size--; // 缓冲区大小减1

      }

      //插入一个元素

      DoubleListNode *ptemp = new DoubleListNode(key,value);

      cache[key] = ptemp; // 将新节点加入缓存

      //将新节点插入到头结点后面

      insertToHead(ptemp);

      size++; // 缓冲区大小加1

    }
private:

      void deleteNode(DoubleListNode* cur) {

        if (nullptr == cur) return;

        cur->prev->next  = cur->next;

        cur->next->prev = cur->prev;

        // cache.erase(cur->key); // 从缓存中删除

        // delete cur; // 删除节点

        // size--; // 缓冲区大小减1

      }
      void insertToHead(DoubleListNode* cur) {

        cur->next = phead->next; // 新节点的下一个指向头结点的下一个

        phead->next->prev = cur; // 头结点的下一个的前一个指向新节点

        phead->next = cur; // 头结点的下一个指向新

        cur->prev = phead; // 新节点的前一个指向头结点

        // size++; // 缓冲区大小加1

      }
};

#include <list>
#include <unordered_map>
usingnamespacestd;

class LRUCache {
    int capacity;
    list<pair<int, int>> cache; // {key, value}
    unordered_map<int, list<pair<int, int>>::iterator> map; 
    // key -> list迭代器
    //https://en.cppreference.com/w/cpp/container/list.html
    //std：：list 是一个容器，
    //它支持从容器中的任何位置插入和删除元素的恒定时间。
    //不支持快速随机访问。它通常实现为双向链表
public:
    LRUCache(int capacity) : capacity(capacity) {}

    int get(int key) {
        auto it = map.find(key);
        if (it == map.end()) return-1;
        // 移动到头部
        cache.splice(cache.begin(), cache, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = map.find(key);
        if (it != map.end()) {
            // 更新并移到头部
            it->second->second = value;
            cache.splice(cache.begin(), cache, it->second);
        } else {
            if (cache.size() == capacity) {
                // 淘汰尾部
                int oldKey = cache.back().first;
                cache.pop_back();
                map.erase(oldKey);
            }
            cache.emplace_front(key, value);
            map[key] = cache.begin();
        }
    }
};
https://www.nextptr.com/tutorial/ta1576645374/stdlist-splice-for-implementing-lru-cache

struct Node {
    Key key;
    Value value;
    std::atomic<Node*> prev, next;
    std::atomic<bool> valid;
};

std::atomic<Node*> head, tail;
std::unordered_map<Key, Node*> index; // 需要替换成 lock-free map

// ...existing code...
typedefstruct redisDb {
    dict *dict;                 /* The keyspace for this DB */
    // ...existing code...
} redisDb;
 C 语言没有这种数据结构， 需要自定义

typedefstruct dictEntry {
    void *key;               // 指向 key 的指针（通常是 sds 类型）
    void *val;               // 指向 value 的指针
    struct dictEntry *next;// 用于处理哈希冲突的链表指针
} dictEntry;

struct redisObject 
{

    unsigned type:;

    unsigned encoding:;

    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or

                            * LFU data (least significant 8 bits frequency

                            * and most significant 16 bits access time). */

    unsigned iskvobj : ;   /* 1 if this struct serves as a kvobj base */

    unsigned expirable : ; /* 1 if this key has expiration time attached.

                             * If set, then this object is of type kvobj */

    unsigned refcount : OBJ_REFCOUNT_BITS;

    void *ptr;

};

// 伪代码，实际实现更复杂
dictEntry *dictGetFairRandomKey(dict *d) {
    dictEntry *entry = NULL;
    int tries = ; // 最多尝试次数
    while (tries--) {
        // 随机选一个哈希桶
        unsignedlong idx = random() % d->ht[].size;
        entry = d->ht[].table[idx];
        if (entry) break;
    }
    // 如果没采到，fallback 到 dictGetRandomKey
    if (!entry) return dictGetRandomKey(d);
    // 桶内有冲突链表，随机选一个
    int listlen = ;
    dictEntry *e = entry;
    while (e) { listlen++; e = e->next; }
    int skip = random() % listlen;
    e = entry;
    while (skip--) e = e->next;
    return e;
}

1. 系统启动
 → Buffer Pool 初始化
 → LRU 链表为空，old/young 未构建成功

2. 访问数据页 P
 → 不存在缓冲中，加载到内存
 → 插入 Old 区头
 → LRU 链表增长

3. 重复大表扫描
 → 访问各页，均插到 Old 区头
 → 1 秒内访问同页多次也不晋升
 → LRU 震荡在 Old 区

4. 内存满了，触发淘汰
 → 淘汰 Old 区尾部页
 → Hot 页留在 Young，未被影响

5. 热点访问重现
 → 访问 Young 或晋升 Old 页
 → Hot 页集中，系统恢复响应率

struct LRUHandle {
  // 存储的 value 对象的指针，可以存储任意类型的值
void* value;

// 当引用计数 `refs` 降为 0 时的清理函数
void (*deleter)(const Slice&, void* value);

// 哈希表通过链地址法解决哈希冲突，发生哈希冲突时指向下一个 entry
  LRUHandle* next_hash;

// LRU 链表双向指针
  LRUHandle* next;
  LRUHandle* prev;

// 分配的可以消耗的内存量
  size_t charge;

// key 的字节数
  size_t key_length;

// entry 是否存在缓存中
  bool in_cache; 

// 引用计数，记录 entry 被不同缓存的引用，用于 entry 删除
  uint32_t refs;

// `key()` 对应的哈希，用于快速分区和比较
  uint32_t hash;

// 存储 key 的开始地址，结合 `key_length` 获取真正的 key 
// GCC 支持 C99 标准，允许定义 char key_data[] 这样的柔性数组（Flexible Array)。
// C++ 标准并不支持柔性数组的实现，这里定义为 key_data[1]，这也是 c++ 中的标准做法。
  char key_data[];
  Slice key() const {
    // 只有当当前节点是空链表头时，`next` 才会等于 `this`
    // 链表是循环双向链表，空链表的头节点 next 和 prev 都指向自己构成环
    // 链表头是冗余的 handle，不存储数据，只利用它的 next 和 prev
    assert(next != this);
    return Slice(key_data, key_length);
  }
};

参考：https://blog.mrcroxx.com/posts/code-reading/leveldb-made-simple/7-cache/

LRU算法的实现
class LUR
{
using LRUList = xlist<LRUObject*>;
 LRUList top, bottom, pintail;  //定义三个链表，而不是一个链表
}
 `top`链表代表最近访问的对象链表。当缓存对象被插入/访问时，这个对象会被放到`top`链表的头部。
`bottom`链表代表较早之前访问过的对象列表。当`top`链表满了或达到某这阈值，就会把`top`链表尾部的对象添加到`bottom`链表的头部。从缓存中淘汰对象时，从`bottom`尾部开始淘汰。


// insert at top of lru

void lru_insert_top(LRUObject *o) 
  {
    o->lru = this; //class LUR
    top.push_front(&o->lru_link);
  }
 

class LRUObject {
public:
friendclass LRU;
private:
class LRU *lru;// LRU算法的真正实现者
  xlist<LRUObject *>::item lru_link; // 记录自己在双向链表里的位置，移动或删除对象时，操作会很快
bool lru_pinned;

inline LRUObject::~LRUObject() 
  {
   if (lru) {
     lru->lru_remove(this);
   }
   }//# c++ new(this)
};

只要你的对象继承了 LRUObject，
就能被 LRU 缓存自动管理，
无需自己手动维护链表节点和指针，
使用起来非常方便和安全。