概述
在平时开发的过程中，大部分都是使用HashMap存储key value结构的数据，但是它是没有顺序的，如果你想要一个有顺序的Map，这时候LinkedHashMap就闪亮登场, 本篇文章主要基于jdk1.8学习下LinkedHashMap的功能和原理。在学习LinkedHashMap你需要对HashMap底层实现和源码有一定了解。
介绍
LinkedHashMap是一个有顺序的Hash表，它可以是元素插入顺序或者访问顺序。
- LinkedHashMap最大的特点是有顺序的
- LinkedHashMap的key 和value都可以为空
- LinkedHashMap不是线程安全
以上是LinkedHashMap的类结构图:
- 继承了HashMap，在HashMap的功能基础上，增加了访问顺序的能力
使用案例
LinkedHashMap基于插入顺序
@Test public void test1() { // 创建默认的 LinkedHashMap Map<String, String> map = new LinkedHashMap<>(); // 插入 map.put("1", "1"); map.put("2", "2"); map.put("5", "5"); map.put("4", "4"); System.out.println(map); // 访问 map.get("2"); map.get("1"); System.out.println(map); }
运行结果：
小结：
- 默认LinkedHashMap是维护插入顺序，访问不会改变顺序
LinkedHashMap基于插入顺序和访问顺序
@Test public void test2() { // 创建 LinkedHashMap, accessOrder设置为true Map<String, String> map = new LinkedHashMap<String, String>(16, 0.75f, true); // 插入 map.put("1", "1"); map.put("2", "2"); map.put("5", "5"); map.put("4", "4"); System.out.println(map); // 访问 map.get("2"); map.get("1"); System.out.println(map); }
运行结果：
小结：
- 通过3个参数的构造函数可以创建出基于插入顺序+访问顺序的LinkedHashMap
核心机制
实现机制
LinkedHashMap继承了HashMap, 那么它也就拥有了HashMap的一些机制，包括扩容机制、转换成红黑树等都是一样的逻辑，但是LinkedHashMap拥有了一个更强的能力，就是有顺序，那么它是怎么维护节点的顺序呢？
LinkedHashMap额外维护了一个双向链表，在在每次插入数据，或者访问、修改数据时，会对这个双向链表增加节点、或调整链表的节点顺序，从而保证这个有序性。
源码解析
成员变量
通过成员变量我们看出LinkedHashMap底层的数据结构。
// 双向链表的头部节点（最早插入的，年纪最大的节点） transient LinkedHashMap.Entry<K,V> head; // 双向链表的尾部节点（最新插入的，年纪最小的节点） transient LinkedHashMap.Entry<K,V> tail; // 用于控制访问顺序，为true时，按插入顺序；为false时，按访问顺序 final boolean accessOrder;
LinkedHashMap继承自HashMap，所以内部存储数据的方式和HashMap一样，使用数组加链表（红黑树）的结构存储数据，LinkedHashMap和HashMap相比，额外的维护了一个双向链表，用于存储节点的顺序。这个双向链表的类型为LinkedHashMap.Entry：
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); } }
LinkedHashMap.Entry继承自HashMap的Node类，新增了before和after属性，用于维护前继和后继节点，以此形成双向链表。
构造方法
LinkedHashMap构造和HashMap多个一个accessOrder, 用于控制访问顺序。
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; }
只有这个构造函数可以通过参数修改accessOrder。
当accessOrder属性为true时，元素按访问顺序排列，即最近访问的元素会被移动到双向列表的末尾。所谓的“访问”并不是只有get方法，符合“访问”一词的操作有put、putIfAbsent、get、getOrDefault、compute、computeIfAbsent、computeIfPresent和merge方法。
关键方法
put方法
LinkedHashMap并没有put方法，而是使用的父类HashMap的put方法，那么它是怎么做到维护链表的呢？答案就是重写，HashMap提供了一些可以重写的入口。关于HashMap的源码这里就不详细分析了。
put方法最后是调到HashMap#putVal。
newNode方法用于创建链表节点，LinkedHashMap重写了newNode方法：
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) { // 创建LinkedHashMap.Entry实例 LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e); // 将新节点放入LinkedHashMap维护的双向链表尾部 linkNodeLast(p); return p; } 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; } }
所以可以看到，在put方法的时候调用newNode方法，LinkedHashMap会维护这个双向链表。
LinkedHashMap也重写了afterNodeAccess方法，顾名思义，就是当节点被访问后执行某些操作。
void afterNodeAccess(Node<K,V> e) { // move node to last LinkedHashMap.Entry<K,V> last; // 如果accessOrder属性为true，并且当前节点不是双向链表的尾节点的话执行if内逻辑 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; } }
LinkedHashMap也重写了afterNodeInsertion方法，执行节点插入成功后的逻辑：
void afterNodeInsertion(boolean evict) { // possibly remove eldest LinkedHashMap.Entry<K,V> first; // 如果头部节点不为空并且removeEldestEntry方法返回true的话 if (evict && (first = head) != null && removeEldestEntry(first)) { // 获取头部节点的key K key = first.key; // 调用父类HashMap的removeNode方法，删除这个key的节点，也就是第一个节点 removeNode(hash(key), key, null, false, true); } }
get方法
LinkedHashMap重写了HashMap的get方法，逻辑如下：
public V get(Object key) { Node<K,V> e; if ((e = getNode(hash(key), key)) == null) return null; // 当accessOrder属性为true时，将key对应的键值对节点移动到双向列表的尾部 if (accessOrder) afterNodeAccess(e); return e.value; }
这里的afterNodeAccess方法上面讲过了，用来节点访问时候的回调，需要通过构造方法设置accessOrder的属性为true才会生效。
remove方法
LinkedHashMap没有重写remove方法，查看HashMap的remove相关方法发现如下：
LinkedHashMap重写了这个afterNodeRemoval方法：
// 逻辑简单，改变节点的前继后继引用 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; }
通过该方法，我们就从LinkedHashMap的双向链表中删除对应的节点。
总结
本文主要分析了LinkedHashMap的有序性的这一特性，从源码层面理解它是如何保证有序的，但是前提希望大家能够对HashMap的实现或者源码有一定的基础，你才能够更好的理解LinkedHashMap。
