LRU介绍和实现

川长思鸟来 2022-02-18 14:51 228阅读 0赞

LRU全称是Least Recently Used，即最近最久未使用的意思。

LRU算法的设计原则是：**如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小**。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。（这一段是找的，让大家理解一下什么是LRU）。

说一下我们什么时候见到过LRU：其实老师们肯定都给大家举过这么个例子：你在图书馆，你把书架子里的书拿到桌子上。。但是桌子是有限的，你有时候不得不把一些书放回去。这就相当于内存和硬盘。这个例子都说过吧？

LRU就是记录你最长时间没看过的书，就把它放回去。在cache那里见过吧

然后最近在研究redis，又看到了这个LRU，所以就想写一下吧。

题目：设计一个结构，这个结构可以查询K-V，但是容量有限，当存不下的时候就要把用的年代最久远的那个东西扔掉。

其实思路很简单，我们维护一个双向链表即可，get也就是使用了，我们就把把它提到最安全的位置。新来的KV就依次放即可。

我们就先写这个双向链表结构

先写节点结构：

public static class Node<V> {
    		public V value;
    		public Node<V> last;//前
    		public Node<V> next;//后
    
    		public Node(V value) {
    			this.value = value;
    		}
    	}

然后写双向链表结构： 我们没必要把链表操作都写了，分析一下，我们只有三个操作：

1、加节点

2、使用了某个节点就把它调到尾，代表优先级最高

3、把优先级最低的移除，也就是去头部

（不会的，翻我之前的链表操作都有写）

public static class NodeDoubleLinkedList<V> {
    		private Node<V> head;//头
    		private Node<V> tail;//尾
    
    		public NodeDoubleLinkedList() {
    			this.head = null;
    			this.tail = null;
    		}
    
    		public void addNode(Node<V> newNode) {
    			if (newNode == null) {
    				return;
    			}
    			if (this.head == null) {//头空
    				this.head = newNode;
    				this.tail = newNode;
    			} else {//头不空
    				this.tail.next = newNode;
    				newNode.last = this.tail;//注意让本节点前指针指向旧尾
    				this.tail = newNode;//指向新尾
    			}
    		}
    /*某个点移到最后*/
    		public void moveNodeToTail(Node<V> node) {
    			if (this.tail == node) {//是尾
    				return;
    			}
    			if (this.head == node) {//是头
    				this.head = node.next;
    				this.head.last = null;
    			} else {//中间
    				node.last.next = node.next;
    				node.next.last = node.last;
    			}
    			node.last = this.tail;
    			node.next = null;
    			this.tail.next = node;
    			this.tail = node;
    		}
    /*删除第一个*/
    		public Node<V> removeHead() {
    			if (this.head == null) {
    				return null;
    			}
    			Node<V> res = this.head;
    			if (this.head == this.tail) {//就一个
    				this.head = null;
    				this.tail = null;
    			} else {
    				this.head = res.next;
    				res.next = null;
    				this.head.last = null;
    			}
    			return res;
    		}
    
    	}

链表操作封装完了就要实现这个结构了。

具体思路代码注释

public static class MyCache<K, V> {
    		//为了kv or vk都能查
    		private HashMap<K, Node<V>> keyNodeMap;
    		private HashMap<Node<V>, K> nodeKeyMap;
    		//用来做优先级
    		private NodeDoubleLinkedList<V> nodeList;
    		private int capacity;//容量
    
    		public MyCache(int capacity) {
    			if (capacity < 1) {//你容量连1都不给，捣乱呢
    				throw new RuntimeException("should be more than 0.");
    			}
    			this.keyNodeMap = new HashMap<K, Node<V>>();
    			this.nodeKeyMap = new HashMap<Node<V>, K>();
    			this.nodeList = new NodeDoubleLinkedList<V>();
    			this.capacity = capacity;
    		}
    
    		public V get(K key) {
    			if (this.keyNodeMap.containsKey(key)) {
    				Node<V> res = this.keyNodeMap.get(key);
    				this.nodeList.moveNodeToTail(res);//使用过了就放到尾部
    				return res.value;
    			}
    			return null;
    		}
    
    		public void set(K key, V value) {
    			if (this.keyNodeMap.containsKey(key)) {
    				Node<V> node = this.keyNodeMap.get(key);
    				node.value = value;//放新v
    				this.nodeList.moveNodeToTail(node);//我们认为放入旧key也是使用过
    			} else {
    				Node<V> newNode = new Node<V>(value);
    				this.keyNodeMap.put(key, newNode);
    				this.nodeKeyMap.put(newNode, key);
    				this.nodeList.addNode(newNode);//加进去
    				if (this.keyNodeMap.size() == this.capacity + 1) {
    					this.removeMostUnusedCache();//放不下就去掉优先级最低的
    				}
    			}
    		}
    
    		private void removeMostUnusedCache() {
    			//删除头
    			Node<V> removeNode = this.nodeList.removeHead();
    			K removeKey = this.nodeKeyMap.get(removeNode);
    			//删除掉两个map中的记录
    			this.nodeKeyMap.remove(removeNode);
    			this.keyNodeMap.remove(removeKey);
    		}
    	}