(一)LRUCache
1.LRU Cache概念
LRU是Least Recently Used的缩写，意思是最近最少使用，它是一种Cache替换算法。
Cache又名缓存，他的容量有限，因此当我们的容量用完后，一旦有新的内容要进行添加，就需要我们对旧的数据进行替换，来空余出新空间来存放新内容，LRU Cache就是将最近没有使用的数据替换掉
2.LRU Cache的实现思路
实现LRU Cache的方法和思路很多，但是我们要保证高效的get和put（时间复杂度O(1)）因为缓存的添加删除是很频繁的，这里我们使用哈希表搭配双向链表的思路，因为哈希表查找是很快的，双向链表的插入删除是很快的
（二）JDK中的实现
我们JDK中也有这样的一种数据结构LinkedHashMap
我们来简单看一下构造方法的参数参数，我们有四种构造方法，本质上还是调用了hahshmap的构造方法，所以我们这里看一下特殊的参数，也就是
这个参数我们看一下他说 如果true的话那就是基于访问顺序，如果是false就是基于插入顺序
那么我们看一下什么是插入顺序，什么是访问顺序
我们先来看一下插入顺序
我们发现他的打印顺序和我们插入顺序是一样的，即使我们中间get了111也没有影响数据大音顺序，那我们再来看基于访问数据
我们在插入111，222之后访问了111，之后插333，我们发现222是在111前面了，因为111在222插入后有过访问
当我们设置为true后
每一次访问数据后，都会吧数据放到当前双向链表的最后
（三）自我实现linkedHashMap
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;public class linkedHashMap {static class DlinkNode{public int key;@Overridepublic String toString() {return "DlinkNode{" +"key=" + key +", value=" + value +'}';}public int value;public DlinkNode prev;public DlinkNode next;public DlinkNode(int key, int value) {this.key = key;this.value = value;}public DlinkNode(){}}//头尾节点public DlinkNode head;public DlinkNode tail;public int usedSize; //有效数据个数（不可超过缓存容量）public int capacity; //缓存容量public Map<Integer,DlinkNode> cache;public linkedHashMap(int key,int value,int capacity){DlinkNode head=new DlinkNode();DlinkNode tail=new DlinkNode();head.next=tail;tail.prev=head;cache=new HashMap<>();this.capacity=capacity;}public void put(int key,int value){//查找当前key是否存在DlinkNode dlinkNode = cache.get(key);if(dlinkNode!=null){//如果存在就更新值并且放到双向链表中的最后dlinkNode.value=value;moveToTail(dlinkNode);}else {//如果不存在，就要进行插入//实例化一个节点DlinkNode dlinkNode1=new DlinkNode(key,value);//hashmap中存储cache.put(key,dlinkNode1);//放到双向链表尾部addToTail(dlinkNode1);//更新有效数据值usedSize++;if(usedSize>capacity){//头删DlinkNode dlinkNode2 = removeHead();//清除cacha中元素cache.remove(dlinkNode2.key);//有效值--usedSize--;}}}//打印双向链表public void pri(){DlinkNode cur=head.next;while(cur!=tail){System.out.println(cur);cur=cur.next;}}public int get(int key){DlinkNode dlinkNode = cache.get(key);//如果没有返回-1if(dlinkNode==null)return -1;//如果有就放到链表尾部moveToTail(dlinkNode);return dlinkNode.value;}//头删private DlinkNode removeHead() {DlinkNode tmp=head.next;removeNode(head.next);return tmp;}
//移动到尾部private void moveToTail(DlinkNode dlinkNode) {//删除这个节点removeNode(dlinkNode);//添加到双向链表尾部addToTail(dlinkNode);}
//添加链表到尾部private void addToTail(DlinkNode dlinkNode) {dlinkNode.next=tail;dlinkNode.prev=tail.prev;tail.prev.next=dlinkNode;tail.prev=dlinkNode;}
//删除节点private void removeNode(DlinkNode dlinkNode) {dlinkNode.prev.next=dlinkNode.next;dlinkNode.next.prev=dlinkNode.prev;}}
