LinkedHashMap的使用和内部实现
深入学习Java基础知识
LinkedHashMap是HashMap的子类，它继承了HashMap大多数的优点，它和HashMap最大的不同点是，HashMap是无序的，而LinkedHashMap是有序的。
一、成员变量accessOrder
accessOrder是LinkedHashMap一个影响排序规则的变量，可以在构造参数中指定，默认是false。
- 当accessOrder是false时，表示插入顺序模式，LinkedHashMap内部保持元素插入的顺序，注：这种模式重复插入相同的key，不更新key的顺序。
- 当accessOrder是false时，表示访问顺序模式，LinkedHashMap内部保持元素访问的顺序，即最近访问的排后面，get，put，replace等操作都算访问，注：这种模式重复插入相同的key，会更新key的顺序。
二、removeEldestEntry方法
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}该方法用于控制在插入新节点后是否删除最年长的节点，在插入顺序的模式下就是最先插入的节点，在访问顺序的模式下就是最早访问的节点，默认是不删除。因为访问顺序模式的特性，再结合removeEldestEntry方法，LinkedHashMap经常会被用来实现LRU（Least recently used，最近最少使用）缓存。
1import java.util.LinkedHashMap;
2import java.util.Map;
3
4class LRUCache extends LinkedHashMap<String, String> {
5
6 private int capacity;
7
8 public LRUCache(int capacity) {
9 super(capacity, 0.75F, true);
10 this.capacity = capacity;
11 }
12
13 @Override
14 protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
15 return size() > capacity;
16 }
17}
18
19public class Main {
20
21 public static void main(String[] args) {
22 LRUCache cache = new LRUCache(3);
23 cache.put("1", "1");
24 cache.put("2", "2");
25 cache.put("3", "3");
26 cache.put("4", "4");
27 cache.forEach((key, value) -> {
28 System.out.println(key + ", " + value);
29 });
30 }
31}三、LinkedHashMap内部有序的实现
LinkedHashMap对内部的节点进行了扩展，在每个节点内部添加了前驱和后驱节点的引用，在对Map进行put、get和remove操作时会同时更新操作节点的前驱和后驱节点，同时保存了全局的一个头部节点和尾部节点，这样在遍历的时候就能拿到链表头部节点然后按顺序遍历整个链表。
1//链表头部节点
2transient LinkedHashMap.Entry<K,V> head;
3//链表尾部节点
4transient LinkedHashMap.Entry<K,V> tail;
5//内部节点
6static class Entry<K,V> extends HashMap.Node<K,V> {
7 Entry<K,V> before, after;
8 Entry(int hash, K key, V value, Node<K,V> next) {
9 super(hash, key, value, next);
10 }
11}在HashMap中，专门为LinkedHashMap定义了三个方法，用于在插入、删除，访问节点后进行后续操作。
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }下面看看在HashMap插入键值对时，LinkedHashMap执行了哪些操作来维护链表顺序，首先重写了newNode方法，在插入节点时，将当前节点添加在链表尾部。
1Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
2 LinkedHashMap.Entry<K,V> p =
3 new LinkedHashMap.Entry<>(hash, key, value, e);
4 linkNodeLast(p);
5 return p;
6}
7//将节点添加到链表尾部
8private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
9 LinkedHashMap.Entry<K,V> last = tail;
10 tail = p;
11 if (last == null)
12 head = p;
13 else {
14 p.before = last;
15 last.after = p;
16 }
17}在HashMap的putVal方法中会调用newNode方法来生成新的节点，实际调用的是上面提到的LinkedHashMap中重写的newNode方法。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
...
//生成新节点，添加到哈希表
newNode(hash, key, value, null)
...
afterNodeInsertion(evict);
return null;
}在HashMap的putVal方法的末尾会调用afterNodeInsertion，这个方法是在LinkedHashMap中实现的。
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}这个方法主要是用来调用removeEldestEntry，根据结果来确定是否要删除最年长的节点，这样就完成插入操作，并且维护了LinkedHashMap内部的顺序。