概述
在平时开发的过程中，大部分都是使用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<>();
-
// 插入
-
("1", "1");
-
("2", "2");
-
("5", "5");
-
("4", "4");
-
(map);
-
-
// 访问
-
("2");
-
("1");
-
-
(map);
-
}
运行结果：
小结：
- 默认LinkedHashMap是维护插入顺序，访问不会改变顺序
LinkedHashMap基于插入顺序和访问顺序
-
@Test
-
public void test2() {
-
// 创建 LinkedHashMap, accessOrder设置为true
-
Map<String, String> map = new LinkedHashMap<String, String>(16, 0.75f, true);
-
// 插入
-
("1", "1");
-
("2", "2");
-
("5", "5");
-
("4", "4");
-
(map);
-
-
// 访问
-
("2");
-
("1");
-
-
(map);
-
}
运行结果：
小结：
- 通过3个参数的构造函数可以创建出基于插入顺序+访问顺序的LinkedHashMap
核心机制
实现机制
LinkedHashMap继承了HashMap, 那么它也就拥有了HashMap的一些机制，包括扩容机制、转换成红黑树等都是一样的逻辑，但是LinkedHashMap拥有了一个更强的能力，就是有顺序，那么它是怎么维护节点的顺序呢？
LinkedHashMap额外维护了一个双向链表，在在每次插入数据，或者访问、修改数据时，会对这个双向链表增加节点、或调整链表的节点顺序，从而保证这个有序性。
源码解析
成员变量
通过成员变量我们看出LinkedHashMap底层的数据结构。
-
// 双向链表的头部节点（最早插入的，年纪最大的节点）
-
transient <K,V> head;
-
-
// 双向链表的尾部节点（最新插入的，年纪最小的节点）
-
transient <K,V> tail;
-
-
// 用于控制访问顺序，为true时，按插入顺序；为false时，按访问顺序
-
final boolean accessOrder;
LinkedHashMap继承自HashMap，所以内部存储数据的方式和HashMap一样，使用数组加链表（红黑树）的结构存储数据，LinkedHashMap和HashMap相比，额外的维护了一个双向链表，用于存储节点的顺序。这个双向链表的类型为：
-
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);
-
}
-
}
继承自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) {
-
// 创建实例
-
<K,V> p =
-
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
-
// 将新节点放入LinkedHashMap维护的双向链表尾部
-
linkNodeLast(p);
-
return p;
-
}
-
-
private void linkNodeLast(<K,V> p) {
-
<K,V> last = tail;
-
tail = p;
-
// 如果尾节点为空，说明双向链表是空的，所以将该节点赋值给头节点，双向链表得以初始化
-
if (last == null)
-
head = p;
-
else {
-
// 否则将该节点放到双向链表的尾部
-
= last;
-
= p;
-
}
-
}
所以可以看到，在put方法的时候调用newNode方法，LinkedHashMap会维护这个双向链表。
LinkedHashMap也重写了afterNodeAccess方法，顾名思义，就是当节点被访问后执行某些操作。
-
void afterNodeAccess(Node<K,V> e) { // move node to last
-
<K,V> last;
-
// 如果accessOrder属性为true，并且当前节点不是双向链表的尾节点的话执行if内逻辑
-
if (accessOrder && (last = tail) != e) {
-
// 下面的逻辑就是将当前节点移动到双向链表的尾部，并且改变相关节点的前继后继关系
-
<K,V> p =
-
(<K,V>)e, b = , a = ;
-
= null;
-
if (b == null)
-
head = a;
-
else
-
= a;
-
if (a != null)
-
= b;
-
else
-
last = b;
-
if (last == null)
-
head = p;
-
else {
-
= last;
-
= p;
-
}
-
tail = p;
-
++modCount;
-
}
-
}
LinkedHashMap也重写了afterNodeInsertion方法，执行节点插入成功后的逻辑：
-
void afterNodeInsertion(boolean evict) { // possibly remove eldest
-
<K,V> first;
-
// 如果头部节点不为空并且removeEldestEntry方法返回true的话
-
if (evict && (first = head) != null && removeEldestEntry(first)) {
-
// 获取头部节点的key
-
K 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 ;
-
}
这里的afterNodeAccess方法上面讲过了，用来节点访问时候的回调，需要通过构造方法设置accessOrder的属性为true才会生效。
remove方法
LinkedHashMap没有重写remove方法，查看HashMap的remove相关方法发现如下：
LinkedHashMap重写了这个afterNodeRemoval方法：
-
// 逻辑简单，改变节点的前继后继引用
-
void afterNodeRemoval(Node<K,V> e) { // unlink
-
<K,V> p =
-
(<K,V>)e, b = , a = ;
-
= = null;
-
if (b == null)
-
head = a;
-
else
-
= a;
-
if (a == null)
-
tail = b;
-
else
-
= b;
-
}
通过该方法，我们就从LinkedHashMap的双向链表中删除对应的节点。
总结
本文主要分析了LinkedHashMap的有序性的这一特性，从源码层面理解它是如何保证有序的，但是前提希望大家能够对HashMap的实现或者源码有一定的基础，你才能够更好的理解LinkedHashMap。