简介
LinkedHashMap继承自HashMap，与HashMap有着类似的存储结构，LinkedHashMap类声明如下：
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
它继承于HashMap，实现了Map接口。
LinkedHashMap是非线程安全的，只是用于单线程环境下。
LinkedHashMap与HashMap的核心结构都相同，但是HashMap是无序的，即我们通过迭代HashMap所得到的元素顺序并不是它们最初放置到HashMap的顺序。而有时，我们却希望使用一个能够保持插入顺序的Map，LinkedHashMap就是为此设计的。
LinkedHashMap源码详解
LinkedHashMap是基于数组＋双向链表＋红黑树来实现的，其整体结构类似于下图：
因为LinkedHashMap继承自HashMap，故常用属性和HashMap都一样，比如具有相同的默认容量以及负载因子等属性。LinkedHashMap中的节点默认都被封装成为了Entry类型数据，它是LinkedHashMap对应的链表节点，Entry类继承自HashMap的Node类：
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节点，LinkedHashMap的Entry节点多了before和after两个属性，其中Entry节点的next属性用于维护HashMap各个桶中的Entry链，before和after属性则用于维护LinkedHashMap的双向链表。
上图中，实线即为next指针，虚线即为before和after指针，如果没有虚线的话，则上图是一个正常的HashMap结构，加上虚线，即增加了一个双向链表，head和tail分别为双向链表的首尾节点。
LinkedHashMap还增加了几个成员变量：
// 双向链表的头结点 transient LinkedHashMap.Entry<K,V> head; // 双向链表的尾结点 transient LinkedHashMap.Entry<K,V> tail; // 双向链表中元素排序规则的标志位 // accessOrder为false，表示按插入顺序排序 // accessOrder为true，表示按访问顺序排序 final boolean accessOrder;
根据accessOrder的值，LinkedHashMap可以实现LRU算法，若accessOrder为true，则表示按entry的访问顺序进行排序，此时，最新访问的entry将会被修改到双向链表的尾部。
LinkedHashMap具有五个构造方法：
// 参数指定了HashMap初始化时的容量以及负载因子，accessOrder默认为false，即按照节点的插入顺序排序
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
// 参数指定了HashMap初始化时的容量，负载因子使用默认负载因子0.75，accessOrder默认为false，即按照节点的插入顺序排序
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
// 无参构造方法，默认的初始化容量为16，负载因子为默认的0.75，accessOrder默认为false，即按照节点的插入顺序排序
public LinkedHashMap() {
super();
accessOrder = false;
}
// 根据其他Map来创建HashMap，负载因子为0.75，accessOrder默认为false，即按照节点的插入顺序排序
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
// 参数指定了HashMap初始化时的容量、负载因子以及accessOrder
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
我们下面来看LinkedHashMap的几个关键方法：put方法、get方法和remove方法。
put(K key, V value)方法
LinkedHashMap并没有重写HashMap的put(K key, V value)方法，HashMap的该方法实际上是调用了putVal方法：
// onlyIfAbsent为true时，则不覆盖key对应的value值，但是put在调用这个方法时，赋值为false，说明会覆盖原始value
// evict为false时，table处于创建模式，put在调用这个方法时，赋值为true
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// table为null或者table长度为0，则通过resize方法来初始化table，其中，n为数组的长度
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// (n - 1) & hash是计算出的节点在数组中的下标，若数组对应下标为null，则直接将节点赋值到tab[i]
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 若数组对应下标不为null，则表明发生了哈希冲突，其中，p为table[i]中的第一个节点
else {
Node<K,V> e; K k;
// 如果p节点与插入节点的hash和key相同，则e = p
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 否则，判断p节点是否为TreeNode，即判断链表是否已经调整为红黑树，若是的话，则通过putTreeVal来添加红黑树节点
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 否则，p为链表节点
else {
for (int binCount = 0; ; ++binCount) {
// 在链表尾节点处插入新节点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果链表节点个数在插入新的节点后，达到转为红黑树的阈值，则需要将链表转为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果插入节点和原链表中的某个key具有相同的hash且key相同，则停止查找
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// e != null表明哈希表中已经存在键为key的节点
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 若允许覆盖value值，或旧值为null，则更新key所对应的值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// HashMap结构修改次数加1
++modCount;
// 若节点个数 > threshold，则对table进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
虽然LinkedHashMap没有重写HashMap的put方法和putVal方法，但是LinkedHashMap修改了newNode方法，来将原来的Node节点替换为Entry节点，并维护了节点的顺序：
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
// 创建新增节点，该节点不再是Node类型，而是Entry类型
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
// 将新节点链接到链表尾部
linkNodeLast(p);
return p;
}
创建节点后，会调用linkNodeLast(LinkedHashMap.Entry<K,V>)方法将新节点链接到链表尾部：
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
// 获取双向链表的尾节点
LinkedHashMap.Entry<K,V> last = tail;
// 将新节点p设置为尾节点
tail = p;
// 若之前的双向链表为空，则初始化双向链表的头结点head
if (last == null)
head = p;
// 否则，将新节点p链接到双向链表尾部
else {
p.before = last;
last.after = p;
}
}
每次put到LinkedHashMap中的Entry都放在双向链表尾部，这样遍历双向链表时，Entry的输出顺序就会和插入的顺序一致，这也是默认的双向链表的存储顺序。
同样，LinkedHashMap重写了HashMap中定义的afterNodeAccess、afterNodeInsertion两个方法，在HashMap中这两个方法的实现都为空，其实还有一个afterNodeRemoval方法：
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
若哈希表中不存在要插入的key对应的节点，则在新节点插入之后，putVal会调用afterNodeInsertion方法；若key对应的节点已经存在，则putVal会调用afterNodeAccess方法，我们来看一下LinkedHashMap对这两个方法的实现：
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
// 如果evict为true、双向链表头结点不为null，且removeEldestEntry返回true，则删除首节点
// LinkedHashMap中的removeEldestEntry方法一直返回false，即不会删除节点
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// 若accessOrder为true，且双向链表尾结点不为e，则将e置为双向链表的尾节点
if (accessOrder && (last = tail) != e) {
// 将e强制转换为Entry节点p，b为p的前驱节点，a为p的后继节点
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// 将p的后继节点置为null，因为p要成为尾节点，尾节点是没有后继节点的
p.after = null;
// 如果p的前驱节点是null，即p以前是头结点head，所以现在要将头结点置为p的后继节点a
if (b == null)
head = a;
// 否则，直接b的后继节点设置为p的后继节点a
else
b.after = a;
// 如果p的后继节点a不是null，则直接将a的前驱节点置为b
if (a != null)
a.before = b;
// 否则，p的后置节点是null，即p就是尾节点，此时将last置为b
else
last = b;
// 如果双向链表尾节点是null，则链表中就一个节点，将head置为p
if (last == null)
head = p;
// 否则，将p的前驱节点置为last，将last的后继节点置为p
else {
p.before = last;
last.after = p;
}
// 将尾节点置为p
tail = p;
++modCount;
}
}
这两个方法是用来实现的实现LRU算法的。我们可以重写removeEldestEntry方法，来自动移除过期的节点，若双向链表按插入顺序排序，则删除最早插入双向链表的节点；若双向链表按访问顺序排序，则为删除最近最少访问的节点，这两种节点在不同的排序方式下都是首节点。
put方法的主要内容我们也就介绍到这，下面看get方法。
get(Object key)方法
LinkedHashMap重写了get(Object key)方法：
public V get(Object key) {
Node<K,V> e;
// 调用getNode方法获取对应节点
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
get(Object key)方法首先会通过getNode方法来获取key相应的节点，LinkedHashMap没有重写getNode方法，所以，getNode方法采用了HashMap的实现：
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// table不为null且长度不为0，且存在哈希值为hash的节点，first为对应下标的首节点
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 总是先检查first节点是否符合条件，若符合，则直接返回first节点
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 否则，若首节点存在后继节点
if ((e = first.next) != null) {
// 若首节点是TreeNode类型节点，则从红黑树中查找节点
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 从链表中查找节点
do {
// 若找到符合条件的节点，则直接返回节点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
// 否则返回null
return null;
}
在获取到节点之后，若节点为null，则直接返回null，否则，根据accessOrder来判断是否调用afterNodeAccess方法，然后返回节点的value。
remove(Object key)方法
LinkedHashMap同样没有重写remove(Object key)方法，LinkedHashMap使用HashMap的默认实现来删除节点：
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
// matchValue如果为true，则表示删除一个node的条件是：key和value都一致才删除
// movable如果为false，则表示删除当前节点时，不会移动其它节点
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
// table不为null且长度不为0，且存在哈希值为hash的节点，p为对应下标的首节点
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
// 总是先检查首节点p是否符合条件，若符合，则node = p
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
// 否则，若首节点存在后继节点
else if ((e = p.next) != null) {
// 若首节点是TreeNode类型节点，则从红黑树中查找节点
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
// 从链表中查找节点
else {
do {
// 若找到符合条件的节点，则node = e，退出循环
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
// 更新p
p = e;
} while ((e = e.next) != null);
}
}
// 如果找到指定key与哈希值的node，且保证了删除策略matchValue，则可以删除
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// node为红黑树节点，则调用红黑树节点删除方法
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
// 否则，node节点是链表节点，若node == p，p为node的前驱节点，则说明node为首节点，直接更新数组对应下标的首节点
else if (node == p)
tab[index] = node.next;
// 否则，更新p.next = node.next，删除node节点
else
p.next = node.next;
// HashMap结构修改次数加1
++modCount;
// 元素个数减1
--size;
afterNodeRemoval(node);
// 返回删除节点
return node;
}
}
// 返回null
return null;
}
但LinkedHashMap重写了afterNodeRemoval方法，在删除节点之后，会调用该方法：
void afterNodeRemoval(Node<K,V> e) { // unlink
// 将e强制转换为Entry节点p，b为p的前驱节点，a为p的后继节点
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// 将p的前驱节点和后继节点都置为null
p.before = p.after = null;
// 如果b为null，即p为头结点，那么现在的头结点应该是p的后继节点a
if (b == null)
head = a;
// 否则将b的后继节点置为a
else
b.after = a;
// 如果a为null，即p为尾结点，那么现在的尾结点应该是p的前驱节点b
if (a == null)
tail = b;
// 否则将a的前驱节点置为b
else
a.before = b;
}
该方法就是将节点删除时，同步将该节点从双向链表上删除。
LinkedHashMap其他相关方法
和HashMap一样，LinkedHashMap的key和value都可以为null，要判断一个key在LinkedHashMap中是否存在，是不可以用get(Object)方法来判断的，我们可以用containsKey(Object)方法来判断，LinkedHashMap没有重写该方法，采用了HashMap的实现方式：
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
containsValue(Object value)方法
LinkedHashMap重写了containsValue(Object value)方法：
public boolean containsValue(Object value) {
// 遍历双向链表
for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
V v = e.value;
// 若找到匹配的节点，则直接返回true
if (v == value || (value != null && value.equals(v)))
return true;
}
// 返回false
return false;
}
LinkedHashMap重写的containsValue(Object value)方法要比HashMap的containsValue(Object value)方法效率高一点，HashMap查找value时用了两个for循环，即使数组中的某一下标没有对应的链表，也要去查找，而LinkedHashMap查找value时，是通过双向链表来查找的，链表中的每一个节点都是有效地，而不用再去查找整个哈希表。
那为什么LinkedHashMap没有重写containsKey(Object)方法呢？
因为HashMap的containsKey(Object)方法已经很高效了，HashMap的containsKey(Object)方法是通过getNode方法来完成的，getNode方法会去key对应的数组链表中去查找，其节点个数可能远远小于双向链表的节点个数，所以LinkedHashMap采用HashMap实现的containsKey(Object)方法就可以了。
clear()方法
public void clear() {
// 调用HashMap的clear()方法
super.clear();
// 将双向链表的头尾节点置为null
head = tail = null;
}
利用LinkedHashMap实现LRU算法
从上面的源码中，我们知道，根据accessOrder的值，LinkedHashMap可以实现LRU算法，若accessOrder为true，则表示按entry的访问顺序进行排序，此时，最新访问的entry将会被修改到双向链表的尾部。下面我们来看一个例子：
public class LinkedHashMapTest {
static class LRUCache<K, V> extends LinkedHashMap<K, V> {
private static final long serialVersionUID = -2856190955107642776L;
private int maxSize;
public LRUCache(int maxSize) {
super(maxSize, 0.75f, true);
this.maxSize = maxSize;
}
@Override
protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
return size() > maxSize;
}
}
public static void main(String[] args) {
LRUCache<Integer, Integer> lCache = new LRUCache<>(3);
lCache.put(1, null);
lCache.put(2, null);
lCache.put(3, null);
printEntry(lCache);
lCache.put(4, null);
printEntry(lCache);
lCache.put(1, null);
printEntry(lCache);
lCache.put(4, null);
printEntry(lCache);
lCache.put(2, null);
printEntry(lCache);
lCache.put(5, null);
printEntry(lCache);
}
private static void printEntry(LRUCache<Integer, Integer> lCache) {
Set<Entry<Integer,Integer>> entrySet = lCache.entrySet();
String s = "";
for (Entry<Integer,Integer> entry : entrySet) {
s += entry.getKey() + " ";
}
System.out.println(s);
System.out.println("------");
}
}
运行结果：
1 2 3 ------ 2 3 4 ------ 3 4 1 ------ 3 1 4 ------ 1 4 2 ------ 4 2 5 ------
我们通过继承LinkedHashMap的方式来实现了LRU算法，我们除了要指定accessOrder为true之外，还要重写removeEldestEntry方法，在LinkedHashMap中，该方法一直返回false，我们需要做的就是，判断什么时候需要将最近最少访问的节点删除，我们这里实现的是如果节点数目已经达到了指定个数，那就删除最近最少访问的节点，这个指定个数是通过LRUCache的构造方法指定的。