LinkedHashMap源码解读(JDK1.8)

在分析LinkedHashMap源码之前， 我们先看下LinkedHashMap在MyBatis缓存中的应用。我们知道LinkedHashMap继承于HashMap，所以底层结构还是数组+链表/红黑树。它的特殊之处在于维护了一个双向链表，使得在遍历Map时，输出是有序的。至于排序规则，是根据accessOrder变量来决定是按照插入顺序，还是按照访问顺序进行排序。

MyBatis中的LruCache

// 先进先出
// 最近最少使用缓存
public class LruCache implements Cache {

  // Cache和Map作用分别是什么？
  // 添加和删除的时候对这两个都进行操作了
  private final Cache delegate;

  private Map<Object, Object> keyMap;

  // 存储最早进入缓存的对象
  private Object eldestKey;

  // 构造函数，初始容量为1024
  // 为什么要传入一个Cache
  public LruCache(Cache delegate) {
    this.delegate = delegate;
    setSize(1024);
  }

  @Override
  public String getId() {
    return delegate.getId();
  }

  @Override
  public int getSize() {
    return delegate.getSize();
  }

  public void setSize(final int size) {
    //使用的是LinkedHashMap 双向链表+HashMap
    keyMap = new LinkedHashMap<Object, Object>(size, .75F, true) {
      private static final long serialVersionUID = 4267176411845948333L;

      // 移除最早进入缓存的entry
      protected boolean removeEldestEntry(Map.Entry<Object, Object> eldest) {
        boolean tooBig = size() > size;
        // 如果元素个数超过size，返回true，然后给最老键赋值
        if (tooBig) {
          eldestKey = eldest.getKey();
        }
        return tooBig;
      }
    };
  }

  @Override
  public void putObject(Object key, Object value) {
    delegate.putObject(key, value);
    cycleKeyList(key);
  }

  @Override
  public Object getObject(Object key) {
    keyMap.get(key); //touch
    // delegate是Cache类型，Cache作为一个接口类型，没有具体的属性，只有成员方法，那获取的元素存储在哪里
    // 解答：在使用LruCache的构造方法时，会传入一个具体的Cache类，调用方法如下
    // Cache cache = new PerpetualCache("default");
    // cache = new LruCache(cache);
    // 或者
    // Cache cache = new LruCache(new PerpetualCache("default"));
    // 而在PerpetualCache中，设置了两个变量，分别是private String id;
    // private Map<Object, Object> cache = new HashMap<Object, Object>();
    // cache用来存储键值对
    return delegate.getObject(key);
  }

  @Override
  public Object removeObject(Object key) {
    return delegate.removeObject(key);
  }

  @Override
  public void clear() {
    delegate.clear();
    keyMap.clear();
  }

  public ReadWriteLock getReadWriteLock() {
    return null;
  }

  // map put元素后，为什么要把cache中元素remove
  // 一个新元素进入，之前的最老元素就要移除
  private void cycleKeyList(Object key) {
    keyMap.put(key, key);
    // 在setSize方法中，检查元素个数后，大小如果不够时，会对eldestKey进行赋值
    if (eldestKey != null) {
      delegate.removeObject(eldestKey);
      eldestKey = null;
    }
  }

}

LruCache 最近最少使用缓存，核心就是覆盖 LinkedHashMap.removeEldestEntry方法,返回true或false表示 LinkedHashMap要不要删除此最老键值。返回true，会对eldestKey进行赋值，赋值后在putObject方法中调用的cycleKeyList(key)方法可知，会移除最老元素。

在分析了MyBatis的LruCache缓存的设计后，我们对于LinkedHashMap的应用有了一定的认识，下面我们来分析LinkedHashMap的源码。对于LinkedHashMap的get、put方法，这里不再赘述。本文重点描述LinkedHashMap如何维护双向链表，即双向链表的建立过程、节点删除过程以及对于LinkedHashMap中元素的有序访问是如何实现的。

LinkedHashMap

存储结构

LinkedHashMap的存储结构是数组+链表/红黑树，如下图所示

Entry

LinkedHashMap的Entry节点继承了HashMap的Node节点。Entry除了包括HashMap的Node节点信息外，还有两个前后指针。

Node节点属性:

final int hash;
final K key;
V value;
Node<K,V> next;

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);
        }
    }

从下面的图可以看出TreeNode、Entry、Node和Entry之间的关系

为什么要这么设计？
原因后续补上

双向链表的建立

LinkedHashMap没有重写HashMap的put、get方法。当有元素插入时，开始建立双向链表。最初是head，tail指向头节点，后面再插入新元素时，移动tail节点。节点与节点之间的关系通过before和after两个变量来维护。
我们先看下HashMap的put方法

public V put(K key, V value) {
        // onlyIfAbsent 传入的是false
        // 如果是true，表示如果存在相同的就不覆盖已经存在的value值
        // 为false 表示覆盖相同key的value值
        return putVal(hash(key), key, value, false, 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;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            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;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            // key已经存在
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                // value为空，更改value值
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

上面的putVal()方法中，调用到的newNode(hash, key, value, null)方法，在LinkedHashMap中重写了。下面是在LinkedHashMap中newNode的方法实现

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;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }

参考：http://javax.xyz/2018/01/24/LinkedHashMap-源码详细分析（JDK1-8）/