LinkedHashMap

一、双向链表结构

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

final boolean accessOrder;
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

三、get获取元素

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

// 在插入元素以后，判断当前容器的元素是否已满，如果是的话，就删除当前最老的元素，也就是队头元素。
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);
}
// 这是用户实现的回调方法，判断当前最老的元素是否需要删除，如果为true，就删除链表头元素
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
}

五、删除元素

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

abstract class LinkedHashIterator {
    LinkedHashMap.Entry<K,V> next;
    LinkedHashMap.Entry<K,V> current;
    int expectedModCount;
    LinkedHashIterator() {
        // 第一次从头开始遍历
        next = head;
        expectedModCount = modCount;
        current = null;
    }
    public final boolean hasNext() {
        return next != null;
    }
    final LinkedHashMap.Entry<K,V> nextNode() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        current = e;
        next = e.after;
        return e;
    }
    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;