星空.jpg
近期简单的看了些算法，印象深刻的lru算法，网上很多，贴了一个运行结果却不尽人意，以下自己单独写了一个，以便后期回顾
package LRU;
import com.alibaba.fastjson.JSON;
import com.alibaba.fastjson.JSONObject;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
public class LRUCache<V> {
/**
* 容量
*/
private int capacity = 1024;
/**
* Node记录表
*/
private Map<String, ListNode<String, V>> table = new ConcurrentHashMap<>();
/**
* 双向链表头部
*/
private ListNode<String, V> head;
/**
* 双向链表尾部
*/
private ListNode<String, V> tail;
/**
* 排序结果
*/
private List orderList;
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 void order(){
List orderList = new ArrayList();
ListNode<String, V> tag = new ListNode<String, V>();
orderList.add(JSON.toJSONString(head.value));
tag = head;
while (null != tag.next.key){
tag = tag.next;
orderList.add(JSON.toJSONString(tag.value));
}
this.orderList = orderList;
}
public V get(String key) {
ListNode<String, V> node = table.get(key);
//重新连线[处理尾部]
//尾部节点的前节点的前节点的下个节点指向尾部
System.out.println("tail---->"+tail.key);
tail.prev.prev.next=tail;
//尾部节点指向前面节点的前节点
System.out.println("tail.prev.prev---->"+tail.prev.prev.key);
tail.prev=tail.prev.prev;
System.out.println("tail.prev.key---->"+tail.prev.key);
//重新连线[处理节点前后]
//当前节点的下个节点的前节点指向当前节点的前节点
node.next.prev=node.prev;
//当前节点的前节点的下个节点指向当前节点的下个节点
node.prev.next=node.next;
//-------删除当前节点
table.remove(key);
//-------插入到头部
//处理node尾部连线
//头节点的下个节点的前节点插入node
head.next.prev=node;
//node的下个节点为当前头节点的下个节点
node.next=head.next;
//处理node头部连线
//头节点的下个节点改为当前节点
head.next=node;
//当前节点的头节点设为头节点
node.prev=head;
table.put(key,node);
return (V) node;
}
//插入前判断是否有大于缓存,如果大于则将尾部删除，头部插入新的节点
//每次都从头插入
//如果插入的值已存在则删除链表里面的节点，并将节点移动到头部
public void put(String key, V value) {
ListNode<String, V> nodeOld = table.get(key);
if (nodeOld==null){
ListNode<String, V> node = (ListNode<String, V>) value;
if (table.size()>=capacity){
//-------删除尾部
table.remove(tail.prev.key);
//重新连线
//尾部节点的前节点的前节点的下个节点指向尾部
System.out.println("tail---->"+tail.key);
tail.prev.prev.next=tail;
System.out.println("tail.prev.key---->"+tail.prev.key);
//尾部节点指向前面节点的前节点
System.out.println("tail.prev.prev---->"+tail.prev.prev.key);
tail.prev=tail.prev.prev;
//-------插入到头部
//处理node尾部连线
//头节点的下个节点的前节点插入node
System.out.println("head.next.prev.key---->"+head.next.prev.key);
head.next.prev=node;
//node的下个节点为当前头节点的下个节点
node.next=head.next;
//处理node头部连线
//头节点的下个节点改为当前节点
System.out.println("head.next.key---->"+head.next.key);
head.next=node;
//当前节点的头节点设为头节点
node.prev=head;
table.put(key,node);
}else {
//-------插入到头部
//处理node尾部连线
//头节点的下个节点的前节点插入node
head.next.prev=node;
//node的下个节点为当前头节点的下个节点
node.next=head.next;
//如果tail的前节点是head证明是刚初始化，需要将node链接到tail
if (tail.prev == head){
tail.prev = node;
}
//处理node头部连线
//头节点的下个节点改为当前节点
head.next=node;
//当前节点的头节点设为头节点
node.prev=head;
table.put(key,node);
}
}else {
//重新连线
//当前节点的下个节点的前节点指向当前节点的前节点
nodeOld.next.prev=nodeOld.prev;
//当前节点的前节点的下个节点指向当前节点的下个节点
nodeOld.prev.next=nodeOld.next;
//-------删除当前节点
table.remove(key);
//-------插入到头部
//处理node尾部连线
//头节点的下个节点的前节点插入node
head.next.prev=nodeOld;
//node的下个节点为当前头节点的下个节点
nodeOld.next=head.next;
//处理node头部连线
//头节点的下个节点改为当前节点
head.next=nodeOld;
//当前节点的头节点设为头节点
nodeOld.prev=head;
table.put(key,nodeOld);
}
}
/**
* 双向链表内部类
*/
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.put("key5", node5);
//map没有顺序，不好看结果
cache.order();
System.out.println("head1-----------"+cache.head.next.key);
System.out.println("tail1-----------"+cache.tail.prev.key);
System.out.println("tail-----------"+ JSON.toJSONString(cache.orderList));
cache.get("key2");
cache.order();
System.out.println("head1-----------"+cache.head.next.key);
System.out.println("tail1-----------"+cache.tail.prev.key);
System.out.println("tail-----------"+ JSON.toJSONString(cache.orderList));
}
}
