LinkedHashMap源码分析。-蒲公英云

/**
 * Map 接口的哈希表和链接列表实现，具有可预知的迭代顺序。此实现与 HashMap 的不同之处在于，
 * 后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，
 * 该迭代顺序通常就是将键插入到映射中的顺序（插入顺序）。注意，如果在映射中重新插入 键，则插入顺序不受影响。
 * （如果在调用 m.put(k, v) 前 m.containsKey(k) 返回了 true，
 * 则调用时会将键 k 重新插入到映射 m 中。） 
 * 此实现可以让客户避免未指定的、由 HashMap（及 Hashtable）所提供的通常为杂乱无章的排序工作，
 * 同时无需增加与 TreeMap 相关的成本。使用它可以生成一个与原来顺序相同的映射副本，而与原映射的实现无关： 
 *     void foo(Map m) {
 *         Map copy = new LinkedHashMap(m);
 *         ...
 *     }
 * 如果模块通过输入得到一个映射，复制这个映射，然后返回由此副本确定其顺序的结果，这种情况下这项技术特别有用。
 * （客户通常期望返回的内容与其出现的顺序相同。） 
 * 提供特殊的构造方法来创建链接哈希映射，该哈希映射的迭代顺序就是最后访问其条目的顺序，
 * 从近期访问最少到近期访问最多的顺序（访问顺序）。这种映射很适合构建 LRU 缓存。
 * 调用 put 或 get 方法将会访问相应的条目（假定调用完成后它还存在）。
 * putAll 方法以指定映射的条目集迭代器提供的键-值映射关系的顺序，为指定映射的每个映射关系生成一个条目访问。
 * 任何其他方法均不生成条目访问。特别是，collection 视图上的操作不 影响底层映射的迭代顺序。 
 * 可以重写 removeEldestEntry(Map.Entry) 方法来实施策略，
 * 以便在将新映射关系添加到映射时自动移除旧的映射关系。 
 * 此类提供所有可选的 Map 操作，并且允许 null 元素。
 * 与 HashMap 一样，它可以为基本操作（add、contains 和 remove）提供稳定的性能，
 * 假定哈希函数将元素正确分布到桶中。由于增加了维护链接列表的开支，其性能很可能比 HashMap 稍逊一筹，
 * 不过这一点例外：LinkedHashMap 的 collection 视图迭代所需时间与映射的大小 成比例。
 * HashMap 迭代时间很可能开支较大，因为它所需要的时间与其容量 成比例。 
 * 链接的哈希映射具有两个影响其性能的参数：初始容量和加载因子。它们的定义与 HashMap 极其相似。
 * 要注意，为初始容量选择非常高的值对此类的影响比对 HashMap 要小，因为此类的迭代时间不受容量的影响。 
 * 注意，此实现不是同步的。如果多个线程同时访问链接的哈希映射，而其中至少一个线程从结构上修改了该映射，
 * 则它必须 保持外部同步。这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象，
 * 则应该使用 Collections.synchronizedMap 方法来“包装”该映射。
 * 最好在创建时完成这一操作，以防止对映射的意外的非同步访问：     
 *  Map m = Collections.synchronizedMap(new LinkedHashMap(...));
 * 结构修改是指添加或删除一个或多个映射关系，或者在按访问顺序链接的哈希映射中影响迭代顺序的任何操作。
 * 在按插入顺序链接的哈希映射中，仅更改与映射中已包含键关联的值不是结构修改。
 * 在按访问顺序链接的哈希映射中，仅利用 get 查询映射不是结构修改。） 
 * Collection（由此类的所有 collection 视图方法所返回）的 iterator 方法返回的迭代器
 * 都是快速失败 的：在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器自身的 remove 方法，
 * 其他任何时间任何方式的修改，迭代器都将抛出 ConcurrentModificationException。
 * 因此，面对并发的修改，迭代器很快就会完全失败，而不冒将来不确定的时间任意发生不确定行为的风险。 
 * 注意，迭代器的快速失败行为无法得到保证，因为一般来说，不可能对是否出现不同步并发修改做出任何硬性保证。
 * 快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。
 * 因此，编写依赖于此异常的程序的方式是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测程序错误。
 * @param <K>    由此映射维护的键的类型
 * @param <V>    映射值的类型
 */
public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{
    private static final long serialVersionUID = 3801124242820219131L;
    // 双链表的头。
    private transient Entry<K,V> header;
    // 这个链接哈希映射的迭代排序方法:true for 访问顺序（access-ordered）， false for 插入顺序（insertion-order）。
    private final boolean accessOrder;
    /**
     * 构造一个带指定初始容量和加载因子的空插入顺序 LinkedHashMap 实例。
     * @param initialCapacity    初始容量
     * @param loadFactor    加载因子
     */
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }
    /**
     * 构造一个带指定初始容量和默认加载因子 (0.75) 的空插入顺序 LinkedHashMap 实例。
     * @param initialCapacity    初始容量
     */
    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }
    /**
     * 构造一个带默认初始容量 (16) 和加载因子 (0.75) 的空插入顺序 LinkedHashMap 实例。 
     */
    public LinkedHashMap() {
        super();
        accessOrder = false;
    }
    /**
     * 构造一个映射关系与指定映射相同的插入顺序 LinkedHashMap 实例。
     * 所创建的 LinkedHashMap 实例具有默认的加载因子 (0.75) 和足以容纳指定映射中映射关系的初始容量。 
     * @param m    要将其映射关系存放在此映射中的映射 
     */
    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super(m);
        accessOrder = false;
    }
    /**
     * 构造一个带指定初始容量、加载因子和排序模式的空 LinkedHashMap 实例。 
     * @param initialCapacity    初始容量
     * @param loadFactor    加载因子
     * @param accessOrder    排序模式 - 对于访问顺序，为 true；对于插入顺序，则为 false 
     */
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
    /**
     * 由超类构造函数和伪构造函数(clone、readObject)在将任何条目（entry）插入映射之前调用。初始化链。
     */
    @Override
    void init() {
        header = new Entry<>(-1, null, null, null);
        header.before = header.after = header;
    }
    /**
     * 将所有项传输到新表数组。此方法由超类resize()方法调用。为了提高性能，它被重写，因为使用链表迭代更快。
     * @param newTable    与当前对象相关联的新table[]
     * @param rehash    是否计算条目（entry）的哈希值
     */
    @Override
    void transfer(HashMap.Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e = header.after; e != header; e = e.after) {// 遍历链表
            if (rehash)// 是否计算条目（entry）的哈希值
                e.hash = (e.key == null) ? 0 : hash(e.key);
            int index = indexFor(e.hash, newCapacity);// 返回哈希码e.hash在表中的索引。
            e.next = newTable[index];
            newTable[index] = e;
        }
    }
    /**
     * 如果此映射将一个或多个键映射到指定值，则返回 true。
     * 覆盖：类 HashMap<K,V> 中的 containsValue
     * @param value    其在此映射中的存在已经测试的值
     * @return 如果此映射将一个或多个键映射到指定值，则返回 true
     */
    public boolean containsValue(Object value) {
        // 重写以利用更快的迭代器
        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;
    }
    /**
     * 返回此映射到指定键的值。如果此映射中没有该键的映射关系，则返回 null 。 
     * 更确切地讲，如果此映射包含满足 (key==null ? k==null : key.equals(k)) 
     * 的从键 k 到值 v 的映射关系，则此方法返回 v；否则，返回 null。
     * （最多只能有一个这样的映射关系。） 
     * 返回 null 值并不 一定 表明此映射不包含该键的映射关系；也可能此映射将该键显式地映射为 null。
     * 可使用 containsKey 操作来区分这两种情况。
     * 覆盖：类 HashMap<K,V> 中的 get
     * @param key    要返回其关联值的键
     * @return V    指定键所映射的值；如果此映射不包含该键的映射关系，则返回 null
     */
    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;
    }
    /**
     * 从该映射中移除所有映射关系。此调用返回后映射将为空。
     * 覆盖：类 HashMap<K,V> 中的 clear
     */
    public void clear() {
        super.clear();// 调用HashMap.clear()方法
        header.before = header.after = header;
    }
    /**
     * LinkedHashMap entry.
     */
    private static class Entry<K,V> extends HashMap.Entry<K,V> {
        // 这些字段包含用于迭代的双链表。
        Entry<K,V> before, after;
        /**
         * 创建新条目
         * @param hash    哈希值
         * @param key    键
         * @param value    值
         * @param next    下一个条目
         */
        Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
            super(hash, key, value, next);
        }
        /**
         * 从链表中移除此条目（entry）。
         * 即：上一个条目的after指向当前条目的after，下一个条目的before指向当前条目的before。
         */
        private void remove() {
            before.after = after;
            after.before = before;
        }
        /**
         * 将此条目插入到列表中指定的现有条目之前。
         */
        private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }
        /**
         * 每当Map.get()读取已存在条目的值时，超类就会调用此方法。通过Map.set获取或修改。
         * 如果所包围的映射是访问顺序（access-ordered）的，则将该条目移动到列表的末尾;否则，它什么也做不了。
         */
        void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            if (lm.accessOrder) {// 如果是访问顺序
                lm.modCount++;
                remove();// 从链表中移除此条目（entry）。
                addBefore(lm.header);// 将此条目插入到列表中指定的现有条目（lm.header）之前。
            }
        }
        /**
         * 从链表中移除此条目（entry）。
         * @param m
         */
        void recordRemoval(HashMap<K,V> m) {
            remove();
        }
    }
    private abstract class LinkedHashIterator<T> implements Iterator<T> {
        Entry<K,V> nextEntry    = header.after;
        Entry<K,V> lastReturned = null;
        /**
         * 迭代器认为支持列表应该具有的modCount值。如果违反了此期望，迭代器将检测到并发修改。
         */
        int expectedModCount = modCount;
        /**
         * 如果仍有元素可以迭代，则返回 true。
         */
        public boolean hasNext() {
            return nextEntry != header;
        }
        /**
         * 从迭代器指向的 collection 中移除迭代器返回的最后一个元素（可选操作）。
         */
        public void remove() {
            if (lastReturned == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            // 调用HashMap.remove()方法，
            LinkedHashMap.this.remove(lastReturned.key);
            lastReturned = null;
            expectedModCount = modCount;
        }
        /**
         * 返回下一个条目
         * @return
         */
        Entry<K,V> nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (nextEntry == header)
                throw new NoSuchElementException();
            Entry<K,V> e = lastReturned = nextEntry;
            nextEntry = e.after;
            return e;
        }
    }
    /**
     *    key迭代器 
     */
    private class KeyIterator extends LinkedHashIterator<K> {
        public K next() { return nextEntry().getKey(); }
    }
    /**
     * value迭代器 
     */
    private class ValueIterator extends LinkedHashIterator<V> {
        public V next() { return nextEntry().value; }
    }
    /**
     * 条目迭代器 
     */
    private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
        public Map.Entry<K,V> next() { return nextEntry(); }
    }
    // 这些重写改变了超类视图的iterator()方法的行为
    Iterator<K> newKeyIterator()   { return new KeyIterator();   }
    Iterator<V> newValueIterator() { return new ValueIterator(); }
    Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }
    /**
     * 此重写更改超类.put()方法的行为。它使新分配的项插入到链表的末尾，并在适当的情况下删除最年长的条目（the eldest entry）。
     * @param hash    根据键计算的哈希值
     * @param key    指定值将要关联的键
     * @param value    指定键将要关联的值
     * @param bucketIndex    在table[]数组上的索引
     */
    void addEntry(int hash, K key, V value, int bucketIndex) {
        super.addEntry(hash, key, value, bucketIndex);
        // 如果有指令，则删除最年长的（eldest ）条目（entry）
        Entry<K,V> eldest = header.after;
        if (removeEldestEntry(eldest)) {// 如果此映射移除其最旧的条目（eldest），则返回 true。
            removeEntryForKey(eldest.key);// 调用HashMap.removeEntryForKey()，删除并返回与LinkedHashMap中指定键关联的条目。
        }
    }
    /**
     * 此重写与addEntry()的不同之处在于，它不会调整表的大小或删除最老的条目（the eldest entry）。
     * @param hash    根据键计算的哈希值
     * @param key    指定值将要关联的键
     * @param value    指定键将要关联的值
     * @param bucketIndex 在table[]数组上的索引
     */
    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);// 将此条目插入到列表中指定的现有条目（header）之前。
        size++;
    }
    /**
     * 如果此映射移除其最旧的条目，则返回 true。在将新条目插入到映射后，put 和 putAll 将调用此方法。
     * 此方法可以提供在每次添加新条目时移除最旧条目的实现程序。
     * 如果映射表示缓存，则此方法非常有用：它允许映射通过删除旧条目来减少内存损耗。 
     * 示例用法：此重写允许映射增加到 100 个条目，然后每次添加新条目时删除最旧的条目，始终维持 100 个条目的稳定状态。 
     *     private static final int MAX_ENTRIES = 100;
     *     protected boolean removeEldestEntry(Map.Entry eldest) {
     *         return size() > MAX_ENTRIES;
     *     }
     * 此方法通常不以任何方式修改映射，相反允许映射在其返回值的指引下进行自我修改。
     * 使用此方法直接修改映射是 允许的，但是如果它执行了此操作，则一定 返回 false（表示该映射不应进行任何进一步的修改）。
     * 在此方法中修改映射后是否返回 true 是不确定的。 
     * 此实现仅返回 false（这样，此映射的行为将类似于正常映射，即永远不能移除最旧的元素）。 
     * @param eldest 在映射中最早插入的条目；如果是访问顺序映射，则为最早访问的条目。
     *               如果此方法返回 true，则此为将移除的条目。如果导致此调用的 put 或 putAll 调用之前映射为空，
     *               则该条目就是刚刚插入的条目；换句话说，如果映射只包含单个条目，则最旧的条目也是最新的条目。
     * @return 如果应该从映射移除最旧的条目，则返回 true；如果应该保留，则返回 false。
     */
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }
}