手写LRU算法两种方式
LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。
本质就是哈希表+双向链表来完成的，并且时间复杂度是O(1)也就是最快的方式.
下面两种方式我参考学习来，在此做个记录直接上代码
第一种：
// 第一种方式
package com.gm.wj.demo;
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUDemoLinkedHashMap<K,V> extends LinkedHashMap<K,V> {
/**
* 手写LRU算法·借助linkedHashMap实现
*
*/
/**
* 负载因子
*/
static private float load_factor = 0.75f;
/**
* 缓存容量
*/
private int initialCapacity;
/**
* 调用父类的构造方法
* @param initialCapacity
*
* 使用指定的初始容量、负载因子和排序模式构造一个空的LinkedHashMap实例。
*
* 当accessOrder：true时，排序按照访问(put和get都是访问)顺序进行排序。
* （也就是插入和访问都会将当前节点放置到尾部，尾部代表的是最近访问的数据，这和JDK1.6是反过来的，jdk1.6头部是最近访问的）
* 如果根据lru删除策略来进行处理近期访问次数较少的数据，则会首先删除头部的数据。
*
*
* 当accessOrder：false时，排序按照插入顺序(put)进行排序。
* (完全按照插入顺序为主，就算get数据，也不会改变数据在链表中的位置)
* 如果根据lru删除策略来进行处理数据，则会首先删除头部的数据，且是先进先出。
*
*/
public LRUDemoLinkedHashMap(int initialCapacity){
super(initialCapacity,load_factor,false);
this.initialCapacity=initialCapacity;
}
/**
* 调用父类的删除方法
* @param eldest
* @return
* *如果此映射应删除其最早的条目，则返回true。
* *此方法由put和putAll、after调用
*
* *在map中插入一个新条目。它提供了实现者每次有机会删除最老的条目时，都会删除一个新条目
* 增加了。如果映射表示缓存，这将非常有用：它允许通过删除过时条目来减少内存消耗的映射。
* *<p>示例使用：此覆盖将允许map增长到100条目，然后在每次创建新条目时删除最旧的条目
添加，保持100个条目的稳定状态。<p>
*
* *私有静态最终int MAX_条目=100；
* *受保护的布尔重构（Map.Entry最早）{
*
* *返回大小（）> 最大输入；
*
* * }
*<p>此方法通常不会以任何方式修改map，而是允许map按照其返回值。允许对该方法进行修改
* 直接映射，但如果它这样做，它必须返回false（表示映射不应尝试任何进一步修改）。
* 返回true从该方法中修改映射后，未指定。
* *<p>此实现仅返回false（因此map的行为类似于普通map-最老的元素永远不会被删除）。
* *@param最早是最近在map中插入的条目，或者如果这是一个按访问顺序排列的映射，是最近访问最少的映射进入。这是将于本周删除的条目
方法返回true。如果之前map是空的到put或putAll调用在这个调用中，这将是插入；换句话说，如果map包含一个最老的条目也是最新的条目。
*
* *@returntrue如果应该删除最老的条目从map上看false如果应该保留。
*
* */
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return super.size() > 4;
}
public static void main(String[] args) {
LRUDemoLinkedHashMap kvlruDemo = new LRUDemoLinkedHashMap(4);
kvlruDemo.put("1", 1);
kvlruDemo.put("2", 1);
kvlruDemo.put("3", 1);
kvlruDemo.put("4", 1);
kvlruDemo.put("7", 1);
kvlruDemo.put("8", 1);
kvlruDemo.get("4");
kvlruDemo.get("4");
kvlruDemo.put("x",1);
/* kvlruDemo.get("7");
kvlruDemo.get("7");*/
/*kvlruDemo.get("2");
kvlruDemo.get("3");*/
/*kvlruDemo.get("2");
kvlruDemo.get("2");
kvlruDemo.put("6", 1);*/
/*kvlruDemo.put("7", 1);*/
System.out.println(kvlruDemo.keySet());
}
/**true
* [7, 8, 3, x]
*
*
*/
/**
* false
*
* [4, 7, 8, x]
*/
}
第二种：
package com.gm.wj.demo;
import java.util.HashMap;
import java.util.Map;
public class HandwrittenLRUDemo {
/**
* 手写LRU算法,此方式是按照元素的插入顺序（accessOrder：false）复现LRU算法
*
* accessOrder：false时，排序按照插入顺序(put)进行排序。
* * (完全按照插入顺序为主，就算get数据，也不会改变数据在链表中的位置)
* * 如果根据lru删除策略来进行处理数据，则会首先删除头部的数据，且是先进先出。
*
* */
/**
* 1.仿照linkedHashMap或者AbstractQueuedSynchronizer定义一个存放数据的载体Node<K,V>
*/
class Node<K,V>{
K key;
V value;
/**
* 前指针
*/
Node<K,V> prev;
/**
* 后指针
*/
Node<K,V> next;
/**
* 无参构造方法
*/
public Node(){
this.prev =this.next = null;
}
/**
* 有参构造方法，初始化Node
* @param key
* @param value
*/
public Node(K key,V value){
this.key = key;
this.value = value;
this.prev =this.next = null;
}
}
/**
* 2.构建一个双向链表用于存放Node节点,也可以理解为创建了一个队列
*/
class bidirectionalLinkedList<K,V>{
/**
* 头指针
*/
Node<K,V> head;
/**
* 尾指针
*/
Node<K,V> tail;
/**
* 无参构造方法
*
* <pre> prev
* * +------+ <===== +-----+ +-----+
* * head | | | | | | tail
* * +------+ =====> +-----+ +-----+
* * </pre> next
*
* 如图此时初始化成为一个虚拟的双向队列，并且head头节点的next指针指向tail尾节点,
* tail尾节点的prev前指针指向head头节点，由此形成闭环。
* (注：head 和 tail 可以理解为指针也可以理解成Node节点)
*/
public bidirectionalLinkedList(){
head = new Node<>();
tail = new Node<>();
head.next =tail;
tail.prev = head;
}
/**
* 新增一个Node进入队列,相当于是在head节点和tail节点中间插入一个新的node节点，以head节点参照物。
*
* 1.head头节点的next指针指向新进入的node节点
* 2.node节点的prev前指针指向head头节点
* 2.node节点的next后指针指向tail尾节点（此时的tail是head头节点的下一个节点，用head.next表示）
* 2.tail节点的prev前指针指向新进入的node节点（此时形成闭环）
*
* @param node
*/
public void addHead(Node<K,V> node){
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
/**
* 删除一个节点，就以node参照物.
* 在这个虚拟队列中删除node,就是把node节点的前后指针的指向不再指向其他节点。
* 在将node的前后两个节点连接起来，这样就是将node删除掉了，被删除的node节点将会被jvm回收清理
*
* @param node
*/
public void removeNode(Node<K,V> node){
node.next.prev = node.prev;
node.prev.next = node.next;
node.prev = null;
node.next = null;
}
public Node<K,V> getLast(){
return tail.prev;
}
}
/**
* 缓存容量
*/
private int initialCapacity;
Map<Object,Node<Object,Object>> map;
bidirectionalLinkedList<Object,Object> bidirectionalLinkedList;
/**
* 构造方法
* @param initialCapacity
*/
public HandwrittenLRUDemo(int initialCapacity){
this.initialCapacity = initialCapacity;
map = new HashMap<>();
bidirectionalLinkedList = new bidirectionalLinkedList<>();
}
//查询方法
public Object get(Object key){
//如果不存在返回-1
if (!map.containsKey(key)){
return -1;
}else {
/**
* 如果存在，通过key查找出map中存放的node节点，
* 更新node节点的位置，从队列中删除该节点并添加到队列的尾部
*/
Node<Object, Object> node = map.get(key);
bidirectionalLinkedList.removeNode(node);
bidirectionalLinkedList.addHead(node);
return node.value;
}
}
/**
* 新增or更新，
* @param key
* @param value
*/
public void put(Object key,Object value){
/**
* map中存在这个key,则更新数据并更新在队列中的位置
*/
if (map.containsKey(key)){
Node<Object, Object> node = map.get(key);
node.value = value;
map.put(key,node);
bidirectionalLinkedList.removeNode(node);
bidirectionalLinkedList.addHead(node);
}else {
/**
* 当达到了缓存容量时，将从队列中找到tail尾节点的前一个节点，
* 同时从队列中和map中删除
*/
if (map.size() == initialCapacity){
Node<Object, Object> lastNode = bidirectionalLinkedList.getLast();
bidirectionalLinkedList.removeNode(lastNode);
map.remove(lastNode.key);
}
}
/**
* 新增：
*/
Node<Object, Object> newNode = new Node<>(key,value);
map.put(key,newNode);
bidirectionalLinkedList.addHead(newNode);
}
public static void main(String[] args) {
HandwrittenLRUDemo kvlruDemo = new HandwrittenLRUDemo(4);
kvlruDemo.put("1", 1);
kvlruDemo.put("2", 1);
kvlruDemo.put("3", 1);
kvlruDemo.put("4", 1);
kvlruDemo.put("7", 1);
kvlruDemo.put("8", 1);
kvlruDemo.get("4");
kvlruDemo.get("4");
kvlruDemo.put("x",1);
/* kvlruDemo.get("7");
kvlruDemo.get("7");*/
/*kvlruDemo.get("2");
kvlruDemo.get("3");*/
/*kvlruDemo.get("2");
kvlruDemo.get("2");
kvlruDemo.put("6", 1);*/
/*kvlruDemo.put("7", 1);*/
System.out.println(kvlruDemo.map.keySet());
}
}