LinkedHashMap

前言：

本文讲述的LinkedHashMap是HashMap的子类，他不仅实现了HashMap的所有功能，更是维护了元素的存储顺序。LinkedHashMap维护元素顺序的方式有两种，一种是维护他的存入顺序，另一种则是维护元素的读取顺序。基于这种功能，LinkedHashMap可以在用于LRU算法的实现。LRU为何物？LRU的全称是Least Recently Used翻译过来就是最近最久未使用，他通常应用于缓存的一种实现方式，当缓存数据满时，删除最少使用的缓存数据。
LinkedHashMap的结构是HashMap+双向链表。他通过继承HashMap得到了用hash表存储数据的能力，同时他又维护了一个双向链表实现了对元素的排序功能。HashMap部分上文已经介绍了，本文着重要介绍的是双向链表部分实现（这里有必要说明一下，我写的系列文章是基于jdk1.8的。jdk1.8和之前版本的实现有不少差异，LinkedHashMap部分就改动了不少，有兴趣的同学可以对照1.7的链表实现和1.8的链表实现，你会发现是两者差异很大，对于两种实现的优缺点可以自行思考哦）。下面就来一起研究研究吧。

一、双向链表结构

jdk1.8的链表结构和1.7的差异很大，可以看出来1.8中的实现简化了不是，只维护了两个指针，befor和after。在整个链表中维护了head（头指针）和tail（尾指针）。这两个指针是有讲究的，head所指向的是eldest元素，也就是最老的元素，tail指向youngest元素，也就是最年轻的元素。在这个链表中，都是在队尾添加元素，队头删除元素，这种方式很像队列，但是还是有点区别。 

  1. static class Entry<K,V> extends HashMap.Node<K,V> {
  2.     Entry<K,V> before, after;
  3.     Entry(int hash, K key, V value, Node<K,V> next) {
  4.         super(hash, key, value, next);
  5.     }
  6. }
  8. // 指向eldest元素
  9. transient LinkedHashMap.Entry<K,V> head;
  10. // 指向youngest元素
  11. transient LinkedHashMap.Entry<K,V> tail;

二、LinkedHashMap实例创建

LinkedHashMap的创建和HashMap没什么两样，就是这个构造方法中，加入了acessOrder的参数，告诉LinkedHashMap以哪种方式维护顺序。

  1. // 元素遍历顺序，true维护元素的访问顺序，最新访问的放入队尾，false维护元素的插入顺序，最新插入的在队尾。
  2. final boolean accessOrder;
  4. public LinkedHashMap(int initialCapacity,
  5.                      float loadFactor,
  6.                      boolean accessOrder) {
  7.     super(initialCapacity, loadFactor);
  8.     this.accessOrder = accessOrder;
  9. }

三、get获取元素

LinkedHashMap的get方法几乎就是复用了HashMap。唯一的区别就是多了一个accessOrder判断，如果accessOrder==true说明他需要维护元素的访问顺序，而afterNodeAccess是HashMap提供的回调方法，他也会在put元素的时候调用。afterNodeAccess方法的作用就是将当前访问的元素添加到队尾，因为这个链表都是从头部删除，因此这个元素会在最后才被删除。

  1. public V get(Object key) {
  2.     Node<K,V> e;
  3.     if ((e = getNode(hash(key), key)) == null)
  4.         return null;
  5.     if (accessOrder)
  6.         afterNodeAccess(e);
  7.     return e.value;
  8. }
  10. void afterNodeAccess(Node<K,V> e) { // 将访问元素添加到队尾
  11.     LinkedHashMap.Entry<K,V> last;
  12.     if (accessOrder && (last = tail) != e) {
  13.         LinkedHashMap.Entry<K,V> p =
  14.             (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
  15.         p.after = null;
  16.         // 如果当前元素是头元素，那么就将head指向他的下一个节点
  17.         if (b == null)
  18.             head = a;
  19.         else
  20.             b.after = a;
  21.         // 如果当前元素是尾元素，那么就将last指向他的上一个节点
  22.         if (a != null)
  23.             a.before = b;
  24.         else
  25.             last = b;
  26.         if (last == null)
  27.             head = p;
  28.         else {
  29.             p.before = last;
  30.             last.after = p;
  31.         }
  32.         tail = p;
  33.         ++modCount;
  34.     }
  35. }

四、put元素

LinkedHashMap并没有自己实现put方法，完完全全是复用了HashMap的，因为HashMap提供了两个回调方法作为他的扩展，LinkedHashMap只需要实现这两个方法即可，从这里也可以学到如何提供代码的扩展性，预先留出回调接口也是个不错的选择哦。在HashMap的put方法中，调用了两个回调方法，afterNodeAccess和afterNodeInsertion。第一个方法已经介绍了，下面就介绍afterNodeInsertion，这个方法的主要目的就是在map添加元素以后，维护链表的顺序，同时也会控制了对链表头元素的删除与否。 

  1. // 在插入元素以后，判断当前容器的元素是否已满，如果是的话，就删除当前最老的元素，也就是队头元素。
  2. void afterNodeInsertion(boolean evict) {
  3.     LinkedHashMap.Entry<K,V> first;
  4.     if (evict && (first = head) != null && removeEldestEntry(first)) {
  5.         K key = first.key;
  6.         removeNode(hash(key), key, null, false, true);
  7.     }
  8. }
  10. // 这是用户实现的回调方法，判断当前最老的元素是否需要删除，如果为true，就删除链表头元素
  11. protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
  12.     return false;
  13. }

五、删除元素

在删除元素以后，LinkedHashMap需要维护当前链表的指针，也就是双向链表的head和tail指针的指向问题 

  1. void afterNodeRemoval(Node<K,V> e) {
  2.     LinkedHashMap.Entry<K,V> p =
  3.         (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
  4.     p.before = p.after = null;
  5.     // 如果当前元素是头元素，那么head指向他的下一个节点
  6.     if (b == null)
  7.         head = a;
  8.     else
  9.         b.after = a;
  11.     // 如果当前元素是尾元素，那么tail指向他的上一个节点
  12.     if (a == null)
  13.         tail = b;
  14.     else
  15.         a.before = b;
  16. }

六、LinkedHashIterator遍历

容器的遍历是一个亘古不变的话题，然而LinkedHashMap的遍历方式有他的特殊性。因为他在hash表的基础之上又维护了一个双向链表，而这个链表维护这元素的遍历顺序，因为LinkedHashMap在遍历的时候，只能遍历这个链表，而不能像HashMap一样遍历hash表。 

  1. abstract class LinkedHashIterator {
  2.     LinkedHashMap.Entry<K,V> next;
  3.     LinkedHashMap.Entry<K,V> current;
  4.     int expectedModCount;
  6.     LinkedHashIterator() {
  7.         // 第一次从头开始遍历
  8.         next = head;
  9.         expectedModCount = modCount;
  10.         current = null;
  11.     }
  13.     public final boolean hasNext() {
  14.         return next != null;
  15.     }
  17.     // 对链表从头到尾开始遍历，顺序遍历的方式很简单就是next = e.after
  18.     final LinkedHashMap.Entry<K,V> nextNode() {
  19.         LinkedHashMap.Entry<K,V> e = next;
  20.         if (modCount != expectedModCount)
  21.             throw new ConcurrentModificationException();
  22.         if (e == null)
  23.             throw new NoSuchElementException();
  24.         current = e;
  25.         next = e.after;
  26.         return e;
  27.     }
  29.     public final void remove() {
  30.         Node<K,V> p = current;
  31.         if (p == null)
  32.             throw new IllegalStateException();
  33.         if (modCount != expectedModCount)
  34.             throw new ConcurrentModificationException();
  35.         current = null;
  36.         K key = p.key;
  37.         removeNode(hash(key), key, null, false, false);
  38.         expectedModCount = modCount;
  39.     }
  40. }