源码和注释来自JDK api 文档

一简述

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。因此，编写依赖于此异常的程序的方式是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测程序错误。

二架构图

[JDK1.8] JAVA集合 LinkedHashMap源码浅析
LinkedHashMap：继承了HashMap
主要字段

名称	注释
head	双向链表的头（最大）。
tail	双向链表的尾部（最小）。
accessOrder	此链接哈希映射的迭代排序方法：对于访问顺序为true，对于插入顺序为false。

LinkedHashMap.Entry 继承了 Node
主要字段

名称	注释
before	前一个节点
after	后一个节点

三构造方法

LinkedHashMap()

注释：使用默认初始容量（16）和加载因子（0.75）构造一个空的插入顺序LinkedHashMap实例。

    public LinkedHashMap() {
        super();
        accessOrder = false;
    }

LinkedHashMap(Map)

注释：使用与指定映射相同的映射构造一个插入有序的LinkedHashMap实例。 LinkedHashMap实例使用默认加载因子（0.75）和足以保存指定映射中的映射的初始容量创建。

    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super();
        accessOrder = false;
        putMapEntries(m, false);
    }

LinkedHashMap(int, float, boolean)

注释：使用指定的初始容量，加载因子和排序模式构造一个空的LinkedHashMap实例。

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

LinkedHashMap(int)

注释：使用指定的初始容量和默认加载因子（0.75）构造一个空的插入排序的LinkedHashMap实例。

    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }

LinkedHashMap(int, float)

注释：使用指定的初始容量和加载因子构造一个空的插入排序的LinkedHashMap实例。

    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

四核心方法

添加 newNode(int, K, V, Node)

注释：LinkedHashMap 调用 HashMap 的put方法，重写了 newNode方法，使得添加的元素安装双链表的形式记录

	// 这个方法在 HashMap中
   	public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
	final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
		··· 省略
		
		tab[i] = newNode(hash, key, value, null);
		
		··· 省略
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
	}
	
    Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<K,V>(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }

linkNodeLast(Node)

注释：链接在列表的末尾

    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }

afterNodeInsertion

注释：这个方法实现移除掉最近最少使用的节点，需要重写 removeEldestEntry

    void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }
	protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }

获取 get

注释：

    public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }

访问排序 afterNodeAccess

注释：这个方法是在创建LinkedHashMap时 accessOrder 设置为 true；调用这个方法将把访问的这个节点移动到链表的尾部，LRU算法，LRU（least recently used）最近最少使用。

    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

移除 afterNodeRemoval

注释：这个方法在HashMap中，删除后调用 afterNodeRemoval

    public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }
    final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
	··· 省略
       if (node != null && (!matchValue || (v = node.value) == value ||
                           (value != null && value.equals(v)))) {
          if (node instanceof TreeNode)
              ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
          else if (node == p)
              tab[index] = node.next;
          else
              p.next = node.next;
          ++modCount;
          --size;
          afterNodeRemoval(node);
          return node;
      }
	··· 省略
	}

afterNodeRemoval

注释：LinkedHashMap 重写了这个方法，断开链表的指定节点

    void afterNodeRemoval(Node<K,V> e) { // unlink
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.before = p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a == null)
            tail = b;
        else
            a.before = b;
    }

移除最旧的节点 removeEldestEntry

源码注释

如果此映射应删除其最旧条目，则返回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（因此此映射的行为类似于普通映射 - 永远不会删除最旧的元素）。

把LinkedHashMap 的方法重写了，节点数量达到一定程度返回true就可以移除最旧的节点，

	protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }

实例：
当容器的数量大于1024时，添加就会把head的节点移除掉

		Map<String, String> linkedHashMap = new LinkedHashMap<String, String>(16, .75f, true) {
			private static final long serialVersionUID = -3295770436308811037L;
			private static final int SIZE_MAX = 1024;
			@Override
			protected boolean removeEldestEntry(java.util.Map.Entry<String, String> eldest) {
				return size() > SIZE_MAX;
			}
		};
		
		for (int i = 0; i < 1200; i++) {
			linkedHashMap.put("" + i, "a_" + i);
		}
		
		System.out.println(linkedHashMap);

迭代器 Iterator

架构图：
[JDK1.8] JAVA集合 LinkedHashMap源码浅析

LinkedHashIterator

    // Iterators

    abstract class LinkedHashIterator {
        LinkedHashMap.Entry<K,V> next;		// 下一个节点的指针
        LinkedHashMap.Entry<K,V> current;	// 当前节点的指针
        int expectedModCount;
		// 构造方法， 初始化next节点
        LinkedHashIterator() {
            next = head;
            expectedModCount = modCount;
            current = null;
        }
		// 是否有下一个节点
        public final boolean hasNext() {
            return next != null;
        }
		// 获取下一个节点
        final LinkedHashMap.Entry<K,V> nextNode() {
            LinkedHashMap.Entry<K,V> e = next;
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
            current = e;
            next = e.after;
            return e;
        }
		// 移除最近一次调用nextNode 返回的节点
        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;
        }
    }

LinkedKeyIterator

LinkedValueIterator

LinkedEntryIterator

    final class LinkedKeyIterator extends LinkedHashIterator
        implements Iterator<K> {
        public final K next() { return nextNode().getKey(); }
    }

    final class LinkedValueIterator extends LinkedHashIterator
        implements Iterator<V> {
        public final V next() { return nextNode().value; }
    }

    final class LinkedEntryIterator extends LinkedHashIterator
        implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
    }

[JDK1.8] JAVA集合 LinkedHashMap源码浅析

文章目录

一 简述

二 架构图

三 构造方法