实现⼀个线程安全并且可以设置过期时间的
LRU（LinkedHashMap原理）
⽬录
FIFO的思想是实现⼀个先进先出的队列，LRU最近最久未使⽤。可以⽤双向链表linkedList来实现，同时为了兼顾查询节点时的效率，结合HashMap来实现。双向链表linkedList+HashMap的数据结构可以联想到LinkedHashMap，就不需要我们⾃⼰来实现了。LinkedHashMap存储数据是有序的，可以分为插⼊顺序（accessOrder = fal）和访问顺序（accessOrder = true），默认为插⼊顺序，⽽且LinkedHashMap提供了删除最后⼀个节点的⽅法removeEldestEntry(Map.Entry eldest)，正好可以⽤来实现热干面
FIFO（LinkedHashMap按插⼊顺序存储数据）和LRU算法（LinkedHashMap按访问顺序存储数据）。
1、HashMap原理
底层是Entry数组+链表（Entry节点的next指针）+红⿊树。JDK8中，链表长度不⼩于8时，将链表转化为红⿊树。默认⽆参构造函数会初始化⼤⼩为16，向集合中添加元素⾄集合⼤⼩的0.75倍时，会⽣成⼀个⼤⼩为原来2倍的新集合，然后重新计算元素的地址，将集合中元素插⼊到新集合，届时效率很低。线
程不安全。（例如：put的时候导致的数据覆盖、集合扩展时(resize⽅法)会出现死循环）。
//HashMap的Entry结构：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
｝
2、LinkedHashMap实现LRU原理（accessOrder = true）
2.1 数据结构
HashMap的原理是内部维护了⼀个Entry数组，⽽LinkedHashMap在HashMap的基础上，增加了链表2006高考
头节点和尾节点两个指针，增加了排序⽅式的标志，Entry节点增加了前后两个指针。因此LinkedHashMap的Entry节点有三个指针，⼀个是双向链表的前指针、⼀个是双向链表的后指针、⼀个是HashMap的hash地址重复时拉链法解决冲突的next的指针。
/*LinkedHashMap的Entry结构：*/
//双向链表头结点
transient LinkedHashMap.Entry<K,V> head;
//双向链表尾节点
transient LinkedHashMap.Entry<K,V> tail;
//是否基于访问顺序排序（默认为fal即插⼊顺序排序）
final boolean accessOrder;
//Entry继承了HashMap的Entry，⼜增加了before, after两个指针
private static class Entry<K,V> extends HashMap.Entry<K,V> {
莺声燕语
Entry<K,V> before, after;
Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
super(hash, key, value, next);
}
｝
2.2 put⽅法
如果put的是新key，则将Entry节点添加到Map中，并添加到双向链表的尾部，若initialCapacity数量已满，删除最近最久未使⽤的Entry 节点即双向链表的头结点；若put的是已有的key，更新节点的value，并将节点删除并添加到尾部。
HashMap的put⽅法会⽣成⼀个节点，调⽤了newNode⽅法，⽽LinkedHashMap重写了此⽅法
/**
* 创建⼀个节点
* 创建⼀个节点
* @param hash hash值
* @param key 键
* @param value 值
* @param e 下⼀个节点，这个是HashMap节点的属性
* @return
*/
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
//调⽤构造⽅法
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
/
/维护链表
linkNodeLast(p);
return p;
}
/**
* 添加⼀个节点到末尾
* @param p 节点
*/
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
//保存尾部节点
LinkedHashMap.Entry<K,V> last = tail;
/
/更新尾部节点
tail = p;
//判断之前的尾部节点是否为空
if (last == null)
//之前的尾部节点为空，说明还没有数据，设置⼀下头节点
head = p;
el {
//说明之前已经有数据了，将新的节点作为尾部节点连接起来
p.before = last;
last.after = p;
}
}
HashMap当put⼀个已经存在的key时，会触发是否更新的操作，之后会调⽤afterNodeAccess⽅法，LinkedHashMap重写了此⽅法/**
* accessOrder为true时，将操作的节点移到链表尾部
* @param e 节点
*/
void afterNodeAccess(Node<K,V> e) {
公关部LinkedHashMap.Entry<K,V> last;
//accessOrder 这个参数是指在进⾏操作的时候，是否将操作的节点移动到链表的最后，默认fal
//也就是说accessOrder为fal的时候链表就是按照插⼊顺序维护的
//true的时候，会将最近使⽤的节点移动到链表最后
if (accessOrder && (last = tail) != e) {
//保存当前节点和其前置节点和后置节点
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//清空后置节点，因为当前节点要被移动到最后了
p.after = null;
//判断前置节点是否为空节点
if (b == null)
//前置节点为空，说明当前节点是头节点，将它的后置节点也就是第⼆个节点设置为头节点
head = a;
el
//存在前置节点，将前置节点的后置节点连接到当前节点的下⼀个节点
b.after = a;
//判断后置节点是否为空
if (a != null)
//后置节点不为空，更新后置节点的前置节点
a.before = b;
el
//说明该节点就是尾部节点，设置前置节点为后节点
//a == null 说明p就是尾部节点？有点不清楚
//a == null 说明p就是尾部节点？有点不清楚
last = b;
//统⼀更新尾部节点
玉质金相if (last == null)
//说明只有这么⼀个节点
head = p;
el {
//将当前节点挂到链表末尾
p.before = last;
last.after = p;
}
//设置尾部节点
tail = p;
++modCount;烟花碎
}
}
LinkedHashMap也重写了afterNodeInrtion⽅法
void afterNodeInrtion(boolean evict) {
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, fal, true);
}
}
需要注意：
removeEldestEntry⽅法是是否删除链表的头结点，默认为不删除，实现LRU需要覆盖此⽅法protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return fal;
}
2.3 get⽅法
移动当前操作的节点到链表最后
public V get(Object key) {
// 调⽤genEntry得到Entry
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
// 如果LinkedHashMap是访问顺序的，则get时，也需要重新排序
return e.value;
}
2.4 remove⽅法
从Map和链表中删除
LinkedHashMap调⽤了HashMap的remove⽅法，重写了afterNodeRemoval⽅法
LinkedHashMap调⽤了HashMap的remove⽅法
重写了afterNodeRemoval⽅法
/**
* 删除链表中的节点
* @param e
*/
void afterNodeRemoval(Node<K,V> e) {
//获取当前节点的前置后置节点
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
证明怎么写//清空前置后置节点
p.before = p.after = null;
if (b == null)
//前置节点为空，说明为头节点，更新头节点为后置节点彼得德鲁克
head = a;
el
/
/前置节点不为空，设置前置节点的后置节点为删除节点的后置节点
b.after = a;
if (a == null)
//后置节点为空，说明为尾部节点，更新尾部节点为其前置节点
tail = b;
el
//后置节点不为空，更新后置节点的前置节点
a.before = b;
}
3、普通LRU代码实现
1、removeEldestEntry⽅法（是否删除元素）默认返回fal，需要重写
2、通过LinkedHashMap构造函数中的参数accessOrder来指定数据存储的顺序（fal为插⼊顺序，true为访问顺序）
//LinkedHashMap构造函数
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
//LRU算法（FIFO算法只需要将LinkedHashMap的第三个参数true改为fal）
public class LRUCache {
private int capacity;
private LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<Integer, Integer>(capacity,0.75f,true) {
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
};
public LRUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
Integer res = (key);
return res;
}
public void put(int key, int value) {
cache.put(key, value);
}
}
4、实现⼀个线程安全并且可以设置过期时间的LRU缓存
4.1 解决安全问题
线程不安全主要是因为HashMap和LinkedHashMap都是线程不安全的，⽽且同时修改map和双向链表之间也会产⽣并发问题，所以仅仅使⽤线程安全的ConcurrentHashMap、ConcurrentLinkedQueue并不能解决问题，还要解决map和链表间的同步问题，最简单的⽅法就是在put或get时直接使⽤ReenTrantLock进⾏同步，如le.gson包提供的LruCache类，直接在⽅法上使⽤synchronized进⾏同步：
