LinkedHashMap
HashMap 的迭代顺序是按照 table 的索引进行的，并不是插入的顺序，因此有 LinkedHashMap；
继承自 HashMap 中，额外维护了一个 双向链表 来维护插入的顺序（如果 accessOrder 设置为true，维护的是访问顺序）
public class LinkedHashMap<K, V> extends HashMap<K, V> implements Map<K, V> {
transient Entry<K, V> head;
transient Entry<K, V> tail;
final boolean accessOrder; // 访问顺序
...
}双向链表节点：
static class Entry<K, V> extends HashMap.Node<K, V> {
Entry<K, V> before;
Entry<K, V> after;
Entry(int hash, K key, V value, HashMap.Node<K, V> next) {
super(hash, key, value, next);
}
}LinkedHashMap 重写了 HashMap 一系列创建节点的方法，使其返回的是 Entry；同时也在创建节点的时候插入到双向链表中；
// 插入新节点会调用
HashMap.Node<K, V> newNode(int hash, K key, V value, HashMap.Node<K, V> e) {
Entry<K, V> p = new Entry(hash, key, value, e);
this.linkNodeLast(p);
return p;
}
HashMap.TreeNode<K, V> newTreeNode(int hash, K key, V value, HashMap.Node<K, V> next) {
HashMap.TreeNode<K, V> p = new HashMap.TreeNode(hash, key, value, next);
this.linkNodeLast(p);
return p;
}
// 退化为链表时会使用
HashMap.Node<K, V> replacementNode(HashMap.Node<K, V> p, HashMap.Node<K, V> next) {
Entry<K, V> q = (Entry)p;
Entry<K, V> t = new Entry(q.hash, q.key, q.value, next);
this.transferLinks(q, t);
return t;
}
// 转换为红黑树时会使用
HashMap.TreeNode<K, V> replacementTreeNode(HashMap.Node<K, V> p, HashMap.Node<K, V> next) {
Entry<K, V> q = (Entry)p;
HashMap.TreeNode<K, V> t = new HashMap.TreeNode(q.hash, q.key, q.value, next);
this.transferLinks(q, t);
return t;HashMap提供的空实现方法
HashMap 提供了三个空实现的方法，用于在节点访问后、节点插入后、节点移除后进行回调
// 访问后
void afterNodeAccess(Node<K,V> p) { }
// 插入后
void afterNodeInsertion(boolean evict) { }
// 移除后
void afterNodeRemoval(Node<K,V> p) { }LinkedHashMap维护插入顺序
LinkedHashMap 在创建节点会调用 linkNodeLast ，将新创建的节点插入到双向链表中：
private void linkNodeLast(Entry<K, V> p) {
Entry<K, V> last = this.tail;
this.tail = p;
if (last == null) {
this.head = p;
} else {
p.before = last;
last.after = p;
}
}在链表转换为红黑树或者红黑树退化为链表时，会将其中的值进行替换：
private void transferLinks(Entry<K, V> src, Entry<K, V> dst) {
Entry<K, V> b = dst.before = src.before;
Entry<K, V> a = dst.after = src.after;
if (b == null) {
this.head = dst;
} else {
b.after = dst;
}
if (a == null) {
this.tail = dst;
} else {
a.before = dst;
}
}LinkedHashMap 通过重写 HashMap 的 afterNodeRemoval 方法，在删除节点时也会将其从双向链表中删除：
void afterNodeRemoval(HashMap.Node<K, V> e) {
Entry<K, V> p = (Entry)e;
Entry<K, V> b = p.before;
Entry<K, V> a = p.after;
p.before = p.after = null;
if (b == null) {
this.head = a;
} else {
b.after = a;
}
if (a == null) {
this.tail = b;
} else {
a.before = b;
}
}该方法用于限制 LinkedHashMap 的容量大小，其中 removeEldestEntry 是判断是否删除该节点，默认返回false，需要继承重写该方法，因此直接使用 LinkedHashMap 是没有被限制容量的（指这里）
void afterNodeInsertion(boolean evict) {
Entry first;
if (evict && (first = this.head) != null && this.removeEldestEntry(first)) {
K key = first.key;
this.removeNode(hash(key), key, (Object)null, false, true);
}
}LinkedHashMap维护访问顺序
HashMap 在访问某一个节点时，比如 get 方法访问、put方法覆盖已有的值都会回调该方法；
LinkedHashMap 通过实现该方法来更新节点的访问顺序；
对于新插入的节点，也算是访问顺序最新的，因此是插入到链表的最后面（在前面的方法）；
void afterNodeAccess(HashMap.Node<K, V> e) {
Entry last;
if (this.accessOrder && (last = this.tail) != e) {
Entry<K, V> p = (Entry)e;
Entry<K, V> b = p.before;
Entry<K, V> a = p.after;
p.after = null;
if (b == null) {
this.head = a;
} else {
b.after = a;
}
if (a != null) {
a.before = b;
} else {
last = b;
}
if (last == null) {
this.head = p;
} else {
p.before = last;
last.after = p;
}
this.tail = p;
++this.modCount;
}
}迭代顺序
内部实现了一个迭代器，根据维护的双向链表来进行迭代：
abstract class LinkedHashIterator {
Entry<K, V> next;
Entry<K, V> current;
int expectedModCount;
LinkedHashIterator() {
this.next = LinkedHashMap.this.head;
this.expectedModCount = LinkedHashMap.this.modCount;
this.current = null;
}
public final boolean hasNext() {
return this.next != null;
}
final Entry<K, V> nextNode() {
Entry<K, V> e = this.next;
if (LinkedHashMap.this.modCount != this.expectedModCount) {
throw new ConcurrentModificationException();
} else if (e == null) {
throw new NoSuchElementException();
} else {
this.current = e;
this.next = e.after;
return e;
}
}
public final void remove() {
HashMap.Node<K, V> p = this.current;
if (p == null) {
throw new IllegalStateException();
} else if (LinkedHashMap.this.modCount != this.expectedModCount) {
throw new ConcurrentModificationException();
} else {
this.current = null;
LinkedHashMap.this.removeNode(p.hash, p.key, (Object)null, false, false);
this.expectedModCount = LinkedHashMap.this.modCount;
}
}
}键值对Entry的迭代：
final class LinkedEntryIterator extends LinkedHashMap<K, V>.LinkedHashIterator implements Iterator<Map.Entry<K, V>> {
LinkedEntryIterator() {
super();
}
public final Map.Entry<K, V> next() {
return this.nextNode();
}
}
accessOrder&LRU
基于 accessOrder 是维护访问顺序的，当某个节点被访问过后，就会移动到双向链表的最后面；
同时 LinkedHashMap 提供了 removeEldestEntry 方法用于判断是否删除 “最老” 的节点（在这里就是在双向链表最前面的节点）
因此可以继承 LinkedHashMap 实现一个 LRU 缓存
private static final class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int maxCacheSize;
LRUCache(int initialCapacity, int maxCacheSize) {
super(initialCapacity, 0.75F, true);
this.maxCacheSize = maxCacheSize;
}
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return this.size() > this.maxCacheSize;
}
}在面试中如果遇到要手写 LRU 缓存，可以使用 LinkedHashMap 类似的思想自己实现：
用双向链表维护访问顺序，最新访问的移动到链表最后面
put 操作时检查当期大小是否大于指定阈值，大于了就删除双向链表最前面的节点；