运用你所掌握的数据结构,设计和实现一个
LRU
(最近最少使用) 缓存机制 。
实现LRUCache
类:
LRUCache(int capacity)
以正整数作为容量 capacity 初始化LRU
缓存
int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。进阶:你是否可以在 O(1) 时间复杂度内完成这两种操作?
LinkedHashMap
LinkedHashMap
不熟悉的朋友们可以简单的将它理解成HashMap
。 下图展示了HashMap
的存储结构LinkedHashMap
只是多了一条链表串起里面的元素LinkedHashMap
是按照顺序存储的。但是LinkedHahsMap
也无法做到按照使用频率进行排序啊?大家都知道他是按照添加顺序排序的!!!LinkedHashMap
改造LinkedHashMap
的确无法满足情况,但是我们稍微看下源码能够发现在put之后都会执行下afterNodeInsertion
这个方法。这也是HashMap
留给LinkedHashMap
做的扩展!removeNode
就是将最前面的数据。想要进入这个方法就需要removeEldestEntry
判断。LinkedHashMap
默认是false . 所以我们只需要重写他就行了。但是还是在get值的时候如何保值在最后面呢?我们仔细看下源码就能够发现在get
中有这个一个方法afterNodeAccess
。他的作用就是将get的元素移位值后面。正好符合我们LRU
的策略特征LinkedHashMap
就非常容易的实现了LRU策略!但是本题的意思是想考察我们自己是如何实现的,而不是巧妙对现有的工具改造的!不过上面对LinkedHashMap
的确改造的很巧这是不可否认的!下面我们就尝试自己来实现下这种方式!
首先我们需要确定需要用到Hash结合链表来实现。Hash我们自然使用HashMap
来存储数据为的就是方便定位数据。定位到数据就需要操作链表将数据实时移位值链表尾部,每次淘汰是将链表首位移除既可。为了方便我们操作链表这里的链表肯定是双链表的!
preNode
,nextNode
分别指向前后节点方法名 | 作用 |
---|---|
addToTail | 将节点添加值链表尾部 |
moveToTail | 将已经存在于链表中的节点移动到链表的尾部 |
removeHeadNode | 删除链表中第一个节点,注意是边界节点后第一个节点 |