LinkedHashMap具有以下特性

• LinkedHashMap继承自HashMap, 它可以保证迭代的顺序跟插入的顺序是一致的
• 不是同步的，如果多个线程同时访问，需要从外部保持同步
• LinkedHashMap还可以按照访问顺序进行排序，如果是按照访问顺序，那么调用get以后，会将访问的元素移到链表末尾

LinkedHashMap的重要变量

    /**
     * 双向链表的表头
     */
    private transient LinkedHashMapEntry<K,V> header;

    /**
     * true: 按照访问顺序; false: 按照插入顺序
     *
     * @serial
     */
    private final boolean accessOrder;

LinkedHashMap是HashMap的子类，从而继承了HashMap中属性，另外LinkedHashMap自定义了两个变量，这两个变量也就是实现其排序的关键

1. init

init方法会在构造函数中调用，HashMap的init是一个空实现，LinkedHashMap重写了init方法

    @Override
    void init() {
        header = new LinkedHashMapEntry<>(-1, null, null, null);
        header.before = header.after = header;
    }

init方法主要就是初始化了header变量，将header的beafore和after都指向header自身

2. put

LinkedHashMap没有重写put方法, 完全还是HashMap.put的逻辑

    public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);

        int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
        int i = indexFor(hash, table.length);
        for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

LinkedHashMap虽然没有重写put方法，但是其重写了两个关键方法recordAccess和addEntry, 其中recordAccess是用来记录访问顺序的方法，即更新当前entry的after,before

2.1 addEntry

void addEntry(int hash, K key, V value, int bucketIndex) {

        // removeEldestEntry(eldest)固定返回false..
        LinkedHashMapEntry<K,V> eldest = header.after;
        if (eldest != header) {
            boolean removeEldest;
            size++;
            try {
                removeEldest = removeEldestEntry(eldest);
            } finally {
                size--;
            }
            if (removeEldest) {
                removeEntryForKey(eldest.key);
            }
        }

        super.addEntry(hash, key, value, bucketIndex);
    }

虽然在super.addEntry之前有一段逻辑，但是由于removeEldestEntry方法固定返回false，所以这一段代码执行与否都没有什么影响..., super.addEntry主要是为了执行扩容操作，HashMap.addEntry在扩容后会执行createEntry方法，而LinkedHashMap重写了createEntry方法

2.2 createEntry

    void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMapEntry<K,V> old = table[bucketIndex];
        LinkedHashMapEntry<K,V> e = new LinkedHashMapEntry<>(hash, key, value, old);
        table[bucketIndex] = e;
        //更新链表指针, 【2.3】
        e.addBefore(header);
        size++;
    }

1. 创建对应的Entry, 如果是要归属到同一个链表内的，将newEntry的next指针指向oldEntry, 将newEntry放置到相应的索引处
2. 更新双向链表指针

2.3 LinkedHashMapEntry.addBefore

  private void addBefore(LinkedHashMapEntry<K,V> existingEntry) {
       after  = existingEntry;
       before = existingEntry.before;
       before.after = this;
       after.before = this;
  }

下面这张图显示了执行两次put操作后(假设没有hash冲突)的链表指向

3. get

public V get(Object key) {
        LinkedHashMapEntry<K,V> e = (LinkedHashMapEntry<K,V>)getEntry(key);
        if (e == null)
            return null;
        e.recordAccess(this);
        return e.value;
    }

3.1 LinkedHashMapEntry.recordAccess

    void recordAccess(java.util.HashMap<K,V> m) {
        LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
        if (lm.accessOrder) {
            lm.modCount++;
            //从双向链表中删除当前元素
            remove();
            //重新将元素添加到链表表头
            addBefore(lm.header);
        }
    }
    
    private void remove() {
        before.after = after;
        after.before = before;
    }

如果是访问顺序进行排序,首先将当前entry从双向链表中删除，之后再重新添当前entry到表头

4.遍历

LinkedHashMap的遍历需要注意的事项跟HashMap的一致，不能在使用迭代器遍历的时候调用LinkedHashMap.remove()删除元素，其原理不变，仍然是使用expectedModCount

4.1 LinkedHashIterator.nextEntry

LinkedHashMapEntry<K,V> nextEntry    = header.after;
LinkedHashMapEntry<K,V> lastReturned = null;

Map.Entry<K,V> nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();

  if (nextEntry == header)
        throw new NoSuchElementException();
    
   LinkedHashMapEntry<K,V> e = lastReturned = nextEntry;
   nextEntry = e.after;
   return e;
}

可以看到，迭代器迭代时，LinkedHashMap会从双向链表的header处开始向后按顺序遍历