战五渣手撕LRU

﹏ヽ暗。殇╰゛Y 2023-05-22 22:20 38阅读 0赞

## 背景介绍 ##

我们从一个程序的运行过程说起。

在运行之前，QQ，就是一堆文件，它静静地躺在磁盘的某个角落。当我们双击QQ图标时，操作系统老大就会找到磁盘中QQ的安装目录，并将其中的文件装载到内存，然后安排CPU阿甘进行相关的运算，小企鹅就跑起来了。

我们知道磁盘的空间非常大，内存与之相比，是非常小的。所以并不是一次性把QQ的所有文件加载到内存，那样的话，电脑根本不能同时运行多个程序（就算一次性全部加载进来，在一段很短的时间内，其实只有某一页是被集中访问的，其他大部分数据被晾在了一边，这叫**局部性原理**）。

磁盘存储是以块为单位，内存则是以页为单位。程序运行时，只有某几页的数据被装载到了内存。若CPU执行运算时，发现所需的数据不在内存页中，则会产生**缺页中断**，会由操作系统老大把缺失的页从磁盘加载到内存，CPU才能继续运算。当产生了**缺页中断**，而内存中又没有多余的空间来存放即将被加载进来的页时，就需要从内存中移出一页，腾出空间。这时就需要一种策略，来决定哪一页应该被移出。

## LRU置换算法 ##

LRU（Least Recently Used），是操作系统常用的一种页面置换的算法，也经常被用来作为一种缓存淘汰策略。

它基于局部性原理，认为最近被访问过的页，会在不久的将来被再次访问。所以它会选择**最近最少使用**的那一页，将其淘汰出去。比如内存一共可以装下5个页，并且在最近一段时间，每个页被访问的次数如下，则当发生缺页中断，则会选择c，将其移出

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZjajEwMDk3ODQ4MTQ_size_16_color_FFFFFF_t_70]

LRU也经常被当作一道面试题，所以今天我花了一点时间写了LRU的缓存实现。这也是LeetCode上的第146道题目

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZjajEwMDk3ODQ4MTQ_size_16_color_FFFFFF_t_70 1]

思路：

使用了HashMap加双向链表的结构，这样能保证获取元素时，时间复杂度是O(1)，需要移除旧元素时，时间复杂度也是O(1)。

链表可以用来表示数据的"新旧"程度。刚刚被添加进来，或者刚刚被获取过的数据，认为是最新的。当一个新的元素被添加时，我们采用尾插法，把它接到链表尾部，这样，链表头就是最早进来的，也就是最旧的，链表尾则是最新的。当一个元素被访问时，调整这个元素在链表中的位置，将它放到链表尾部，表示这个元素刚刚被访问过，很新鲜。这样，当缓存满了，需要移除元素时，链表头就是最近最少使用的元素，直接移除链表头即可。

代码如下：

import java.util.HashMap;
    import java.util.Map;
    
    public class LRUCache { 
        /** 链表节点 **/
    	static class  Node{ 
    		int key;
    		int value;
    		Node prev;
    		Node next;
    		public Node(int key,int value){ 
    			this.key = key;
    			this.value = value;
    		}
    	}
    
    	private Map<Integer,Node> map;
    
    	private Node head;
    
    	private Node tail;
    
    	private int capacity;
    
    	public LRUCache(int capacity){ 
    		if (capacity <= 0){ 
    			throw new IllegalArgumentException("capacity should be positive");
    		}
    		this.capacity = capacity;
    		map = new HashMap<>(capacity);
    	}
    
    	public int get(int key){ 
    		Node node = map.get(key);
    		refreshNode(node);
    		return node == null ? -1 : node.value;
    	}
    
    	public void put(int key,int value){ 
    		Node node = map.get(key);
    		if (node == null){ 
                /** 新元素，先判断容量是否足够 **/
    			removeNodeIfOverCapacity();
    			node = new Node(key,value);
    			map.put(key,node);
    			appendNode(node);
    		}else { 
                /** 存在该元素时，直接替换 **/
    			node.value = value;
    			refreshNode(node);
    		}
    	}
    
    	private void removeNodeIfOverCapacity(){ 
    		if (map.size() == capacity){ 
    			map.remove(head.key);
    			head = head.next;
    			if (head == null){ 
    				tail = null;
    			}else { 
    				head.prev = null;
    			}
    		}
    	}
    
    	private void appendNode(Node node){ 
    		if (node == null)
    			return ;
    		if (head == null){ 
    			head = tail = node;
    		}else{ 
    			tail.next = node;
    			node.prev = tail;
    			node.next = null;
    			tail = node;
    		}
    	}
    
    	private void refreshNode(Node node){ 
    		if (node == null)
    			return;
    		if (node == head){ 
                /** 当node=head=tail时，不做任何操作 **/
    			if (node != tail){ 
    				Node newHead = head.next;
    				head = newHead;
    				head.prev = null;
    				tail.next = node;
    				node.prev = tail;
    				node.next = null;
    				tail = node;
    			}
    		}/** node=tail时，也无需做任何操作 **/
            else if (node != tail){ 
    			Node prev = node.prev;
    			Node next = node.next;
    			prev.next = next;
    			next.prev = prev;
    			tail.next = node;
    			node.prev = tail;
    			node.next = null;
    			tail = node;
    		}
    	}
    }

对于我这样一个算法战5渣的四川吃货来说，LeetCode的测试结果让我比吃了红烧排骨水煮牛肉毛血旺串串香肯德基超级外带全家桶还要尼玛的宇宙无敌爆炸螺旋爽，必须晒一波图臭屁一下。下一个吊打面试官的人就是我了哈哈哈（逃）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZjajEwMDk3ODQ4MTQ_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZjajEwMDk3ODQ4MTQ_size_16_color_FFFFFF_t_70]: /images/20230521/8979fb58119a49b9ab10492b29ec9c77.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZjajEwMDk3ODQ4MTQ_size_16_color_FFFFFF_t_70 1]: /images/20230521/60e3f5cbe14e4992964c21c1fe39d43d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZjajEwMDk3ODQ4MTQ_size_16_color_FFFFFF_t_70 2]: /images/20230521/b84662777f944f57b3be756eebec7f51.png