Jdk1.6 Collections Framework源码解析(5)-LinkedHashMap

        前面总结了java.util.HashMap，这篇来看一下HashMap的一个子类——java.util.LinkedHashMap。
        先读了一下源码的注释，首先LinkedHashMap中所有的Entry组成了一个双向链表，该链表定义了内部数据的迭代顺序，通常是按key插入的顺序(最近插入的放到链表的末尾，覆盖操作不会影响链表顺序)。LinkedHashMap还提供了构造方法LinkedHashMap(int,float,boolean)，如果第三个参数为true，那么内部数据的迭代顺序是按访问的某种顺序(访问时间由远到近)，最近访问的数据会放到链表的末尾。这样的结构很适合建立一个LRU Cache，所以基于LinkedHashMap来构建一个LRU Cache是很方便的(可参见removeEldestEntry方法)。
        对于大部分的操作来说，LinkedHashMap的性能比HashMap稍慢那么一点点(由于维护内部双向链表需要附加一些操作，但总体还是常数时间的)。LinkedHashMap的几种视图的迭代(XXIterator)要比HashMap快一些，由于它可以根据内部的双向链表来迭代，而HashMap需要遍历内部的散列表。
        其他特性继承自HashMap，来看下源码。

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{

    private static final long serialVersionUID = 3801124242820219131L;

    /**
     * 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 specified initial capacity and load factor.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

    /**
     * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
     * with the specified initial capacity and a default load factor (0.75).
     *
     * @param  initialCapacity the initial capacity
     * @throws IllegalArgumentException if the initial capacity is negative
     */
    public LinkedHashMap(int initialCapacity) {
	super(initialCapacity);
        accessOrder = false;
    }

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

    /**
     * Constructs an insertion-ordered <tt>LinkedHashMap</tt> instance with
     * the same mappings as the specified map.  The <tt>LinkedHashMap</tt>
     * instance is created with a default load factor (0.75) and an initial
     * capacity sufficient to hold the mappings in the specified map.
     *
     * @param  m the map whose mappings are to be placed in this map
     * @throws NullPointerException if the specified map is null
     */
    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super(m);
        accessOrder = false;
    }

    /**
     * Constructs an empty <tt>LinkedHashMap</tt> instance with the
     * specified initial capacity, load factor and ordering mode.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @param  accessOrder     the ordering mode - <tt>true</tt> for
     *         access-order, <tt>false</tt> for insertion-order
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    public LinkedHashMap(int initialCapacity,
			 float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

        像LinkedList一样，内部存在一个表头header来作为双向链表的起点和终点(实际是一个环状)。accessOrder表示两种顺序——true为访问顺序；false为插入顺序。

    /**
     * Called by superclass constructors and pseudoconstructors (clone,
     * readObject) before any entries are inserted into the map.  Initializes
     * the chain.
     */
    void init() {
        header = new Entry<K,V>(-1, null, null, null);
        header.before = header.after = header;
    }

    /**
     * Transfers all entries to new table array.  This method is called
     * by superclass resize.  It is overridden for performance, as it is
     * faster to iterate using our linked list.
     */
    void transfer(HashMap.Entry[] newTable) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e = header.after; e != header; e = e.after) {
            int index = indexFor(e.hash, newCapacity);
            e.next = newTable[index];
            newTable[index] = e;
        }
    }


    /**
     * Returns <tt>true</tt> if this map maps one or more keys to the
     * specified value.
     *
     * @param value value whose presence in this map is to be tested
     * @return <tt>true</tt> if this map maps one or more keys to the
     *         specified value
     */
    public boolean containsValue(Object value) {
        // Overridden to take advantage of faster iterator
        if (value==null) {
            for (Entry e = header.after; e != header; e = e.after)
                if (e.value==null)
                    return true;
        } else {
            for (Entry e = header.after; e != header; e = e.after)
                if (value.equals(e.value))
                    return true;
        }
        return false;
    }

        还记得HashMap中的钩子方法init()，这里覆盖了init方法，在里面进行了双向链表的初始化。另外覆盖了transfer和containsValue方法，里面采用对链表的遍历，提高了一点儿性能。
        接下来先看一下LinkedHashMap中Entry的代码。

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

        /**
         * Removes this entry from the linked list.
         */
        private void remove() {
            before.after = after;
            after.before = before;
        }

        /**
         * Inserts this entry before the specified existing entry in the list.
         */
        private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }

        /**
         * This method is invoked by the superclass whenever the value
         * of a pre-existing entry is read by Map.get or modified by Map.set.
         * If the enclosing Map is access-ordered, it moves the entry
         * to the end of the list; otherwise, it does nothing.
         */
        void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            if (lm.accessOrder) {
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }
        }

        void recordRemoval(HashMap<K,V> m) {
            remove();
        }
    }

        重点看下recordAccess和recordRemoval方法。在分析总结HashMap的时候见过这两个钩子方法，在HashMap里，添加或者修改一个数据时(put)，会调用recordAccess；删除一个数据时会调用recordRemoval。
        LinkedHashMap的Entry里覆盖了这两个方法。在recordAccess里，如果accessOrder为true，说明是按访问顺序，那么改变双向链表的结构，把当前访问的Entry删掉，添加到链表的末尾。而在recordRemoval里则是从链表中删除当前的Entry。
        那么看下访问方法有什么变化。

    /**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     *
     * <p>More formally, if this map contains a mapping from a key
     * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
     * key.equals(k))}, then this method returns {@code v}; otherwise
     * it returns {@code null}.  (There can be at most one such mapping.)
     *
     * <p>A return value of {@code null} does not <i>necessarily</i>
     * indicate that the map contains no mapping for the key; it's also
     * possible that the map explicitly maps the key to {@code null}.
     * The {@link #containsKey containsKey} operation may be used to
     * distinguish these two cases.
     */
    public V get(Object key) {
        Entry<K,V> e = (Entry<K,V>)getEntry(key);
        if (e == null)
            return null;
        e.recordAccess(this);
        return e.value;
    }

        访问方法中调用了Entry的recordAccess方法。

    /**
     * This override alters behavior of superclass put method. It causes newly
     * allocated entry to get inserted at the end of the linked list and
     * removes the eldest entry if appropriate.
     */
    void addEntry(int hash, K key, V value, int bucketIndex) {
        createEntry(hash, key, value, bucketIndex);

        // Remove eldest entry if instructed, else grow capacity if appropriate
        Entry<K,V> eldest = header.after;
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        } else {
            if (size >= threshold)
                resize(2 * table.length);
        }
    }

    /**
     * This override differs from addEntry in that it doesn't resize the
     * table or remove the eldest entry.
     */
    void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMap.Entry<K,V> old = table[bucketIndex];
	Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
        table[bucketIndex] = e;
        e.addBefore(header);
        size++;
    }

    /**
     * Returns <tt>true</tt> if this map should remove its eldest entry.
     * This method is invoked by <tt>put</tt> and <tt>putAll</tt> after
     * inserting a new entry into the map.  It provides the implementor
     * with the opportunity to remove the eldest entry each time a new one
     * is added.  This is useful if the map represents a cache: it allows
     * the map to reduce memory consumption by deleting stale entries.
     *
     * <p>Sample use: this override will allow the map to grow up to 100
     * entries and then delete the eldest entry each time a new entry is
     * added, maintaining a steady state of 100 entries.
     * <pre>
     *     private static final int MAX_ENTRIES = 100;
     *
     *     protected boolean removeEldestEntry(Map.Entry eldest) {
     *        return size() > MAX_ENTRIES;
     *     }
     * </pre>
     *
     * <p>This method typically does not modify the map in any way,
     * instead allowing the map to modify itself as directed by its
     * return value.  It <i>is</i> permitted for this method to modify
     * the map directly, but if it does so, it <i>must</i> return
     * <tt>false</tt> (indicating that the map should not attempt any
     * further modification).  The effects of returning <tt>true</tt>
     * after modifying the map from within this method are unspecified.
     *
     * <p>This implementation merely returns <tt>false</tt> (so that this
     * map acts like a normal map - the eldest element is never removed).
     *
     * @param    eldest The least recently inserted entry in the map, or if
     *           this is an access-ordered map, the least recently accessed
     *           entry.  This is the entry that will be removed it this
     *           method returns <tt>true</tt>.  If the map was empty prior
     *           to the <tt>put</tt> or <tt>putAll</tt> invocation resulting
     *           in this invocation, this will be the entry that was just
     *           inserted; in other words, if the map contains a single
     *           entry, the eldest entry is also the newest.
     * @return   <tt>true</tt> if the eldest entry should be removed
     *           from the map; <tt>false</tt> if it should be retained.
     */
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }

        这里覆盖了父类的addEntry方法，当添加一个数据时，首先调用createEntry方法，该方法也做了重写，加入了维护链表的逻辑，把新加的数据放到了表尾。然后在addEntry方法中有一个判断——通过调用removeEldestEntry方法来决定是否删除最老的(最长时间未访问的)数据。如果是，删除表头的数据；否则，判断是否需要扩容。所以子类可以覆盖removeEldestEntry方法来达到删除最老数据的目的，这在实现一个Cache的时候是非常有用的。
        其余的代码也很容易看懂了，LinkedHashMap就总结到这儿。

评论

4 楼 BrokenDreams 2015-12-21  

a005020671 写道

BrokenDreams 写道

a005020671 写道

有点疑问的是，LinkedHashMap不是基于双向链表实现对不、LinkedHashMap是Hash表+双向链表，底层和HashMap一样仍然是一个hash表，只不过多内部节点同时又组成了一个双向循环链表，用来维持顺序。。。

对的。感谢指正，之前写的，现在回头看确实有歧义，会让人误以为每个桶(bucket)内部是双向链表呢~ 已将引起歧义的内容调整。
多交流~！！

我是yhj

3 楼 a005020671 2015-12-21  

BrokenDreams 写道

a005020671 写道

有点疑问的是，LinkedHashMap不是基于双向链表实现对不、LinkedHashMap是Hash表+双向链表，底层和HashMap一样仍然是一个hash表，只不过多内部节点同时又组成了一个双向循环链表，用来维持顺序。。。

对的。感谢指正，之前写的，现在回头看确实有歧义，会让人误以为每个桶(bucket)内部是双向链表呢~ 已将引起歧义的内容调整。
多交流~！！

我是yhj

2 楼 BrokenDreams 2015-12-21  

a005020671 写道

有点疑问的是，LinkedHashMap不是基于双向链表实现对不、LinkedHashMap是Hash表+双向链表，底层和HashMap一样仍然是一个hash表，只不过多内部节点同时又组成了一个双向循环链表，用来维持顺序。。。

对的。感谢指正，之前写的，现在回头看确实有歧义，会让人误以为每个桶(bucket)内部是双向链表呢~ 已将引起歧义的内容调整。
多交流~！！

1 楼 a005020671 2015-12-21  

有点疑问的是，LinkedHashMap不是基于双向链表实现对不、LinkedHashMap是Hash表+双向链表，底层和HashMap一样仍然是一个hash表，只不过多内部节点同时又组成了一个双向循环链表，用来维持顺序。。。