LRU Cache 经典的算法题实现是“双端链表 + 哈希映射”。双端链表存储值（或指向值的索引），从而实现 O(1)的节点移动与增删。哈希映射存储键与链表的节点指针，从而实现 O(1) 访问与查询。

C++ 代码类似这样：

template<typename Key, typename Value, size_t Capacity> // Capacity: 最大容量  
class LRUCache {
    std::unordered_map<Key, typename std::list<Value>::iterator> m_map,
    std::list<Value> m_list,
    size_t m_size, // 现有元素数  
}

虽然复杂度已经够低了，但常数项的优化空间依然很大，因为链表本身并不符合局部性原理。

那么如何更高效地实现呢？很简单，让数据尽量连续。既然最大容量已知，就可以用连续缓冲区存放值，通过二级索引代替链表，看起来像这样：（Rust）

struct ListNode<V> {
    // 数据，MaybeUninit 表示可能未初始化
    data: MaybeUninit<V>,
    // 使用 u32 压缩空间，不使用 usize
    next: u32, // 下一个节点的索引
    prev: u32, // 上一个节点的索引
}

struct LRUCache<K, V, const CAP: usize>{
    list: [ListNode<V>, CAP], // 链表节点数组
    head: u32,   // 活跃的首节点索引，自定义特殊值表示不存在
    tail: u32,   // 活跃的尾节点索引，自定义特殊值表示不存在
    idle: [u32, CAP], // 存储空闲的节点索引
    idle_len: u32,    // 空闲节点数，空闲索引必然存储在前 len 个位置
    map: HashMap<K, u32>, // 从键映射到链表节点的索引
}

整体思路和经典实现一样，但我们使用连续内存实现链表并存放数据 idle 类似固定容量的动态数组，容量固定但是元素个数是动态的，我们优先操作尾部元素以保证 O(1) 的操作开销和更好的缓存命中率。 使用 u32 代替 usize 以压缩空间。

注：u32 表示 32bits 的无符合整数；usize/size_t 通常为 8Bytes；而 X86_64 中单缓存行通常为 64 B。

初始状态下，idlen_len == CAP，表示缓存完全空闲。

• 查找元素且缓存未命中，则尝试从空闲队列中取出可用索引并设置节点内容，将节点设置为链表的尾节点以表示最近访问，然后将元素插入 data 中。

• 查找元素且缓存命中，则直接根据索引访问节点并读取数据。将当前节点设置为尾节点即可表示最近访问，这只需调整几个相关节点的 next/prev 以及整体的 head/tail，无需拷贝数据，类似 C++ std::list 的 splice。

• 查找元素且缓存未命中，但空闲队列为空，说明需要移除最久未使用的数据。只需移除首节点和对应的元素，然后重复上面的插入节点步骤。