什么是LRU算法? LRU是Least Recently Used的缩写，即最近最少使用，常用于页面置换算法，是为虚拟页式存储管理服务的。
关于操作系统的内存管理，如何节省利用容量不大的内存为最多的进程提供资源，一直是研究的重要方向。而内存的虚拟存储管理，是现在最通用，最成功的方式–
在内存有限的情况下，扩展一部分外存作为虚拟内存，真正的内存只存储当前运行时所用得到信息。这无疑极大地扩充了内存的功能，极大地提高了计算机的并发度。虚拟页式存储管理，则是将进程所需空间划分为多个页面，内存中只存放当前所需页面，其余页面放入外存的管理方式。然而，有利就有弊，虚拟页式存储管理增加了进程所需的内存空间，却也带来了运行时间变长这一缺点:进程运行过程中，不可避免地要把在外存中存放的一些信息和内存中已有的进行交换，由于外存的低速，这一步骤所花费的时间不可忽略。因而，采取尽量好的算法以减少读取外存的次数，也是相当有意义的事情
–from 360百科
LRU:Least Recently Used
使用代码实现，思路：
借助LinkedHashMap
import java.util.*;
class LRUCache {private int capacity;LinkedHashMap<Integer, Integer> maps = new LinkedHashMap<>();public LRUCache(int capacity) {this.capacity = capacity;}public int get(int key) {if(!maps.containsKey(key)){return -1;}makeRecent(key);return maps.get(key);}public void put(int key, int value) {if(maps.containsKey(key)){maps.remove(key);maps.put(key, value);return;}if(maps.size() >= capacity){removeLast();}maps.put(key, value);}public void makeRecent(int key){int v = maps.get(key);maps.remove(key);maps.put(key, v);}public void removeLast(){maps.remove(maps.keySet().iterator().next());}
}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/
扩展的，对于LFU， 根据使用频次，内存满时淘汰掉
Map<Integer, Node> cache; // 存储缓存的内容, 从这里返回getMap<Integer, LinkedHashSet<Node>> freqMap; // 存储每个频次对应的双向链表，int size;int capacity;int min; // 存储当前最小频次
)
