运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get
和 写入数据 put
。
获取数据 get(key)
- 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
写入数据 put(key, value)
- 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作?
示例:
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
在解答这到题之前我们先看看看什么是LRU
LRU (英文:Least Recently Used )它是内存管理的一种页面置换算法,对于在内存中但又不用的数据块(内存块)叫做LRU,操作系统会根据哪些数据属于LRU而将其移出内存而腾出空间来加载另外的数据。
LRU算法:最近最少使用,简单来说就是将数据块中,每次使用过的数据放在数据块的最前端,然后将存在的时间最长的,也就是数据块的末端的数据剔除掉,这个算法的精髓在于如果一块数据最近被访问,那么它将来被访问的几率也很高,根据数据的历史访问来淘汰长时间未使用的数据,这就是LRU算法。
那么为什么需要这个算法呢??
关于操作系统的内存管理,如何节省利用容量不大的内存为最多的进程提供资源,一直是研究的重要方向。而内存的虚拟存储管理,是现在最通用,最成功的方式—— 在内存有限的情况下,扩展一部分外存作为虚拟内存,真正的内存只存储当前运行时所用得到信息。这无疑极大地扩充了内存的功能,极大地提高了计算机的并发度。虚拟页式存储管理,则是将进程所需空间划分为多个页面,内存中只存放当前所需页面,其余页面放入外存的管理方式。
然而,有利就有弊,虚拟页式存储管理增加了进程所需的内存空间,却也带来了运行时间变长这一缺点:进程运行过程中,不可避免地要把在外存中存放的一些信息和内存中已有的进行交换,由于外存的低速,这一步骤所花费的时间不可忽略。因而,采取尽量好的算法以减少读取外存的次数,也是相当有意义的事情。
所以,我们解题的思路就出来了:
1.我们需要用栈的思想来想一下。栈顶就是最近刚访问的,而栈底就是最久没访问过的。
2.需要以个HashMap来保证里面的数据不重复。
需要明确的:
1.添加节点:新节点插入到表头即可,时间复杂度O(1)
2.查找节点:每次节点被查询到时,将节点移动到链表头部,时间复杂度O(n)
3. 替换节点:查找到后替换(更新节点value),将节点移动到链表头部;
对于下一个页面的情况;
1.栈中存在:则需要更新栈顶元素,就是将当前存在的页号放到栈顶。
2.栈中并未存在:
2.1.栈未满:直接将该页放到栈顶。
2.2.栈已满:需要选一个最近最久未访问的将它置换出,然后将该页放到栈顶。
代码如下:
class LRUCache {
private HashMap<Integer,Integer> map;
private Stack<Integer> stack;
private int size;
public LRUCache(int capacity) {
map = new HashMap<>(capacity);
stack = new Stack<Integer>();
size = capacity;
}
public int get(int key) {
if(!stack.contains(key)){
return -1;
}
boolean old = stack.remove(Integer.valueOf(key)); //栈中存在
stack.push(key);
return map.get(key);
}
public void put(int key, int value) {
if(stack.contains(key)){
stack.remove(Integer.valueOf(key));
}else{
if(stack.size() == size){
int count = stack.remove(0);
map.remove(count);
}
}
stack.add(key);
map.put(key,value);
}
}