LinkedHashMap 是 Java 集合框架中的一个重要类，它继承自 HashMap，并且维护了元素的插入顺序或访问顺序。LinkedHashMap 基于 HashMap 和双向链表的组合实现，在保持哈希映射高效性的同时，还提供了有序的特性。

1. LinkedHashMap 的基本特性

• 继承自 HashMap：LinkedHashMap 继承了 HashMap 的所有特性，包括存储结构、哈希函数等。同时通过维护一个双向链表来保证顺序。
• 有序性：通过链表维护键值对的插入顺序或访问顺序。默认情况下，LinkedHashMap 保留插入顺序，也可以通过设置访问顺序来实现 LRU 缓存。
• 适用场景：LinkedHashMap 适用于既需要快速查找，又需要保留元素顺序的场景，例如实现缓存。

2. 构造函数

LinkedHashMap 提供了多个构造函数，主要如下：

• 默认构造函数：

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

  • 通过调用 HashMap 的构造函数，创建默认容量为 16，负载因子为 0.75 的哈希表，并设置插入顺序。
• 指定初始容量和负载因子的构造函数：

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

  • 指定初始容量和负载因子，仍然设置插入顺序。
• 访问顺序构造函数：

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

  • accessOrder 为 true 时，表示按访问顺序排序。

3. 数据结构

LinkedHashMap 通过继承 HashMap，并增加了双向链表来维护顺序。以下是关键数据结构的源码：

• Entry 结构：

  static class Entry<K,V> extends HashMap.Node<K,V> {
      Entry<K,V> before, after;
      Entry(int hash, K key, V value, Node<K,V> next) {
          super(hash, key, value, next);
      }
  }
  

  • LinkedHashMap.Entry 继承自 HashMap.Node，新增了 before 和 after 两个字段，分别指向前一个节点和后一个节点。
  • 这些引用实现了一个双向链表，用于记录键值对的插入顺序或访问顺序。

4. 插入元素 (put() 方法)

LinkedHashMap 的 put() 方法继承自 HashMap，但在插入时会将新节点链接到链表中，以下是关键的代码逻辑：

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

void afterNodeInsertion(boolean evict) {
    LinkedHashMap.Entry<K,V> last;
    if (evict && (last = head) != null) {
        removeNode(hash(last.key), last.key, null, false, false);
    }
}

• afterNodeInsertion()：在节点插入后，该方法会将新节点添加到链表尾部，从而维护插入顺序。
• removeNode()：如果需要移除节点，会调用 removeNode() 方法进行删除处理。

5. 访问元素 (get() 方法)

当 LinkedHashMap 设置为按访问顺序排序时，get() 方法会影响元素在链表中的顺序：

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

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

• afterNodeAccess()：在访问某个节点后，如果按访问顺序排序，会将该节点移到链表的尾部。
• 链表操作：通过调整 before 和 after 引用，保证链表顺序更新，体现访问顺序的特性。

6. 删除元素 (remove() 方法)

LinkedHashMap 的 remove() 方法与 HashMap 类似，但需要额外维护链表中的顺序：

void afterNodeRemoval(Node<K,V> e) {
    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;
}

• afterNodeRemoval()：在节点被移除后，更新链表中前后节点的引用，保证链表的完整性。

7.业务使用场景

• LRU（Least Recently Used）缓存
  LinkedHashMap 可以通过构造函数的 accessOrder 参数设置为按访问顺序排序，使其可以轻松实现 LRU 缓存策略。 在缓存中，当存储的数据超过指定容量时，最久未使用的数据应当被淘汰，LinkedHashMap 的 accessOrder 机制能够帮助实现这一功能。
  通过设置 accessOrder 为 true，并重写 removeEldestEntry() 方法，可以实现自动移除最不常用的元素。例如：

LinkedHashMap<Integer, String> lruCache = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {
        return size() > 100; // 当缓存大小超过 100 时移除最老的元素
    }
};

• 日志记录
  当需要记录一系列操作日志，并保持记录的顺序以便后续分析时，可以使用 LinkedHashMap 来保存这些记录。
• 配置文件加载
  例如在加载配置文件并将其映射到键值对中时，保持加载的顺序有助于管理和调试，可以使用 LinkedHashMap 来存储这些配置项。

8. 总结

LinkedHashMap 通过继承 HashMap 并引入双向链表，实现了键值对的有序存储。它既保留了 HashMap 的高效查找特性，又能够按照插入或访问顺序来维护元素的顺序，适用于需要顺序访问的场景。LinkedHashMap 的实现中，链表的维护逻辑贯穿于插入、访问和删除操作，这使得它在有序性上有着更好的表现。