相信即便是Java初学者都应该用过Java中的HashMap和TreeMap，但貌似大多数人都没怎么用过LinkedHashMap，对其知之甚少。因为基本上大多数情况下TreeMap和HashMap都能满足需求，只有在需要map中K-V保持一定顺序时才会用到LinkedHashMap。所以保序是LinkedHashMap较HashMap和TreeMap最大的特点，至于保什么序后面会详细讲解。
从类图其实可以看出来，LinkedHashMap其实是完全继承于HashMap的，甚至好多地方干脆复用了HashMap的源码。其实可以认为HashMap的功能是LinkedHashMap的子集，HashMap可以做的LinkedHashMap都可以做。
如何使用
其使用方式和HashMap一致，但默认是能保持插入顺序的，所以使用Iterator比例keySet或者entrySet时可以得到和插入顺序一致的结果。
public static void main(String[] args) { Map<Integer, Integer> map = new LinkedHashMap<>(); map.put(4,2); map.put(2,4); map.put(3,5); Iterator<Integer> iterator = map.keySet().iterator(); while (iterator.hasNext()) { System.out.println(iterator.next()); } }
它不仅仅能保持插入顺序，也可以看元素是否访问调整顺序，下面代码和上面代码的区别是多了构造函数和一个元素的get。但迭代的结果完全不同。LinkedHashMap对访问调序的支持为简单实现LRUCache奠定了基础。
public static void main(String[] args) { Map<Integer, Integer> map = new LinkedHashMap<>(8, (float)0.75, true); map.put(4,2); map.put(2,4); map.put(3,5); map.get(4); Iterator<Integer> iterator = map.keySet().iterator(); while (iterator.hasNext()) { System.out.println(iterator.next()); } }
实现
从类图其实可以看出来，LinkedHashMap其实是完全继承于HashMap的，甚至好多地方干脆复用了HashMap的源码。其实可以认为HashMap的功能是LinkedHashMap的子集，HashMap可以做的LinkedHashMap都可以做。
其实说白了，LinkedHashMap其实就是在HashMap+链表，就是用双链表把HashMap中的每个Node串起来，可以看如下示意图，黄色线条代表链表中的关系，主体结构还是HashMap中的结构，关于HashMap可以看我另一篇博客Java HashMap源码浅析 。所以较HashMap的源码，LinkedHashMap就是多加了一些双链表的操作（插入、删除、节点挪动到尾部……）。
源码
初始化
LinkedHashMap的构造函数和HashMap的差不多类似，但多出来上图中的最后一个，其中参数多了一个boolean 类型的accessOrder，这个其实是否在节点被访问和变更后将其移动到双向链表的末尾，这也是文章最后实现LRUCache的关键参数。
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; }
Entry
Entry继承自HashMap.Node<K,V>，就是在HashMap.Node<K,V>的基础上只添加了双向链表的前后指针，代码很简单如下。
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); } }
put & get & resize & removeNode
其实LinkedHashMap中没有自己的put & get & resize & removeNode方法，完全是继承了HashMap中的方法。那肯定你也会好奇，LinkedHashMap中肯定每次增删改查总是会涉及到对双链表的操作，这是如何实现的？这个时候我们需要回到HashMap的源码中去。
// Callbacks to allow LinkedHashMap post-actions void afterNodeAccess(Node<K,V> p) { } void afterNodeInsertion(boolean evict) { } void afterNodeRemoval(Node<K,V> p) { }
如果你之前看HashMap的代码，你可能注意到了这三个没有实现的方法，你可能会很好奇他们有什么用。这三个方法在HashMap的各种操作中被用到了，看名字和注释也能看出来是在节点操作后做一些工作。可惜在HashMap中没用，你不看LinkedHashMap的源码肯定会感到莫名其妙的。
void afterNodeRemoval(Node<K,V> e) { // unlink 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; else b.after = a; if (a == null) tail = b; else a.before = b; } 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); } } void afterNodeAccess(Node<K,V> e) { // move node to last LinkedHashMap.Entry<K,V> last; 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; else b.after = a; if (a != null) a.before = b; else last = b; if (last == null) head = p; else { p.before = last; last.after = p; } tail = p; ++modCount; } }
afterNodeRemoval()就是在Map中元素被移除后也移除双链表中相应的元素。 afterNodeInsertion()就是额外在双链表尾部插入新元素。但afterNodeAccess()就比较奇怪了，它是把某个元素挪动到队列的尾部，这有啥用？
afterNodeAccess分别在putVal、merge、replace……总之所有有变动的地方调用，这以为着map中最新变动的值肯定是会在链表尾部，相反最旧的就在头部了（需要在构造函数中开启accessOrder）。
在afterNodeInsertion()中我们还看到了removeEldestEntry(first)，就是在插入新元素后移除最老的元素。 LinkedHashMap中默认是false，也就是不移除。如果我们继承了LinkedHashMap并对其重载，然后结合afterNodeAccess，就可以对最近最久未访问的元素做清理，不就是有个LRUCache了吗。
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
```
### LinkedHashMap如何实现遍历时的保序
开头说过，LinkedHashMap和HashMap最大的一个区别就是前者能实现遍历的保序。可以按插入顺序或者最久访问顺序遍历，如何实现的？其实看下keySet() values() entrySet()这几个key value k-v遍历方法就知道了。HashMap中无法保存顺序信息，但双链表可以啊，所以为了获取顺序信息，它们不是HashMap中从map中获取数据，而是从双向链表中获取。
```java public Set<K> keySet() { Set<K> ks = keySet; if (ks == null) { ks = new LinkedKeySet(); keySet = ks; } return ks; } final class LinkedKeySet extends AbstractSet<K> { public final int size() { return size; } public final void clear() { LinkedHashMap.this.clear(); } public final Iterator<K> iterator() { return new LinkedKeyIterator(); } public final boolean contains(Object o) { return containsKey(o); } public final boolean remove(Object key) { return removeNode(hash(key), key, null, false, true) != null; } public final Spliterator<K> spliterator() { return Spliterators.spliterator(this, Spliterator.SIZED | Spliterator.ORDERED | Spliterator.DISTINCT); } public final void forEach(Consumer<? super K> action) { if (action == null) throw new NullPointerException(); int mc = modCount; for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) action.accept(e.key); if (modCount != mc) throw new ConcurrentModificationException(); } }
values() entrySet()方法实现类似，就不全贴了。
LRUCache
上文提到多次LRUCache，其中LRU是Least Recently Used的缩写，其实就是想在有限的存储空间里保留更多有价值数据的一种方式。其实现的依旧就是最佳被使用的数据将来还被使用的概率更高，这个现象在计算机领域非常明显，很多优化就是基于此的。LRUCache就是这样一种存储的实现，它的难点就在于如何高效地剔除掉最旧的数据，以及如何维护数据的新旧度。
有了LinkedHashMap后，我们就可以很简单的实现一个LRUCache。依赖Linked和HashMap的结合，查询时可以从HashMap中以O(1)的时间复杂度查询，数据过期也可以用O(1)的时间复杂度从Linked中删除。LRUCache就是HashMap和Linked二者完美结合的体现。
一个LRUCache的完整代码如下，没错 是完整的代码，就是这么简单，主要的逻辑LinkedHashMap里都已经帮你实现了，你只需要稍微封装下就可以了。其实只需要重载下HashMap中的removeEldestEntry()方法就行，这个方法会在新节点插入或者旧节点访问后被调用。
import java.util.LinkedHashMap; import java.util.Map; public class LRUCache<K,V> extends LinkedHashMap<K,V> { private int maxCap; @Override protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return size() > this.maxCap; } public LRUCache(int capacity) { super(capacity, (float)0.75, true); this.maxCap = capacity; } }
