数据结构之LRUCache

找往期文章包括但不限于本期文章中不懂的知识点：

个人主页：我要学编程(ಥ_ಥ)-CSDN博客

所属专栏：数据结构（Java版）

LRU Cache的概念

LRU是Least Recently Used的缩写，意思是最近最少使用，它是一种Cache替换算法。什么是Cache？狭义的Cache指的是位于CPU和主存间的快速RAM（random-access memory的缩写，即我们日常生活中所说的运行内存），通常它不像系统主存那样使用DRAM技术，而使用昂贵但较
快速的SRAM技术。广义上的Cache指的是位于速度相差较大的两种硬件之间，用于协调两者数据传输速度差异的结构。除了CPU与主存之间有Cache，内存与硬盘之间也有Cache，乃至在硬盘与网络之间也有某种意义上的Cache一称为lnternetl临时文件夹或网络内容缓存等。
Cache的容量有限，因此当Cache的容量用完后，而又有新的内容需要添加进来时，就需要挑选并舍弃原有的部分内容，从而腾出空间来放新内容。LRUCache的替换原则就是将最近最少使用的内容替换掉。其实，LRU译成最久未使用会更形象，因为该算法每次替换掉的就是一段时间内最久没有使用过的内容。

LRU Cache的实现

实现LRU Cache的方法和思路很多，但是要保持高效实现O(1)的put和get，那么使用双向链表和哈希表的搭配是最高效和经典的。使用双向链表是因为双向链表可以实现任意位置O(1)的插入和删除，使用哈希表是因为哈希表的增删查改也是O(1)。

在Java的集合类中有一个类和LRU Cache的实现类似——LinkedHashMap，其底层也是哈希表+双向链表。

每次使用get方法，访问数据后，会把数据放到当前双向链表的最后。
当accessOrder为true时，get方法和put方法都会调用recordAccess方法使得最近使用的Entry移到双向链表的末尾；当accessOrder为默认值false时，从源码中可以看出recordAccess方法什么也不会做。

模拟实现LRU Cache

模式实现LRU Cache主要就是实现两个方法：put 和 get。

前期准备：

哈希表+双向链表：

    // 节点static class ListNode{public int key;public int val;public ListNode prev;public ListNode next;public ListNode(int key, int val) {this.key = key;this.val = val;}}// 这个哈希表中存放的是一个一个的节点，快速查找public HashMap<Integer, ListNode> hashMap;// 带头节点和尾节点便于修改，速度非常快public ListNode head;public ListNode tail;public int capacity; // LRU Cache容量public int usedSize; // 记录使用个数public LRUCache(int capacity) {this.hashMap = new HashMap<>();this.head = new ListNode(-1, -1);this.tail = new ListNode(-1, -1);this.head.next = this.tail;this.tail.prev = this.head;this.capacity = capacity;}

实现 put 方法：

思路：首先，得在哈希表中查找是否存在该key。如果存在，只需要更新其 val值即可，然后再把这个节点移动到链表的尾部（先删除，在尾插）；如果不存在，就新实例化一个节点，然后再尾插到链表尾部，接着usedSize++，检查容量是否满了。满了就得删除头结点（最近最久未被使用）

代码实现：

    public void put(int key, int val) {// 首先得查找hashmap中是否有这个元素ListNode node = hashMap.get(key);if (node == null) {ListNode newNode = new ListNode(key, val);hashMap.put(key, newNode); // 哈希表存一份usedSize++; // 个数++addToTail(newNode); // 把该节点移到链表末尾if (usedSize > capacity) {// 移除链表的头节点ListNode head = moveHead();// 将哈希表中的元素移除hashMap.remove(head.key);usedSize--;}} else {// 存在这个元素，更新val即可node.val = val; // 这里就已经把哈希表中的val更新了moveTail(node);}}private ListNode moveHead() {ListNode del = head.next;head.next = del.next;del.next.prev = head;return del;}private void moveTail(ListNode node) {// 先删除node节点，在尾插到末尾removeNode(node);addToTail(node);}private void addToTail(ListNode node) {node.next = tail;node.prev = tail.prev;tail.prev.next = node;tail.prev = node;}private void removeNode(ListNode newNode) {newNode.prev.next = newNode.next;newNode.next.prev = newNode.prev;}

实现 get 方法：

思路：直接在哈希表中查找。如果不存在，返回-1；如果存在，就返回其对应的val，并在此之前把这个节点移动到链表的尾部。

代码实现：

    public Integer get(int key) {if (hashMap.get(key) == null) {return -1;} else {// 把这个移到链表尾部moveTail(hashMap.get(key));return hashMap.get(key).val;}}

相关练习

146. 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) 的平均时间复杂度运行。

示例：
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4
提示：

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put

思路一：就是直接手动实现一个LRU Cache，也就是我们模拟实现LRU Cache的代码。

思路二：在Java中LInkedHashMap是类似于LRU Cache的，因此我们直接用这个来写也是可以的。

class LRUCache extends LinkedHashMap<Integer, Integer>{private int capacity;public LRUCache(int capacity) {super(capacity, 0.75F, true);this.capacity = capacity;}public int get(int key) {return super.getOrDefault(key, -1);}public void put(int key, int value) {super.put(key, value);}// 注意：这个是用来判断是否需要移除元素的，因此一定要重写（默认是false）@Overrideprotected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {return size() > capacity; }
}

好啦！本期数据结构之LRUCache 的学习之旅就到此结束啦！我们下一期再一起学习吧！