分布式页面替换(lrulru )是一种常见的页面替换算法，计算将所有文件操作放在内存中，但计算机的内存大小是固定的，因此无法将所有文件加载到内存中。 因此，必须制定策略来选择要添加到内存中的文件条目。
常见的页面替换算法如下：
LRU最近未使用的FIFO先进先出替换算法队列OPT优化替换算法(理想存在的) NRU Clock替换算法LFU最小使用替换算法PBA页面缓冲区算法LRU原理LRU的设计原理是数据最近频繁访问也就是说，经常访问的数据必须立即命中，但不经常访问的数据必须在容量超过限制时丢弃。
按以下顺序访问数据时，LRU的工作方式如下：
如上图所示，每次访问时，数据都放在堆栈的顶部。 如果要访问的数据不在内存中，并且堆栈中的数据已满，请选择删除堆栈底部的元素。 因为对堆栈底部数据的访问频率很低。 所以必须淘汰。
LRU的实现是如何设计LRU算法的呢？ 对于这种系列这样的结构，一般选择链表或数组来构建。
差异对比：
数组查询比较快，但对于添加/删除来说不是很好的链接列表选择查询。 但是，添加/删除有没有在o(1)小时的复杂性中加快检索的同时，迅速进行添加/删除操作的方法呢？
我们可以选择链表+hash表，哈希表搜索时间复杂度可以达到0(1)，这样就可以完美解决我们搜索时间慢的问题
1 .基于链表Hash表Hash表，在Java中HashMap是我们唯一的选择
链表、节点双向链表的实现。 Node中存储的是以下数学结构。
class NodeK，V{private K key； 私有v值； 私有节点，V prev； 私有节点，V next； 在HashMap中，通过key存储Node的key，value存储Node，建立了Map与Node的映射关系。 我们可以把HashMap看作搜索表，快速搜索我们必须定位的节点
下图展示这个结构：
代码实现大致思路：
要构建双向链表节点ListNode，必须包含基本属性key、value、prev和next
对于Cache对象，必须定义缓存的容量，因此必须在初始化时设置容量大小，实例化双向链表中的头、tail，并创建头.下一个- tail tail .预读
对于get操作，首先检查hashmap，如果存在，直接从当前位置删除Node，并将其插入链表的开头。 在链表中实现删除很有用，因为Node的前体节点直接指向后续节点。 如果不存在，则直接返回Null
put操作很麻烦。
Created with Raphal 2.2.0是否开始检测hash表的存在？ 插入链表的开头结束时是否超过了缓存容量？ 删除hash表key，删除链表末尾的node创建node，加入链表的开头，记录hash表yes no yes no package code.fragment； import java.util.Map； import Java.util.concurrent.concurrent hashmap； 公共类lrucachev {/* * *容量*/private int capacity=1024； /** * Node记录表*/private MapString，ListNodeString，V table=new ConcurrentHashMap (； /** *双向链表头部* /专用列表字符串，V head； /** *双向链表的末尾* /私有列表字符串，V tail；
public LRUCache(int capacity) { this(); this.capacity = capacity; } public LRUCache() { head = new ListNode<>(); tail = new ListNode<>(); head.next = tail; head.prev = null; tail.prev = head; tail.next = null; } public V get(String key) { ListNode<String, V> node = table.get(key); //如果Node不在表中，代表缓存中并没有 if (node == null) { return null; } //如果存在，则需要移动Node节点到表头 //截断链表，node.prev -> node -> node.next ====> node.prev -> node.next // node.prev <- node <- node.next ====> node.prev <- node.next node.prev.next = node.next; node.next.prev = node.prev; //移动节点到表头 node.next = head.next; head.next.prev = node; node.prev = head; head.next = node; //存在缓存表 table.put(key, node); return node.value; } public void put(String key, V value) { ListNode<String, V> node = table.get(key); //如果Node不在表中，代表缓存中并没有 if (node == null) { if (table.size() == capacity) { //超过容量了 ,首先移除尾部的节点 table.remove(tail.prev.key); tail.prev = tail.next; tail.next = null; tail = tail.prev; } node = new ListNode<>(); node.key = key; node.value = value; table.put(key, node); } //如果存在，则需要移动Node节点到表头 node.next = head.next; head.next.prev = node; node.prev = head; head.next = node; } /** * 双向链表内部类 */ public static class ListNode<K, V> { private K key; private V value; ListNode<K, V> prev; ListNode<K, V> next; public ListNode(K key, V value) { this.key = key; this.value = value; } public ListNode() { } } public static void main(String[] args) { LRUCache<ListNode> cache = new LRUCache<>(4); ListNode<String, Integer> node1 = new ListNode<>("key1", 1); ListNode<String, Integer> node2 = new ListNode<>("key2", 2); ListNode<String, Integer> node3 = new ListNode<>("key3", 3); ListNode<String, Integer> node4 = new ListNode<>("key4", 4); ListNode<String, Integer> node5 = new ListNode<>("key5", 5); cache.put("key1", node1); cache.put("key2", node2); cache.put("key3", node3); cache.put("key4", node4); cache.get("key2"); cache.put("key5", node5); cache.get("key2"); }}断点执行情况：