您的位置:首页 > 文旅 > 旅游 > 数据结构之LRUCache

数据结构之LRUCache

2024/12/23 2:42:17 来源:https://blog.csdn.net/2301_80854132/article/details/141409321  浏览:    关键词:数据结构之LRUCache

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

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

所属专栏:数据结构(Java版) 

目录

LRU Cache的概念 

LRU Cache的实现

模拟实现LRU Cache

相关练习 


 

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 的学习之旅就到此结束啦!我们下一期再一起学习吧!

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com