Map随笔：有序的HashMap——LinkedHashMap
一，概述
LinkedHashMap继承于HashMap(笔者另一篇分享HashMap的博文)，它的特点在于它的有序性。底层采用双向链表来实现数据节点的顺序性。LinkedHashMap的有序性分成两种，一种是输出顺序可以是插入的顺序，另一种顺序便是将最新操作的数据放在内部链表的尾部，可以用来做LRU算法（文中会详解）。
二，源码结构
1，属性
//链表的头部
transient LinkedHashMap.Entry<K,V> head;
//链表的尾部
transient LinkedHashMap.Entry<K,V> tail;
//存取数据后是否把数据放在尾部，该属性是LinkedHashMap实现LRU（最少使用）算法的关键
//默认都是false
final boolean accessOrder;
2，重要的内部类
static class Entry<K,V> extends HashMap.Node<K,V> {
//before：上一个节点，after：下一个节点
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两个属性，这两个属性是的多个Entry连成一条链表，这也时LinkedHashMap有序性的原理。
3，构造器
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
public LinkedHashMap() {
super();
accessOrder = false;
}
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
因为LinkedHashMap是继承HashMap的，所以构造器基本上都是类似的，无非不同的就是它多了一个属性accessOrder来控制内部排序的方式，可以看出默认都是fasle，如果要更改内部的默认的排序方式，可以使用三参的这个构造器。
4，核心方法
1，新建节点
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
//将节点添加到双向链表上
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
//如果链表尾部数据时null，则说明这个链表上没有数据，则当前新插入的数据便是链表的头部节点
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
LinkedHashMap重写了HashMap的新建节点方法，在原先基础上只是将新的节点添加到内部链表上而已，所以代码相对简单。
2，节点插入成功后的扩展方法
看过HashMap（Java8）源码的同学应该应该对这个方法有一些印象，如下，HashMap的put方法在新增数据之后，会先调用afterNodeInsertion方法，这也是HashMap预留给LinkedHashMap的可扩展点，像这种扩展点一共三处，另外两处，一个也是在putVal方法的数据修改后，另一个是在删除节点后。
// put数据
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
...................................
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//新增覆盖后
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
//新增数据后
afterNodeInsertion(evict);
return null;
}
// 删除节点
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
...................................
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
//节点删除后
afterNodeRemoval(node);
return node;
}
}
return null;
}
分开看一下这三个留给LinkedHashMap的扩展方法它都做了什么。首先afterNodeInsertion()——当数据插入后，因为LinkedHashMap比HashMap内部多了一个维持顺序的双向链表，所以不难猜出都干了什么，这么想，如果我们自己实现一个缓存，首先要解决的便是这个缓存空间满了怎么处理，第一想到的便是删除一些数据，那怎么删除，删除哪些数据，什么时候删除呢？用过Redis的都知道Redis采用的时LRU算法，当Redis的内存小于一点大小后，便会删除一些不常用的数据（Redis采用的也不是真正的LRU，具体这块不做过多研究），由Redis的理念我们便可以利用LinkedHashMap来实现我们自己定义的缓存了，首先怎么删除数据我们是不用考虑的，如下所示源码，删除是调用的HashMap的方法。下来就是删除哪些数据，由源码可以，每次删除的时顺序链表的头部的那个节点，而头部节点是什么数据，这个控制逻辑不在这个方法中定义，是在afterNodeAccess这个方法中吗，我们稍后在分析，剩下的就只有是什么时候删除这个问题，看源码，作者将什么时候删除这个问题的逻辑封装到了removeEldestEntry这个方法中，而这个方法我们是可以重写的，这对我们是非常友好的，我们可以自定义这个逻辑，最的简单的，我们写一段伪代码来讲(如下3)，我们可以设计当LinkedHashMap容量小于10时，删除节点，当然具体逻辑可以根据业务去设计。虽然说Java提供了LinkedHashMap的这个功能，但是基本上，工作中我们用的很少，但这块了解了解也不是什么坏事。
//1，当数据插入后
//evict：是否允许改变数据结构
void afterNodeInsertion(boolean evict) {
LinkedHashMap.Entry<K,V> first;
//如果顺序链表的头部节点不为null，则删除头部节点
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
//removeNode方法时HashMap的方法
removeNode(hash(key), key, null, false, true);
}
}
//2,LinkedHashMap 预留出来的扩展方法，如果此方法返回true，则在新增节点成功后删除顺序链表上的头部节点，也就是使用最少的节点，这个方法便是实现 用LinkedHashMap做缓存实现LRU算法的核心，默认返回的是false
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
//3，伪代码
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
if(容量 < 10){
return true;
}
return false;
}
接下来就是当数据修改后，LinkedHashMap的扩展方法afterNodeAccess，通过源码可以，每当每次put操作是更新了数据后，便把这个数据所在的节点放在顺序链的尾部，由此可知，调用频繁的节点总是处于链表的尾部，而链表的首部便是使用较少的甚至不用的数据，便可以删除.
void afterNodeAccess(Node<K,V> e) { // move node to last
//链表上的尾节点
LinkedHashMap.Entry<K,V> last;
//accessOrder的功能在这里编就体现了出来
if (accessOrder && (last = tail) != e) {
//拿到当前节点的上一个节点b和下一个节点a
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//因为要将当前的节点放在链表的尾部，所以当前节点的after置为null
p.after = null;
//如果b为空，说明当前节点是链表的head，则设置当前节点的下一个节点为head，否则将当前节点的上一个节点和下一个节点连接起来
if (b == null)
head = a;
else
b.after = a;
//如果a不为null，则将a和b连接起来，如果a为null，则说明当前节点可能是尾节点或者链表为null，
//判断链表是不是为null是由b节点判断的，如果b为null，说明当前链表为null（a为null，b为null）
if (a != null)
a.before = b;
else
last = b;
//如果last为null，则说明链表为null，设置当前节点为链表的head，否则设置当前节点到链表的尾部
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
//更新尾节点
tail = p;
//更新操作数，作用于Fast-Fail
++modCount;
}
}
最后一个，当节点删除时，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;
}
3，获取方法get()
LinkedHashMap重写了HashMap的get方法，在HashMap的get方法的原先逻辑上添加了排序逻辑，前面介绍的属性accessOrder在这里便有了用处，有源码可知，数据不光是在修改时会将当前节点移动到尾部，在获取时也会，但是去觉得accessOrder。
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
//如果允许排序
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
4，迭代器方法
我们猜测一下，如果使用迭代器遍历LinkedHashMap，如果采用HashMap的迭代器能按照顺序遍历出来吗？结果是否定的，HashMap并不知到LinkedHashMap内部双向链表的存在，所以LinkedHashMap也肯定重写了HashMap的迭代器逻辑
abstract class LinkedHashIterator {
LinkedHashMap.Entry<K,V> next;
LinkedHashMap.Entry<K,V> current;
//预期的map结构变化次数，用来判断是否抛出Fast-Fail 的异常
int expectedModCount;
LinkedHashIterator() {
//next等于链表的头部节点，遍历按照链表顺序遍历，HashMap next初始是等于null的
next = head;
expectedModCount = modCount;
current = null;
}
//和HashMap相同
public final boolean hasNext() {
return next != null;
}
//此处遍历是按照LinkedHashMap内部的双向链表来遍历，所以可以保证顺序
final LinkedHashMap.Entry<K,V> nextNode() {
LinkedHashMap.Entry<K,V> e = next;
//这里便是Map的Fast-Fail机制，如果你在迭代器中直接调用map的remove方法时，再次获取数据时便会报这个错，所以这也是为什么阿里巴巴java开发代码规范里，精致foreach时使用map删除方法的原因
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
current = e;
next = e.after;
return e;
}
//移除节点，如果在foreach中移除数据，应该采用迭代器的移除方法，因为迭代器中的移除方法在移除节点后将用于判断是否触发Fast-Fail的参数expectedModCount修改成LinkedHashMapmodCount
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}
三，总结
LinkedHashMap源码其实挺简单，无非就是内部多了一条链表来记录节点的先后顺序，另外就是重写了一些HashMap的部分方法，给这些方法中添加了内部链表相关的逻辑，另外，虽然说LinkedHashMap可以做缓存，也支持LRU，但是基本上如果要使用缓存还是采用类似与redis中这种，专业的东西做专业的事。另外就是Fast-Fail机制也作用于list和set等Collections的子集，我们需要在工作中注意。