LinkedHashMap

java version "1.7.0_75"

特点

LinkedHashMap继承了HashMap，解决了HashMap的无序问题。
key和value都允许为空。key重复会覆盖，value可以重复。有序的。非线程安全的。

问题

LinkedHashMap在LRUCache（Least Recently Used）中的应用。
<small>答：主要是accessOrder的作用。图解集合6：LinkedHashMap</small>

基本属性

    /**
     * The head of the doubly linked list.
     */
    private transient Entry<K,V> header;

    /**
     * The iteration ordering method for this linked hash map: <tt>true</tt>
     * for access-order, <tt>false</tt> for insertion-order.
     *
     * @serial
     */
    private final boolean accessOrder;

构造器

    /**
     * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
     * with the default initial capacity (16) and load factor (0.75).
     */
    public LinkedHashMap() {
        super();
        accessOrder = false;
    }

LinkedHashMap中重写的Entry定义为：

private static class Entry<K,V> extends HashMap.Entry<K,V> {
        // These fields comprise the doubly linked list used for iteration.
        Entry<K,V> before, after;

        Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
            super(hash, key, value, next);
        }
}

put()

    public V put(K key, V value) {
        ...// 继承了HashMap
        addEntry(hash, key, value, i);//重写了addEntry()方法。
        return null;
    }
    void addEntry(int hash, K key, V value, int bucketIndex) {
         //HashMap中的addEntry()方法会调用createEntry()方法，此方法也被LinkedHashMap重写了。
        super.addEntry(hash, key, value, bucketIndex);

        // Remove eldest entry if instructed
        Entry<K,V> eldest = header.after;
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        }
    }
    //LinkedHashMap中多了addBefore()方法。
    void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMap.Entry<K,V> old = table[bucketIndex];
        Entry<K,V> e = new Entry<>(hash, key, value, old);
        table[bucketIndex] = e;
        e.addBefore(header);
        size++;
    }

        /**
         * Inserts this entry before the specified existing entry in the list.
         */
        //existingEntry即是header，是维护LinkedHashMap中元素顺序的双向链表的头。
        private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }