JDK（六）JDK1.8源码分析【集合】LinkedHashMap

本文转载自joemsu，原文连接【JDK1.8】JDK1.8集合源码阅读——LinkedHashMap

LinkedHashMap的数据结构

可以从上图中看到，LinkedHashMap数据结构相比较于HashMap来说，添加了双向指针，分别指向前一个节点——before和后一个节点——after，从而将所有的节点已链表的形式串联一起来，从名字上来看LinkedHashMap与HashMap有一定的联系，实际上也确实是这样，LinkedHashMap继承了HashMap，重写了HashMap的一部分方法，从而加入了链表的实现。

本节我们将结合HashMap的部分源码一起分析一下LinkedHashMap。

LinkedHashMap的继承关系

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

LinkedHashMap的成员变量

// 用于指向双向链表的头部

transient LinkedHashMap.Entry<K,V> head;

//用于指向双向链表的尾部

transient LinkedHashMap.Entry<K,V> tail;

/**

 * 用来指定LinkedHashMap的迭代顺序，

 * true则表示按照基于访问的顺序来排列，意思就是最近使用的entry，放在链表的最末尾

 * false则表示按照插入顺序来

 */

final boolean accessOrder;

注意：accessOrder的final关键字，说明我们要在构造方法里给它初始化。

LinkedHashMap的构造方法

跟HashMap的构造方法类似，里面唯一的区别就是添加了前面提到的accessOrder，默认赋值为false——按照插入顺序来排列

//多了一个 accessOrder的参数，用来指定按照LRU排列方式还是顺序插入的排序方式

public LinkedHashMap(int initialCapacity,

                         float loadFactor,

                         boolean accessOrder) {

   super(initialCapacity, loadFactor);

   this.accessOrder = accessOrder;

}

LinkedHashMap的get()方法

public V get(Object key) {

  Node<K,V> e;

  //调用HashMap的getNode的方法，详见上一篇HashMap源码解析

  if ((e = getNode(hash(key), key)) == null)

    return null;

  //在取值后对参数accessOrder进行判断，如果为true，执行afterNodeAccess

  if (accessOrder)

    afterNodeAccess(e);

  return e.value;

}

从上面的代码可以看到，LinkedHashMap的get方法，调用HashMap的getNode方法后，对accessOrder的值进行了判断，我们之前提到：

accessOrder为true则表示按照基于访问的顺序来排列，意思就是最近使用的entry，放在链表的最末尾

由此可见，afterNodeAccess(e)就是基于访问的顺序排列的关键，让我们来看一下它的代码：

//此函数执行的效果就是将最近使用的Node，放在链表的最末尾

void afterNodeAccess(Node<K,V> e) {

  LinkedHashMap.Entry<K,V> last;

  //仅当按照LRU原则且e不在最末尾，才执行修改链表，将e移到链表最末尾的操作

  if (accessOrder && (last = tail) != e) {

    //将e赋值临时节点p， b是e的前一个节点， a是e的后一个节点

    LinkedHashMap.Entry<K,V> p =

      (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;

    //设置p的后一个节点为null，因为执行后p在链表末尾，after肯定为null

    p.after = null;

    //p前一个节点不存在，情况一

    if (b == null) // ①

      head = a;

    else

      b.after = a;

    if (a != null)

      a.before = b;

    //p的后一个节点不存在，情况二

    else // ②

      last = b;

    //情况三

    if (last == null) // ③

      head = p;

    //正常情况，将p设置为尾节点的准备工作，p的前一个节点为原先的last，last的after为p

    else {

      p.before = last;

      last.after = p;

    }

    //将p设置为尾节点

    tail = p;

    // 修改计数器+1

    ++modCount;

  }

}

标注的情况如下图所示（特别说明一下，这里是显示链表的修改后指针的情况，实际上在桶里面的位置是不变的，只是前后的指针指向的对象变了）：

下面来简单说明一下：

正常情况下：查询的p在链表中间，那么将p设置到末尾后，它原先的前节点b和后节点a就变成了前后节点；
情况一：p为头部，前一个节点b不存在，那么考虑到p要放到最后面，则设置p的后一个节点a为head；
情况二：p为尾部，后一个节点a不存在，那么考虑到统一操作，设置last为b；
情况三：p为链表里的第一个节点，head=p。

LinkedHashMap的put()方法

接下来，让我们来看一下LinkedHashMap是怎么插入Entry的：LinkedHashMap的put方法调用的还是HashMap里的put，不同的是重写了里面的部分方法：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

                   boolean evict) {

    ...

    tab[i] = newNode(hash, key, value, null);

    ...

    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

    ...

    if ((e = p.next) == null) {

      p.next = newNode(hash, key, value, null);

    ...

        afterNodeAccess(e);

    ...

        afterNodeInsertion(evict);

      return null;

}

这里省略了部分代码，LinkedHashMap将其中newNode方法以及之前设置下的钩子方法afterNodeAccess和afterNodeInsertion进行了重写，从而实现了加入链表的目的：

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {

  //秘密就在于 new的是自己的Entry类，然后调用了linkedNodeLast

  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) {

  //将tail给临时变量last

  LinkedHashMap.Entry<K,V> last = tail;

  //把new的Entry给tail

  tail = p;

  //若没有last，说明p是第一个节点，head=p

  if (last == null)

    head = p;

  //否则就把p的before指针指向last，last的after指针指向p

  else {

    p.before = last;

    last.after = p;

  }

}

//这里把TreeNode的重写也加了进来，因为putTreeVal里有调用了这个

TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {

  TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);

  linkNodeLast(p);

  return p;

}

//插入后把最老的Entry删除，不过removeEldestEntry总是返回false，所以不会删除，估计又是一个钩子方法给子类用的

void afterNodeInsertion(boolean evict) {

  LinkedHashMap.Entry<K,V> first;

  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;

}

总结：设计者灵活的运用了Override，以及设置的钩子方法，实现了双向链表。

LinkedHashMap的remove()方法

remove里面也设置了一个钩子方法：

final Node<K,V> removeNode(int hash, Object key, Object value,

                               boolean matchValue, boolean movable) {

  ...

      //node即是要删除的节点

      afterNodeRemoval(node);

  ...

}

void afterNodeRemoval(Node<K,V> e) {

  //与afterNodeAccess一样，记录e的前后节点b，a

  LinkedHashMap.Entry<K,V> p =

    (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;

  //p已删除，前后指针都设置为null，便于GC回收

  p.before = p.after = null;

  //与afterNodeAccess一样类似，一顿判断，然后b，a互为前后节点

  if (b == null)

    head = a;

  else

    b.after = a;

  if (a == null)

    tail = b;

  else

    a.before = b;

}

巴特西