You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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.
1. 什么是LRU Cache?
之前,在LeetCode上看到一个LRU Cache实现的题目,题目描述是这样的:
简单的说,就是保证基本的get和set的功能的同时,还要保证最近访问(get或put)的节点保持在限定容量的Cache中,如果超过容量则应该把LRU(近期最少使用)的节点删除掉。
那么我们思考一个问题:如何设计实现一个LRU Cache?
那么,我们可能需要使用类似这样的数据结构去实现这个LRU Cache:
这不就是LinkedHashMap吗!
这样做的好处是,
get
和set
在不冲突的情况下可以保证O(1)的复杂度,同时,也可以通过双向链表来保证LRU的删除
和更新
操作也能保证O(1)的复杂度。2.实现思路
在学习了HashMap(#7 )和LinkedHashMap(#8 )后,是不是觉得这俩数据结构简直太适合做LRU Cache了!那么动手实现一下:
基于HashMap和双向链表的实现
基于LinkedHashMap的实现
HashMap+双向链表?这不就是LinkedHashMap吗!
The text was updated successfully, but these errors were encountered: