写在前面

LRU (Least Recently Used) 算法就是一种缓存淘汰策略, 见名知意就是删除掉最久未使用的内存。题目要求get和put在$O(1)$时间内完成，哈希表可以做到快速的存取，但是还需要涉及到更新关键字的位置（最近使用时间），就需要做到快速的插入和删除，这个链表可以做到。总的来说，链表和哈希表的结合就可以实现该算法。

  • 哈希表：需要快速找到并更新值，因此pair对的key对应着关键字，value就对应着链表中的一个节点（Node*）
    • unordered_map<int,Node*> map
  • 链表：单向 or 双向？
    • 其实都可以，只不过就是空间换时间，时间换空间。
    • 先考虑为什么可能需要考虑双向？因为我们删除节点时，需要将当前节点的前驱节点与后驱节点连接起来。因此可能需要对节点增加一个前向指针，从而使用双向链表。
    • 单向链表也可以做到，只不过需要一个虚拟头结点，这样也可以获取当前节点的前驱节点，从前往后遍历即可找到。
  • 为了方便，使用双向链表，同时增加虚拟头尾节点（dummy head,tail）
  • 为什么node需要包含key？
    • 因为，当超出容量需要删除时，需要用到key信息去删除map中的键值对
      手写小笔记

具体分步实现

从需求出发，列出所需要的数据结构和构造方法

节点类（结构体）

  • 节点包含内容：
    • key,value信息
    • 前驱后驱指针： Node* prev，Node* next
    • 构造函数:Node(int k,int v):key(k),value(v),prev(nullptr),next(nullptr){}

双向链表

  • 头尾虚拟节点：head,tail
  • 初始化函数：特别注意对虚拟节点的初始化操作

  • 对应的插入、删除、移动等操作

    class DoubleList{
private:
Node* head,*tail;
public:
DoubleList(){
    Node* head=new Node(-1,-1);
    Node* tail=new Node(-1,-1); // 根绝题目范围确定初始值
    head->next=tail;  // 前驱在初始化时已经置空
    tail->prev=next;  // 后驱在初始化时已经置空
}
// other operations 
};

LRU算法

将上述的类节点、双向链表以及哈希表结合起来，实现LRU算法的数据结构

成员变量及构造函数

  • 结构体节点以及记录最大容量的capicity
  • 哈希表、将双向链表中的成员提取出来

  • 构造函数

    class LRUCache {
private:
// 节点：结构体
struct Node{
    int key,val;
    Node* prev,*next;
    Node(int k,int v):key(k),val(v),next(nullptr),prev(nullptr){}
};
// DoubleList相关的两个虚拟头尾
Node* head,*tail;
// hashmap
unordered_map<int, Node*>map;
// 容量
int capacity;
public:
LRUCache(int capacity) {
    // 容量
    this->capacity=capacity;
    // 初始化双向链表
    head=new Node(-1,-1);
    tail=new Node(-1,-1);
    head->next=tail;
    tail->prev=head;
}
// get 和 put 方法
};

对链表的操作

就是插入、删除操作，或者移动，需要注意的是插入和删除操作，同时需要对哈希表中的键值对进行操作。

  • 插入、移动及删除操作
  • 注意删除时，尽量删除对应的堆内存，切记对hashmap也要erase操作

  • 写的比较杂，可以拆分操作的

    // 更新位置
void moveToEnd(Node* node){
// node的前后节点
Node* left=node->prev;
Node* right=node->next;
// 连接前后
left->next=right;
right->prev=left;
// 插入末尾
Node* endLeft=tail->prev;
endLeft->next=node;
node->prev=endLeft;
node->next=tail;
tail->prev=node;
}
// 删除头部元素
void deleteHead(){
// 删除链表中的节点
Node* node=head->next;
Node* nodeRight=node->next;
head->next=nodeRight;
nodeRight->prev=head;
// 删除map中的key,value
map.erase(node->key);
// 删除节点对应的内存
delete(node);
}
// 添加新节点到到末尾
void addToend(int key,int value){
Node* node=new Node(key,value);
Node* endLeft=tail->prev;
// 插入链表末尾
endLeft->next=node;
node->prev=endLeft;
node->next=tail;
tail->prev=node;
// 增加hashMap中的值
// map.insert(make_pair(key,node));
map[key]=node;
}

具体的成员函数实现

get 和 put 方法实现，在双向链表中，这里默认向链表尾添加元素，链表头删除元素，也就是说越往后数据越新，越靠近头结点越旧。

  • 对于get方法
    • 如果存在，则直接返回，并且更新位置（移动到末尾）
    • 如果不存在，则返回-1（比较简单）

  • 对于put方法

    • 如果存在：更新值，并更新位置

    • 不存在，则put；put时要判断容量：不够，则先删除，再put,够了，直接put

      int get(int key) {
if(!map.count(key))
    return -1;
Node* node=map[key];
// 注意要更新该node的位置
moveToEnd(node);   
return node->val;
}

void put(int key, int value) {
if(map.count(key)){
// 更新值
Node* node=map[key];
node->val=value;
// 更新位置
moveToEnd(node);
}
else{
// 判断是否满了
// yes->删除头元素后插入到最后
if(map.size()==capacity){
    deleteHead(); 
}
addToend(key,value);
}
}

$\cdots$ end $\cdots$