操作系统-2-存储管理之LRU页面置换算法(LeetCode146)
LRU缓存机制
题目：运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。
它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) – 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) – 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。
当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
示例：
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
代码：
1 class LRUCache { 2 3 public LRUCache(int capacity) { 4 5 } 6 7 public int get(int key) { 8 9 } 10 11 public void put(int key, int value) { 12 13 } 14 } 15 16 /** 17 * Your LRUCache object will be instantiated and called as such: 18 * LRUCache obj = new LRUCache(capacity); 19 * int param_1 = obj.get(key); 20 * obj.put(key,value); 21 */
LRU页面置换算法(最近最少使用使用算法)
原理：
选择最后一次访问时间距离当前时间最长的一页并淘汰之。即淘汰没有使用的时间最长的页
每页设置访问时间戳，每当页面被访问时，该页面的时间戳被更新；
发生缺页中断时，淘汰时间戳最小的页面；
如图：图中的页面为三页，依次向存储中加入432143543215这些数字。
而存储空间只能存储三个页面，所以会按照上述规则不断淘汰已经存储在页面中的数字。
解题思路(logN的思路)：
知道了LRU的置换规则后，由于此题需要存储的是key和value,所以
首先，需要建一个类node，存放三样东西，key,value,times(时间戳)
其次，选择一种合适的数据结构来解决存储优先级问题，此处我们采用内部是小顶堆的PriorityQueue优先级队列用来实现times最小的元素在队头
但是我们会在让新元素入队之前可能会删除队列中指定元素，当然可以去遍历队列，但是这样太慢了
我们可以再用一种HashMap的数据集合用来存储节点，以便快速通过node的key来得到整个node。
最后，便是处理逻辑关系，写题目要求的get,put方法了
解题代码详解(logN)：
1 public class node implements Comparable<node>{ 2 private int Key;//键 3 private int Value;//值 4 private int Times;//时间戳 5 node() {} 6 node(int key, int value, int time) { 7 this.Key = key; 8 this.Value = value; 9 this.Times = time; 10 } 11 public int getKey() { 12 return Key; 13 } 14 15 public void setKey(int Key) { 16 this.Key = Key; 17 } 18 19 public int getValue() { 20 return Value; 21 } 22 23 public void setValue(int Value) { 24 this.Value = Value; 25 } 26 27 public int getTimes() { 28 return Times; 29 } 30 31 public void setTimes(int Times) { 32 this.Times = Times; 33 } 34 35 @Override 36 public int compareTo(node o) { 37 //实现times最小的元素在队头 38 return Times - o.Times; 39 } 40 } 41 42 class LRUCache { 43 PriorityQueue<node> KeyValueTimes = new PriorityQueue();//用于实现优先级顺序 44 Map<Integer, node> nodeset;//用于O(1)取出某个具体的node 45 public int Capacity = 0;//我的cache中最大容量 46 public int nownum = 0;//cache的实时元素个数 47 public int tim = 0;//时间戳 48 49 public LRUCache(int capacity) { 50 this.Capacity = capacity;//设置cache容量 51 nodeset = new HashMap<Integer, node>(capacity);//用于O(1)取出某个具体的node，容量依然设置为capacity 52 } 53 54 public int get(int key) { 55 if(this.Capacity == 0)//判断容量是否为空，为空则直接返回-1 56 return -1; 57 node nownode = nodeset.get(key);//通过HashMap，快速通过key键快速得到node 58 if (nownode == null) {//如果key这个键没在队列中，则返回-1 59 return -1; 60 }else{ 61 KeyValueTimes.remove(nownode);//移除队列中当前的这个node 62 nownode.setTimes(tim++);//更新当前这个node的时间戳 63 KeyValueTimes.offer(nownode);//再把它放回去 64 } 65 return nownode.getValue(); 66 } 67 68 public void put(int key, int value) { 69 if(this.Capacity == 0)//判断容量是否为空,为空则不进行put 70 return; 71 node thisnode = new node(key,value,tim++); 72 node oldnode = nodeset.get(key); 73 if(oldnode == null){//队列里不存在这个key 74 if(nownum < this.Capacity){//没装满 75 KeyValueTimes.offer(thisnode);//在队列里添加新node 76 nodeset.put(key,thisnode);//在HashMap里添加新node 77 nownum++;//更新当前cache的元素个数 78 } 79 else{//装满了，需要LRU,最近最久为使用被移除 80 nodeset.remove(KeyValueTimes.poll().getKey());//移除队列里的队头，移除HashMap对应的那个node 81 KeyValueTimes.offer(thisnode);//在队列里添加新node 82 nodeset.put(key,thisnode);//在HashMap里添加新node 83 } 84 } 85 else{//队列里存在这个key 86 KeyValueTimes.remove(oldnode);//移除队列里键为key的node，移除HashMap对应的那个node 87 nodeset.remove(oldnode.getKey()); 88 KeyValueTimes.offer(thisnode);//在队列里添加新node,这里新的node的value值可能会不一样，所以更新了value 89 nodeset.put(key,thisnode);//在队列里添加新node,这里新的node的value值可能会不一样，所以更新了value 90 } 91 } 92 }