LinkedHashMap其实是继承自HashMap，所以LinkedHashMap中的很多方法都是直接使用了HashMap，并且实现了HashMap中没有实现的，允许在LinkedHashMap后处理的回调。
LinkedHashMap 继承 HashMap，在 HashMap 的基础上进行扩展，put 方法并没有重写，说明LinkedHashMap遵循HashMap的数组加链表的结构，但是LinkedHashMap采用的链表是双向链表，从LinkedHashMapEntry可以看出。
LruCache其实就是封装了LinkedHashMap实现的

结构源码

LinkedHashMapEntry

LinkedHashMapEntry是继承自HashMap.Node，在LinkedHashMapEntry增加了两个属性before和after，用来保存当前节点的上一个节点和下一个节点

static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
    LinkedHashMapEntry<K,V> before, after;
    LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

HashMap.Node的源码与HashMap中的一致，可以看上一篇HasnMap源码解析

构造器

LinkedHashMap的构造器，除了需要传accessOrder属性值以外，默认都是accessOrder=false，即按插入顺序进行排序

    public LinkedHashMap() {
        super();
        accessOrder = false;
    }

常用函数解析

get(Object key)

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

afterNodeAccess是HashMap的空方法，在LinkedHashMap中进行了实现，用来对LinkedHashMap进行重新排序，安装访问顺序排序，将最近访问的放在最末尾

getNode(int hash, Object key)

public V get(Object key) {
  Node<K,V> e;
  return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
  Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
   //先是判断一通table是否为空以及根据hash找到存放的table数组的下标，
   //并赋值给临时变量。这里的(n-1)表示的就是Node数组的最大长度，
  //是2的x次方-1，这样得到的就是一个最高位往右都是1的二进制数，
  //然后与上一个hash值，有0的位上得0，就可以得到在table数组的下标
  if ((tab = table) != null && (n = tab.length) > 0 &&
      (first = tab[(n - 1) & hash]) != null) {
    //总是先检查数组下标第一个节点是否满足key，满足则返回
    if (first.hash == hash &&
        ((k = first.key) == key || (key != null && key.equals(k))))
      return first;
    //如果第一个与key不相等，则循环查看桶
    if ((e = first.next) != null) {
      //检查是否为树节点，是的话采用树节点的方法来获取对应的key的值
      if (first instanceof TreeNode)
        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
      //do-while循环判断，直到找到为止
      do {
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
          return e;
      } while ((e = e.next) != null);
    }
  }
  return null;
}

afterNodeAccess(Node<K,V> e)

afterNodeAccess(e)就是基于访问的顺序排列的关键
此函数执行的效果就是将最近使用的Node，放在链表的最末尾
这个方法在LinkedHashMap调用putVal的时候，也会执行，即在map已经存在当前存入的key的时候会调用该方法，然后移动节点到链表的末尾。

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设置为将p设置为尾节点
    tail = p;
    // 修改计数器+1
    ++modCount;
  }
}

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

put(K key, V value)

LinkedHashMap并没有重写put函数，依然是使用HashMap的put函数

public V put(K key, V value) {
  return putVal(hash(key), key, value, false, true);
}

/**
 * Implements Map.put and related methods
 * @param hash key的hash值
 * @param key
 * @param value
 * @param onlyIfAbsent 如果为true，则在有值的时候不会更新
 * @param evict false表示在创建map
 */
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;
  //如果tab对应的数组位置为空，则创建新的node，并指向它
  if ((p = tab[i = (n - 1) & hash]) == null)
    // newNode方法就是返回Node：return new Node<>(hash, key, value, next);
    tab[i] = newNode(hash, key, value, null); 
  else {
    Node<K,V> e; K k;
    //如果比较hash值和key的值都相等，说明要put的键值对已经在里面，赋值给e
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
      e = p;
    //如果p节点是树节点，则执行插入树的操作
    else if (p instanceof TreeNode)
      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    //不是树节点且数组中第一个也不是，则在桶中查找
    else {
      for (int binCount = 0; ; ++binCount) {
        //找到了最后一个都不满足的话，则在最后插入节点。注意这里的e = p.next，
        //赋值兼具判断都在if里了
        if ((e = p.next) == null) 
          p.next = newNode(hash, key, value, null);
          //之前field说明中的，如果桶中的数量大于树化阈值，则转化成树，
          //第一个是-1
          if (binCount >= TREEIFY_THRESHOLD - 1)
            treeifyBin(tab, hash);
          break;
        }
        //在桶中找到了对应的key，赋值给e，退出循环
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
          break;
        //没有找到，则继续向下一个节点寻找
        p = e;
      }
    }
    //上面循环中找到了e，则根据onlyIfAbsent是否为true来决定是否替换旧值
    if (e != null) {
      V oldValue = e.value;
      if (!onlyIfAbsent || oldValue == null)
        e.value = value;
      //钩子函数，用于给LinkedHashMap继承后使用，在HashMap里是空的
      //该函数会判断accessOrder是否为true，且最后一个节点是否为e
      //来判断是否需要按照访问顺序进行重排序
      afterNodeAccess(e);
      return oldValue;
    }
  }
  //修改计数器+1
  ++modCount;
  //实际大小+1， 如果大于阈值，重新计算并扩容
  if (++size > threshold)
    resize();
  //钩子函数，用于给LinkedHashMap继承后使用，在HashMap里是空的
  afterNodeInsertion(evict);
  return null;
}

resize()

final Node<K,V>[] resize() {
  Node<K,V>[] oldTab = table;
  //扩容/缩容前的容量
  int oldCap = (oldTab == null) ? 0 : oldTab.length;
  //旧的阈值
  int oldThr = threshold;
  int newCap, newThr = 0;
  //说明之前已经初始化过map
  if (oldCap > 0) {
    //达到了最大的容量，则将阈值设为最大，并且返回旧的table
    if (oldCap >= MAXIMUM_CAPACITY) {
      threshold = Integer.MAX_VALUE;
      return oldTab;
    }
    //如果两倍的旧容量小于最大的容量且旧容量大于等于默认初始化容量，
    //则旧的阈值也扩大两倍。
    //oldCap << 1，其实就是*2的意思。
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
             oldCap >= DEFAULT_INITIAL_CAPACITY)
      newThr = oldThr << 1; // double threshold
  }
  //旧容量为0且旧阈值大于0，则赋值给新的容量(应该是针对初始化的时候
  //指定了其容量的构造函数出现的这种情况)
  else if (oldThr > 0)
    newCap = oldThr;
  //这种情况就是调用无参数的构造函数
  //初始化table数组的大小和阈值
  //默认负载因子DEFAULT_LOAD_FACTOR=0.75f
  //默认初始table容量DEFAULT_INITIAL_CAPACITY=1<<4=16
  else {               
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  }
  // 新阈值为0，则通过：新容量*填充因子 来计算
  if (newThr == 0) {
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
              (int)ft : Integer.MAX_VALUE);
  }
  threshold = newThr;
  //根据新的容量来初始化table，并赋值给table
  @SuppressWarnings({"rawtypes","unchecked"})
  Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  table = newTab;
  //如果旧的table里面有存放节点，则初始化给新的table
  if (oldTab != null) {
    for (int j = 0; j < oldCap; ++j) {
      Node<K,V> e;
      //将下标为j的数组赋给临时节点e
      if ((e = oldTab[j]) != null) {
        //清空
        oldTab[j] = null;
        //如果该节点没有指向下一个节点，则直接通过计算hash和
        //新的容量来确定新的下标，并指向e
        if (e.next == null)
          newTab[e.hash & (newCap - 1)] = e;
        //如果为树节点，按照树节点的来拆分
        else if (e instanceof TreeNode)
          ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        //e还有其他的节点，将该桶拆分成两份(不一定均分)
        else {
          //loHead是拆分后的，链表的头部，tail为尾部
          Node<K,V> loHead = null, loTail = null;
          Node<K,V> hiHead = null, hiTail = null;
          Node<K,V> next;
          do {
            next = e.next;
            //根据e的hash值和旧的容量做位与运算是否为0来拆分，
            //注意之前是 e.hash & (oldCap - 1)
            if ((e.hash & oldCap) == 0) {
              if (loTail == null)
                loHead = e;
              else
                loTail.next = e;
              loTail = e;
            }
            else {
              if (hiTail == null)
                hiHead = e;
              else
                hiTail.next = e;
              hiTail = e;
            }
          } while ((e = next) != null);
          if (loTail != null) {
            loTail.next = null;
            newTab[j] = loHead;
          }
          if (hiTail != null) {
            hiTail.next = null;
            newTab[j + oldCap] = hiHead;
          }
        }
      }
    }
  }
  return newTab;
}

afterNodeInsertion(boolean evict)

在put之后，执行的插入后操作，但是removeNode在LinkedHashMap中总是返回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;
}

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

LinkedHashMap采用的双向链表，所以在构建链表时，LinkedHashMap需要给节点配置before和after

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
  //tail是链表的末尾节点，用于缓存每次新加入的末尾节点
  LinkedHashMap.Entry<K,V> last = tail;
  //把new的Entry给tail
  tail = p;
  //若没有last，说明p是第一个节点，head=p
  if (last == null)
    head = p;
  //否则就做准备工作，你懂的 (￣▽￣)"
  else {
    p.before = last;
    last.after = p;
  }
}

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

在LinkedHashMap中会重写newTreeNode函数，而且TreeNode是重写了LinkedHashMapEntry

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

//创建新的节点插入双向链表中
private void linkNodeLast(LinkedHashMapEntry<K,V> p) {
    // 将之前的尾巴节点做临时保存
    LinkedHashMapEntry<K,V> last = tail;
// 将新插入的节点赋值给尾节点
    tail = p;
    if (last == null)
     // 如果尾节点是null，则说明之前是一个空队列
        head = p;
    else {
     // 如果之前的尾节点不为null，则将新加入的节点的前节点置为之前的尾结点，
     // 将之前的尾结点的后节点置为新加入的节点
        p.before = last;
        last.after = p;
    }
}

其实newTreeNode的创建与newNode的创建并无多大区别，只是创建的节点对象从Node变成了TreeNode，而链表结构和红黑二叉树结构的节点都需要保存期before和after，这样是为了在红黑二叉树转成双向链表的时候能找到节点的上一个节点和下一个节点
这里暂时不分析红黑二叉树的转换，等TreeMap时再进行分析

removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable)

其实LinkedHashMap的removeNode就是HashMap的removeNode函数，只不过LinkedHashMap重写了afterNodeRemoval方法，而HashMap中这个方法是一个空方法，没有方法体

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

迭代器

public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        //返回LinkedEntrySet
        return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
}
final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
public final Iterator<Map.Entry<K,V>> iterator() {
return new LinkedEntryIterator();
}
}
final class LinkedEntryIterator extends LinkedHashIterator
        implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
}

    abstract class LinkedHashIterator {
        //下一个节点
        LinkedHashMap.Entry<K,V> next;
        //当前节点
        LinkedHashMap.Entry<K,V> current;
        int expectedModCount;

        LinkedHashIterator() {
            //初始化时，next 为 LinkedHashMap内部维护的双向链表的扁头
            next = head;
            //记录当前modCount，以满足fail-fast
            expectedModCount = modCount;
            //当前节点为null
            current = null;
        }
        //判断是否还有next
        public final boolean hasNext() {
            //就是判断next是否为null，默认next是head  表头
            return next != null;
        }
        //nextNode() 就是迭代器里的next()方法 。
        //该方法的实现可以看出，迭代LinkedHashMap，就是从内部维护的双链表的表头开始循环输出。
        final LinkedHashMap.Entry<K,V> nextNode() {
            //记录要返回的e。
            LinkedHashMap.Entry<K,V> e = next;
            //判断fail-fast
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            //如果要返回的节点是null，异常
            if (e == null)
                throw new NoSuchElementException();
            //更新当前节点为e
            current = e;
            //更新下一个节点是e的后置节点
            next = e.after;
            //返回e
            return e;
        }
        //删除方法 最终还是调用了HashMap的removeNode方法
        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;
        }
    }