众所周知，HashMap 提供的访问，是无序的。而在一些业务场景下，我们希望能够提供有序访问的 HashMap 。那么此时，我们就有两种选择：
- TreeMap ：按照 key 的顺序。
- LinkedHashMap ：按照 key 的插入和访问的顺序。
LinkedHashMap在HashMap 的基础之上，提供了顺序访问的特性。而这里的顺序，包括两种：
- 按照 key-value 的插入顺序进行访问
- 按照 key-value 的访问顺序进行访问。通过这个特性，我们实现基于 LRU 算法的缓存。
类图
成员变量
// 链表头，越老的节点，放在越前面。
transient LinkedHashMap.Entry<K,V> head;
// 链表尾，越新的节点，放在越后面。
transient LinkedHashMap.Entry<K,V> tail;
// 继承 Node，为数组的每个元素增加了 before 和 after 属性
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
// 控制两种访问模式的字段，默认 false
// true 按照访问顺序，会把经常访问的 key 放到队尾
// false 按照插入顺序提供访问
final boolean accessOrder; LinkedHashMap的数据结构很像是把 LinkedList 的每个元素换成了 HashMap 的 Node，像是两者的结合体，也正是因为增加了这些结构，从而能把 Map 的元素都串联起来，形成一个链表，而链表就可以保证顺序了，就可以维护元素插入进来的顺序。
构造方法
LinkedHashMap的构造方法都是调用HashMap完成的，唯一不同的就是accessOrder的设置。
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
public LinkedHashMap() {
super();
accessOrder = false;
}
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}创建节点
LinkedHashMap 初始化时，默认 accessOrder 为 false，就是会按照插入顺序提供访问，插入方法使用的是父类 HashMap的put方法，不过覆写了put方法执行中调用的 newNode/newTreeNode和afterNodeAccess方法。
newNode/newTreeNode方法，控制新增节点追加到链表的尾部，这样每次新节点都追加到尾部，即可保证插入顺序了，我们以 newNode 源码为例：
//新增节点，并追加到链表尾部
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;
}
// link at the end of list
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;//第一个节点，头尾都指向它
else {
//建立新增节点和上个尾节点之间的前后关系
p.before = last;
last.after = p;
}
}LinkedHashMap 通过新增头节点、尾节点，给每个节点增加 before、after 属性，每次新增时，都把节点追加到尾节点等手段，在新增的时候，就已经维护了按照插入顺序的链表结构了。
按照访问顺序访问
默认是按照插入顺序进行访问的，所以需要设置accessOrder为true。
LinkedHashMap<Integer, Integer> map = new LinkedHashMap<Integer, Integer>(4,0.75f,true) ;
map.put(10, 10);
map.put(9, 9);
map.put(20, 20);
map.put(1, 1);
System.out.println(map);
System.out.println(map.get(9));
System.out.println(map);
System.out.println(map.get(20));
System.out.println(map);
/**
* 访问过的节点被移动到尾部了
* {10=10, 9=9, 20=20, 1=1}
* 9
* {10=10, 20=20, 1=1, 9=9}
* 20
* {10=10, 1=1, 9=9, 20=20}
*/节点操作回调
在 HashMap 的读取、添加、删除时，分别提供了 afterNodeAccess(Node<K,V> e)、afterNodeInsertion(boolean evict)、afterNodeRemoval(Node<K,V> e) 回调方法。这样，LinkedHashMap 可以通过它们实现自定义拓展逻辑。
afterNodeAccess
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);//对访问节点后的回调
return e.value;
}
// 移动节点到链表尾部
void afterNodeAccess(Node<K,V> e) {
LinkedHashMap.Entry<K,V> last;
//accessOrder为true，并且访问的节点也不是表尾节点
if (accessOrder && (last = tail) != e) {
//记录下访问节点的前继节点b和后继节点a
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;//访问节点为头节点，移走后a为头节点
else
b.after = a;//将a设为b的后继
if (a != null)
a.before = b;//a不为null,将b设为它的前继
else
last = b;
if (last == null)
head = p;
else {
p.before = last;//访问节点移动到尾部
last.after = p;
}
tail = p;//访问节点设为尾节点
++modCount;
}
}不仅仅是 get 方法，执行 getOrDefault、compute、computeIfAbsent、computeIfPresent、merge 方法时，也会这么做，通过不断的把经常访问的节点移动到队尾，那么靠近队头的节点，自然就是很少被访问的元素了。
afterNodeInsertion
在开始看afterNodeInsertion(boolean evict)方法之前，我们先来看看如何基于 LinkedHashMap 实现 LRU 算法的缓存。
class LRUCache<K, V> extends LinkedHashMap<K, V> {
//缓存大小
private final int CACHE_SIZE;
/**
* 传递进来最多能缓存多少数据
*
* @param cacheSize 缓存大小
*/
public LRUCache(int cacheSize) {
// true 表示让 LinkedHashMap 按照访问顺序来进行排序，最近访问的放在头部，最老访问的放在尾部。
super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);
CACHE_SIZE = cacheSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
// 当 map 中的数据量大于指定的缓存个数的时候，就自动删除最老的数据。
return size() > CACHE_SIZE;
}
}//LRUCache代码演示：
LRUCache<Integer,Integer> cache = new LRUCache<>(3);
cache.put(1,1);
cache.put(2,2);
cache.put(3,3);
System.out.println(cache);
cache.get(1);
System.out.println(cache);
cache.put(4,4);
System.out.println(cache);
/**
* {1=1, 2=2, 3=3}
* {2=2, 3=3, 1=1}
* {3=3, 1=1, 4=4}//删除了最老的节点2
*/ 重写removeEldestEntry方法就可以了，为什么呢！现在我们看看具体的afterNodeInsertion方法吧！
// evict表示是否允许移除元素
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
// first = head 记录当前头节点。因为移除从头开始，最老
//使用removeEldestEntry(first) 判断是否满足移除最老节点
if (evict && (first = head) != null && removeEldestEntry(first)) {
//移除指定节点
K key = first.key;
//调用HashMapd的removeNode方法
removeNode(hash(key), key, null, false, true);
}
}
//默认实现一直返回false，说明不进行删除
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}afterNodeRemoval
在节点被移除时，LinkedHashMap 需要将节点也从链表中移除，所以重写afterNodeRemoval(Node<K,V> e)方法，实现该逻辑。
void afterNodeRemoval(Node<K,V> e) { // unlink
// 将 e 赋值给 p 【因为要 Node 类型转换成 Entry 类型】
// 同时 b、a 分别是 e 的前后节点
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// 将 p 从链表中移除
p.before = p.after = null;
// 处理 b 的下一个节点指向 a
if (b == null)
head = a;
else
b.after = a;
// 处理 a 的前一个节点指向 b
if (a == null)
tail = b;
else
a.before = b;
}LeetCode146:实现LRU
class LRUCache {
private Map<Integer, Integer> map;
private LinkedList<Integer> list;
private int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>();
list = new LinkedList<>();
}
public int get(int key) {
if(map.containsKey(key)) {
list.remove((Integer) key);
list.addLast(key);
return map.get(key);
}
return -1;
}
public void put(int key, int value) {
if(map.containsKey(key)) {
list.remove((Integer) key);
list.addLast(key);
map.put(key, value);
return;
}
if(capacity == list.size()) {
// 如果容量等于数组容量，则删除头部信息
map.remove(list.getFirst());
list.removeFirst();
list.addLast(key);
map.put(key, value);
} else {
list.addLast(key);
map.put(key, value);
}
}
}版权属于：带翅膀的猫
本文链接：https://www.chengpengper.cn/archives/118/
转载时须注明出处及本声明
