摘要:但是哈希表无序的,我们没办法在缓存满时,将最早更新的元素给删去。所以双向链表是最好的选择。我们用双向链表实现一个队列用来记录每个元素的顺序,用一个哈希表来记录键和值的关系,就行了。
LRU Cache
双向链表加哈希表 复杂度Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
时间 Get O(1) Set O(1) 空间 O(N)
思路缓存讲究的就是快,所以我们必须做到O(1)的获取速度,这样看来只有哈希表可以胜任。但是哈希表无序的,我们没办法在缓存满时,将最早更新的元素给删去。那么是否有一种数据结构,可以将先进的元素先出呢?那就是队列。所以我们将元素存在队列中,并用一个哈希表记录下键值和元素的映射,就可以做到O(1)获取速度,和先进先出的效果。然而,当我们获取一个元素时,还需要把这个元素再次放到队列头,这个元素可能在队列的任意位置,可是队列并不支持对任意位置的增删操作。而最适合对任意位置增删操作的数据结构又是什么呢?是链表。我可以用链表来实现一个队列,这样就同时拥有链表和队列的特性了。不过,如果仅用单链表的话,在任意位置删除一个节点还是很麻烦的,要么记录下该节点的上一个节点,要么遍历一遍。所以双向链表是最好的选择。我们用双向链表实现一个队列用来记录每个元素的顺序,用一个哈希表来记录键和值的关系,就行了。
注意这题更多的是考察用数据结构进行设计的能力,再写代码时尽量将子函数拆分出来,先写个整体的框架。
移出链表最后一个节点时,要记得在链表和哈希表中都移出该元素,所以节点中也要记录Key的信息,方便在哈希表中移除
代码public class LRUCache { int size; int capacity; ListNode tail; ListNode head; Mapmap; public LRUCache(int capacity) { this.head = new ListNode(-1,-1); this.tail = new ListNode(-1,-1); head.next = tail; tail.prev = head; this.size = 0; this.capacity = capacity; this.map = new HashMap (); } public int get(int key) { ListNode n = map.get(key); if(n != null){ moveToHead(n); return n.val; } else { return -1; } } public void set(int key, int value) { ListNode n = map.get(key); if(n == null){ n = new ListNode(value, key); attachToHead(n); size++; } else { n.val = value; moveToHead(n); } // 如果更新节点后超出容量,删除最后一个 if(size > capacity){ removeLast(); size--; } map.put(key, n); } // 将一个孤立节点放到头部 private void attachToHead(ListNode n){ n.next = head.next; n.next.prev = n; head.next = n; n.prev = head; } // 将一个链表中的节点放到头部 private void moveToHead(ListNode n){ n.prev.next = n.next; n.next.prev = n.prev; attachToHead(n); } // 移出链表最后一个节点 private void removeLast(){ ListNode last = tail.prev; last.prev.next = tail; tail.prev = last.prev; map.remove(last.key); } public class ListNode { ListNode prev; ListNode next; int val; int key; public ListNode(int v, int k){ this.val = v; this.prev = null; this.next = null; this.key = k; } } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/64530.html
摘要:剑指缓存实现声明文章均为本人技术笔记,转载请注明出处解题思路缓存两种功能获取的对应,不存在返回版本版本设置缓存已满,删除最近最久未被使用的节点,添加新节点进缓存缓存未满,节点存在,修改节点不存在,添加新节点进缓存解题思路由于缓存插入和删除 剑指offer/LeetCode146/LintCode134_LRU缓存实现 声明 文章均为本人技术笔记,转载请注明出处[1] https://s...
摘要:当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。但是无法保证是,也无法保证更新数据时是,因为这两个操作必然要遍历队列。因为可以通过来判断是否有这个节点。 题目地址:https://leetcode-cn.com/probl...题目描述:运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获...
摘要:缓存算法我是,我会统计每一个缓存数据的使用频率,我会把使用最少的缓存替换出缓存区。浏览器就是使用了我作为缓存算法。在缓存系统中找出最少最近的对象是需要较高的时空成本。再来一次机会的缓存算法,是对的优化。直到新的缓存对象被放入。 缓存 什么是缓存? showImg(https://segmentfault.com/img/bVusZg); 存贮数据(使用频繁的数据)的临时地方,因为取原始...
摘要:酷库,每天两分钟,了解一个流行库。而直接将数据保存在程序变量中,最经济快捷。但是这样就会带来一些其他问题,比如缓存更新缓存过期等。用于在内存中管理缓存数据,并且支持算法。可以让程序不依赖任何外部数据库实现缓存管理。 NPM酷库,每天两分钟,了解一个流行NPM库。 为了优化程序性能,我们常常需要奖数据缓存起来,根据实际情况,我们可以将数据存储到磁盘、数据库、redis等。 但是有时候要缓...
阅读 1083·2021-11-23 09:51
阅读 1048·2021-10-18 13:31
阅读 2922·2021-09-22 16:06
阅读 4086·2021-09-10 11:19
阅读 2149·2019-08-29 17:04
阅读 372·2019-08-29 10:55
阅读 2407·2019-08-26 16:37
阅读 3339·2019-08-26 13:29