聊聊如何实现 LRU 缓存算法

LRU 算法全称是最近最少使用算法（Least Recently Use），是一种简单的缓存策略。顾名思义，LRU 算法会选出最近最少使用的数据进行淘汰。,那么什么是缓存呢？缓存专业点可以叫一种提高数据读取性能的技术，可以有效解决存储器性能和容量的矛盾，是一种空间换时间的设计思想，比如我们常见的内存是硬盘的缓存，Cache 是内存的缓存，浏览器本地存储是网络访问的缓存......,LRU 有许多应用场景，例如：,146. LRU 缓存，请你设计并实现一个满足  LRU (最近最少使用) 缓存约束的数据结构。,实现 LRUCache 类：,函数 get 和 put 必须以 O (1) 的平均时间复杂度运行。,示例：,(1) 首先，题目中提到函数 get 和 put 必须以 O (1) 的平均时间复杂度运行，很自然地我们可以想到应该使用哈希表。,(2) 其次，当访问数据结构中的某个 key 时，需要将这个 key 更新为最近使用；另外如果 capacity 已满，需要删除访问时间最早的那条数据。这要求数据是有序的，并且可以支持在任意位置快速插入和删除元素，链表可以满足这个要求。,(3) 结合 1，2 两点来看，我们可以采用哈希表 + 链表的结构实现 LRU 缓存。,如上图所示，就是哈希表 + 链表实现的 LRU 缓存数据结构，有以下几个问题解释一下：,(1) 为什么这里要使用双向链表，而不是单向链表？我们在找到了节点，需要删除节点的时候，如果使用单向链表的话，后驱节点的指针是直接能拿到的，但是这里要求时间复杂度是 O (1)，要能够直接获取到前驱节点的指针，那么只能使用双向链表。,(2) 哈希表里面已经保存了 key ，那么链表中为什么还要存储 key 和 value 呢，只存入 value 不就行了？当我们删除节点的时候，除了需要删除链表中的节点，还需要删除哈希表中的节点。删除哈希表中的节点需要知道 key，所以在链表的节点中需要存储 key 和 value，当删除链表节点时拿到 key，再根据 key 到哈希表中删除节点。,(3) 虚拟头节点和虚拟尾节点有什么用？虚拟节点在链表中被广泛应用，又称为哨兵节点，通常不保存任何数据。使用虚拟节点我们可以统一处理链表中所有节点的插入删除操作，而不用考虑头尾两个节点的特殊情况。,(1) Golang,(2) Java,(3) 运行结果,代码运行的返回结果如下，其中头尾两个 key=0, value=0 的节点是虚拟节点，请忽略。,第 1 步：初始化数据结构。,第 2 步：插入节点 key1。,第 3 步：插入节点 key2。 此时 key2 插入到链表头部。,第 4 步：插入节点 key3。 此时 key3 插入到链表头部。,第 5 步：插入节点 key4。当前 capacity 容量达到上限（3），分为 2 步：,使用 removeTail() 方法删除链表尾部的节点 key1，从 removeTail() 方法的返回值得到 node，再根据 node.key 得到 key1，然后去哈希表删除节点 key1。,然后插入节点 key4，此时 key4 在链表头部。,第 6 步：读取 key2 的值，将 key2 移动到链表头部。 ,