LinkedHashMap详解

基于JDK8
LinkedHashMap相比于HashMap最显著的一个特性就是维持了插入的顺序。

1、LinkedHashMap的继承体系

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

可以看到LinkedHashMap继承了HashMap,所以HashMap能做的事情LinkedHashMap都能做。

还记得HashMap详解这篇文章里面提到的两个方法吗？
afterNodeAccess和afterNodeInsertion 在 LinkedHashMap中就有对应的实现。下面会详细说到。

2、LinkedHashMap的特性介绍和代码示例

LinkedHashMap 是 HashMap 的子类，与 HashMap 类似，它也基于哈希表来存储键值对。但是，LinkedHashMap 维护了一个双向链表来记录插入顺序或者访问顺序，因此具备一些特有的特性和功能。

双向链表在 LinkedList详解这篇文章中有介绍。

LinkedHashMap 中使用双向链表维护顺序的图示：
绿色连线表示 双向链表的 pre和next指针。

①、特性

插入顺序：默认情况下，LinkedHashMap 按照键值对的插入顺序来维护顺序。
插入顺序代码示例

public static void main(String[] args) {
        LinkedHashMap<String, String> map = new LinkedHashMap<>();

        // ========== 演示插入顺序 ===============
        map.put("a","1");
        map.put("b","2");
        map.put("c","3");
        map.put("d","4");

        System.out.println("插入顺序遍历:");
        for (Map.Entry<String, String> entry : map.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
        // 插入顺序遍历:
        //a: 1
        //b: 2
        //c: 3
        //d: 4
    }

访问顺序：可以通过构造函数设置 accessOrder 参数为 true，使其按照访问顺序来维护顺序。

访问顺序代码示例：

public static void main(String[] args) {
        Map<String, String> map = new LinkedHashMap<>(16, 0.75f, true);

        // ========== 插入元素 ===============
        map.put("a","1");
        map.put("b","2");
        map.put("c","3");
        map.put("d","4");

        // ========== 访问其中一些元素 ===============
        map.get("c");
        map.get("a");

        System.out.println("访问顺序遍历:");
        for (Map.Entry<String, String> entry : map.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
        // ========= 最新一次访问的排在最后
        // 访问顺序遍历:
        //b: 2
        //d: 4
        //c: 3
        //a: 1
    }

②、适用场景

**需要有序遍历的场景：**当需要按插入顺序或访问顺序遍历键值对时，LinkedHashMap 是一个很好的选择。

**缓存：**由于 LinkedHashMap 可以按照访问顺序来维护键值对的顺序，因此非常适合用来实现 LRU（Least Recently Used，最近最少使用）缓存。

使用LinkedHashMap 实现最简单的 LRU缓存

import java.util.LinkedHashMap;
import java.util.Map;

public class TestA {
    public static void main(String[] args) {
        // 创建一个容量为 3 的 LRUCache
        LRUCache<Integer, String> cache = new LRUCache<>(3);

        // 添加一些键值对到缓存中
        cache.put(1, "one");
        cache.put(2, "two");
        cache.put(3, "three");
        // 打印当前缓存内容
        System.out.println("Cache: " + cache); // Cache: {1=one, 2=two, 3=three}

        // 访问键 1 的值，使其成为最近访问的条目
        cache.get(1);
        System.out.println(cache); // {2=two, 3=three, 1=one}
        // 添加新的键值对 4 -> "four"  由于超过缓存容量 所以会删除 最近最久没使用的数据
        cache.put(4, "four");
        // 打印当前缓存内容，观察最老的条目是否被移除   （2被删除）
        System.out.println("访问1 添加 4 后的缓存: " + cache); // 访问1 添加 4 后的缓存: {3=three, 1=one, 4=four}

        // 访问键 3 的值，使其成为最近访问的条目
        cache.get(3);
        System.out.println(cache); // {1=one, 4=four, 3=three}
        // 添加新的键值对 5 -> "five"   由于超过缓存容量 所以会删除 最近最久没使用的数据
        cache.put(5, "five");
        // 打印当前缓存内容，观察最老的条目是否被移除    （1被删除）
        System.out.println("访问3 添加5 后的缓存: " + cache);  // 访问3 添加5 后的缓存: {4=four, 3=three, 5=five}
    }
}

// LRUCache 类，继承 LinkedHashMap 实现最近最少使用 (LRU) 缓存
class LRUCache<K, V> extends LinkedHashMap<K, V> {

    // 缓存的最大容量
    private final int capacity;

    // 构造函数，接受缓存的最大容量作为参数
    public LRUCache(int capacity) {
        // 调用父类的构造函数
        // initialCapacity: 初始容量，设置为传入的 capacity
        // loadFactor: 负载因子，设置为默认值 0.75F 
        // accessOrder: 设置为 true，表示按照访问顺序排序
        super(capacity, 0.75F, true);
        this.capacity = capacity; // 初始化缓存容量
    }

    // 重写 LinkedHashMap 的 removeEldestEntry 方法
    // 当添加一个新的键值对时，此方法会被调用，以判断是否需要删除最老的条目
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // 当缓存元素个数大于我们设置的容量时  删除 最近最少使用的缓存元素
        return size() > capacity;
    }
}

3、LinkedHashMap的构造函数

• ①、空参构造

public LinkedHashMap() {
        super(); // 调用父类(HashMap)的空参构造
        accessOrder = false; // 不按照访问顺序排序
    }

• ②、有参构造1
  接收 initialCapacity 初始容量 loadFactor 负载因子

public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor); // 设置自定义的哈希表容量 和负载因子
        accessOrder = false; // 不按照访问顺序排序
    }

• ③、有参构造2
  接收 initialCapacity: 初始容量 loadFactor: 负载因子 accessOrder: 是否按照访问顺序排序
  上面实现的LRUCache就是用的这个构造方法。

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

• ④、有参构造3
  接收一个Map的实现。

public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super(); // 调用父类(HashMap)的空参构造
        accessOrder = false; // 不按照访问顺序排序
        putMapEntries(m, false); // 调用HashMap的 putMapEntries方法
    }

上面只列举了4个构造函数，还有一个直接收initialCapacity参数的就不列举了。

4、LinkedHashMap是如何存储元素的，底层数据结构是什么？

在HashMap详解的文章中 我们知道 HashMap的数组存储的是 Node<K,V>。

而我们看LinkedHashMap的put方法是直接调用的父类HashMap的put方法。
上面已经介绍过了，LinkedHashMap使用双向链表维护每一个元素的插入顺序。
那么LinkedHashMap是如何实现双向链表的，LinkedHashMap的底层数据结构是什么？
下面就来探讨这两个问题。
在看LinkedHashMap源码之前，我们可以把HashMap和LinkedHashMap 类比ArrayList和LinkedList。
先猜测下LinkedHashMap里面一定也有类似LinkedList的Node节点，并且有pre和next指针实现双向链接。

LinkedHashMap的属性注释

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{
   // 指向双向链表的头节点，即最早插入的键值对
   transient LinkedHashMap.Entry<K,V> head;
   
   // 指向双向链表的尾节点，即最后插入或访问的键值对
   transient LinkedHashMap.Entry<K,V> tail;
   
   // 标识链表是否按访问顺序维护
   // 如果为 true，则每次访问（get 或 put）某个键值对时，该键值对将被移到链表尾部
   final boolean accessOrder;
}

可以看到LinkedHashMap是通过 LinkedHashMap.Entry<K,V>这个内部类 来保存链表节点的。

LinkedHashMap的静态内部类Entry<K,V>

// LinkedHashMap 的静态内部类 Entry，继承自 HashMap.Node
// 此类在 LinkedHashMap 中用于维护双向链表，以记录键值对的插入顺序或访问顺序
static class Entry<K,V> extends HashMap.Node<K,V> {
    // 指向链表中前一个节点的引用
    Entry<K, V> before;

    // 指向链表中后一个节点的引用
    Entry<K, V> after;

    // 构造函数，用于创建一个新的 Entry 节点
    // hash: 键的哈希值
    // key: 键
    // value: 值
    // next: 指向哈希表中下一个节点的引用（用于处理哈希冲突）
    Entry(int hash, K key, V value, Node<K, V> next) {
        // 调用父类 HashMap.Node 的构造函数，初始化 hash, key, value 和 next
        super(hash, key, value, next);
    }
}

可以看到不仅LinkedHashMap继承了HashMap，就连LinkedHashMap保存的元素 Entry都是继承HashMap的Node Entry<K,V> extends HashMap.Node<K,V> ，LinkedHashMap.Entry在HashMap.Node的基础上 添加了两个属性before和after用来保存链表的前一个和后一个引用。

可以看下内部类的继承图：

图中可以看到，还有个TreeNode(红黑树的节点)是继承Entry的。

我在HashMap详解的文章中并没有去看 TreeNode的源码，因为实现红黑树数据库结构的源码比较多，也比较难理解。要想写好注释 比较费力。

从TreeNode的继承结构引发一个关于设计类继承关系的思考？

     为什么在TreeNode和Node之间 还要搞个Entry来实现链表的功能，不如直接在Node节点加上before和after属性实现双向链表功能得了，这样还省事就不用再写一个Entry夹在中间了是不是。

     这样做当然是可以的，只不过这样设计会使得HashMap本身不需要链表结构的每个元素都有before和after属性,当元素存储很多的是时候对于空间来说是浪费的。 如果再设计个Entry夹在中间，LinkedHashMap需要双向链表结构就用Entry，但是TreeNode有时候需要双向链表(比如LinkedHashMap需要转红黑树的时候)，有时候不需要双向链表(比如HashMap需要转红黑树的时候)。这个时候的TreeNode不管需不需要双向链表结构，都是已经继承Entry的了，所以会多出before和after属性。
     在HashMap需要转红黑树的情况下继承Entry实际上是一种空间浪费，但是别忘了概率， hash 值如果足够随机，则在 hash 表内按泊松分布，在负载因子 0.75 的情况下，长度超过8的链表出现概率是0.00000006。这么低的概率正常情况下注定红黑树节点在哈希表中不会有很多。

     所以这么分析下来 搞个Entry夹在中间是个非常不错的设计。 既节省了HashMap的Node节点的空间占用，Entry又复用了Node的代码，TreeNode又复用了Entry的代码，实在是妙呀！

5、LinkedHashMap的put方法

是的你没有看错，LinkedHashMap并没有重写HashMap的put方法，直接调用的就是HashMap的put方法。

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

那LinkedHashMap在put元素的时候又是如何把每个元素都链在一块形成双向链表的呢？

LinkedHashMap实际上并不需要整体重写put方法，只需要重写newNode方法即可。
HashMap的newNode方法

Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
        return new Node<>(hash, key, value, next);
    }

LinkedHashMap在重写的newNode方法中新建LinkedHashMap.Entry<K,V>元素。然后把元素链接到链表的尾部。

newNode方法

@Override
Node<K, V> newNode(int hash, K key, V value, Node<K, V> e) {
    // 创建一个新的 LinkedHashMap.Entry 节点，并初始化其哈希值、键、值和下一个节点指针
    LinkedHashMap.Entry<K, V> p = new LinkedHashMap.Entry<>(hash, key, value, e);
    // 将新节点插入到双向链表的尾部
    linkNodeLast(p);
    // 返回新创建的节点
    return p;
}

linkNodeLast方法

private void linkNodeLast(LinkedHashMap.Entry<K, V> p) {
    // 当前的尾节点
    LinkedHashMap.Entry<K, V> last = tail;
    // 将新节点设置为尾节点
    tail = p;
    if (last == null) {
        // 如果链表为空，新节点即为头节点
        head = p;
    } else {
        // 否则，将当前尾节点的 after 指针指向新节点
        p.before = last;
        last.after = p;
    }
}

afterNodeAccess方法

还记得 HashMap详解这篇文章中提过这个方法吗
LinkedHashMap就重写了 HashMap给的扩展方法。

afterNodeAccess 方法在访问节点后调用，用于将被访问的节点移动到双向链表的尾部。
这对于按访问顺序维护的 LinkedHashMap 特别重要。

@Override
void afterNodeAccess(Node<K, V> e) { // move node to last
    LinkedHashMap.Entry<K, V> last;
    // 检查是否按访问顺序维护链表，并且被访问的节点不是当前的尾节点
    if (accessOrder && (last = tail) != e) {
        // 将节点 e 转换为 LinkedHashMap.Entry 类型
        LinkedHashMap.Entry<K, V> p = (LinkedHashMap.Entry<K, V>) e;
        // 获取节点 p 的前一个和后一个节点
        LinkedHashMap.Entry<K, V> b = p.before, a = p.after;
        // 将 p 的 after 指针置为 null，表示它将成为新的尾节点
        p.after = null;
        // 更新前一个节点和后一个节点的指针
        if (b == null)
            head = a; // 如果 p 没有前一个节点，则它是头节点，更新头节点为 a
        else
            b.after = a; // 否则，将前一个节点的 after 指针指向 a
        if (a != null)
            a.before = b; // 如果 p 有后一个节点，将后一个节点的 before 指针指向 b
        else
            last = b; // 如果 p 是当前的尾节点，更新 last 为 b
        // 如果 last 为空，表示链表为空，将 p 设置为头节点
        if (last == null)
            head = p;
        else {
            // 否则，将 p 插入到链表尾部
            p.before = last;
            last.after = p;
        }
        // 更新尾节点为 p
        tail = p;
        // 增加修改计数，以反映结构性修改
        ++modCount;
    }
}

afterNodeInsertion方法

afterNodeInsertion 方法在插入节点后调用，用于检查是否需要移除最老的节点（头节点）。
这对于按插入顺序维护的 LinkedHashMap 特别重要。

@Override
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);
    }
}

看了上面的代码注释就会明白，afterNodeAccess和afterNodeInsertion方法的主要目的都是为了实现按照访问顺序处理元素的位置。

6、LinkedHashMap的get方法

LinkedHashMap重写了 HashMap的get方法，主要新增了按访问顺序维护链表的功能。

@Override
public V get(Object key) {
    Node<K, V> e;
    // 调用 HashMap 的 getNode 方法，使用键的哈希值查找节点
    if ((e = getNode(hash(key), key)) == null)
        // 如果节点不存在，返回 null
        return null;
    // 如果 accessOrder 为 true，表示按访问顺序维护链表
    if (accessOrder)
        // 调用 afterNodeAccess 方法，将访问的节点移动到链表尾部
        afterNodeAccess(e);
    // 返回节点的值
    return e.value;
}

afterNodeAccess在上面已经详细注释了。

7、LinkedHashMap的remove方法

LinkedHashMap的remove方法在设计上和put方法有相似之处，LinkedHashMap并没有重写HashMap的remove方法，而是重写了afterNodeRemoval方法，在删除节点时维护双向链表。

void afterNodeRemoval(Node<K, V> e) { // unlink
    // 将节点 e 转换为 LinkedHashMap.Entry 类型
    LinkedHashMap.Entry<K, V> p = (LinkedHashMap.Entry<K, V>) e;
    // 获取节点 p 的前一个和后一个节点
    LinkedHashMap.Entry<K, V> b = p.before, a = p.after;
    // 将节点 p 的 before 和 after 指针置为 null
    p.before = p.after = null;
    // 更新前一个节点和后一个节点的指针
    if (b == null)
        head = a; // 如果 p 没有前一个节点，则它是头节点，更新头节点为 a
    else
        b.after = a; // 否则，将前一个节点的 after 指针指向 a
    if (a == null)
        tail = b; // 如果 p 没有后一个节点，则它是尾节点，更新尾节点为 b
    else
        a.before = b; // 否则，将后一个节点的 before 指针指向 b
}

最后再整体看下HashMap中留给LinkedHashMap扩展的几个方法：

// Callbacks to allow LinkedHashMap post-actions

	// 在访问节点（即调用 get 方法）后调用。
	// 主要用途：LinkedHashMap 重写此方法，用于在访问一个节点后将其移动到双向链表的尾部，以维护访问顺序
    void afterNodeAccess(Node<K,V> p) { }

	// 在插入新节点后调用  
	// 主要用途：LinkedHashMap 重写此方法，用于在插入新节点后检查并移除最老的节点，以维护固定大小的缓存或按照插入顺序迭代。
    void afterNodeInsertion(boolean evict) { }

	// 在删除节点后调用
	// 主要用途：LinkedHashMap 重写此方法，用于在删除节点后调整双向链表的指针，确保链表的完整性。
    void afterNodeRemoval(Node<K,V> p) { }

其中afterNodeInsertion方法的参数 boolean evict,该参数指示当前的操作是否在创建模式下。如果为 false，表示哈希表处于创建模式；如果为 true，表示哈希表处于正常操作模式。此参数通常在初始化哈希表时使用，以避免在创建模式中触发删除操作。

evict 参数为 false 的情况：
在哈希表初始化时，通过 putMapEntries 方法调用 putVal，设置 evict 为 false。 HashMap的readObject反序列化方法也会调用 putVal，设置 evict 为 false。

evict 参数为 true 的情况：
正常操作（非创建模式）下，插入或更新元素时，evict 为 true，允许执行淘汰策略。

8、LinkedHashMap的迭代器

LinkedHashMap的迭代器可以对比 HashMap详解 这篇文章的 HashMap的迭代器来学习。

    二者本质的区别是由 LinkedHashMap 维护了双向链表而决定的。 LinkedHashMap的迭代器不会像HashMap的迭代器那样遍历全部的数组节点，而是通过双向链表的头结点，以及after指针一个一个往下遍历，这种方式就少了HashMap那种遍历全部数组节点的过程，直接通过after指针就能遍历全部的元素,这种方式比 HashMap 的迭代更为直接高效。

abstract class LinkedHashIterator {
        // 下一个要返回的节点
        LinkedHashMap.Entry<K,V> next;        
        // 当前的节点
        LinkedHashMap.Entry<K,V> current;     
        // 用于快速失败的期望修改计数
        int expectedModCount;  

        // 构造方法
        LinkedHashIterator() {
            // 初始化下一个节点为链表的头节点
            next = head;
            // 初始化期望的修改计数，等于当前的修改计数
            expectedModCount = modCount;
            // 初始化当前节点为null
            current = null;
        }

        // 判断是否有下一个元素
        public final boolean hasNext() {
            return next != null;
        }

        // 获取下一个节点
        final LinkedHashMap.Entry<K,V> nextNode() {
            // e用于存储当前的下一个节点
            LinkedHashMap.Entry<K,V> e = next;
            // 如果哈希表的修改计数与期望的修改计数不同，抛出并发修改异常
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            // 如果下一个节点为空，抛出没有元素异常
            if (e == null)
                throw new NoSuchElementException();
            // 将当前节点设为下一个节点
            current = e;
            // 更新下一个节点为当前节点的下一个节点（after）
            next = e.after;
            // 返回当前的节点
            return e;
        }
    }

9、LinkedHashMap的一些常见问题

LinkedHashMap 和 HashMap 的区别及适用场景

数据结构对比

特性	HashMap	LinkedHashMap
数据结构	数组 + 链表（红黑树）	数组 + 链表（红黑树）+ 双向链表
顺序保证	无	按插入顺序或访问顺序
空间开销	较低	较高（需要额外维护链表指针）

插入和迭代性能

操作	HashMap	LinkedHashMap
插入	O(1) 平均，O(n) 最坏（哈希冲突）	O(1) 平均，O(n) 最坏（哈希冲突）
删除	O(1) 平均，O(n) 最坏(未转红黑树的情况)	O(1) 平均，O(n) 最坏(未转红黑树的情况)
查找	O(1) 平均，O(n) 最坏(未转红黑树的情况)	O(1) 平均，O(n) 最坏(未转红黑树的情况)
迭代	与数据插入顺序无关，但是要循环数组	按插入顺序或访问顺序，直接遍历链表，性能稍好

适用场景

场景	HashMap	LinkedHashMap
快速查找和插入	✔	✔
需要保证元素顺序	✖	✔
LRU 缓存实现	✖	✔
内存使用较少的场景	✔	✖

• HashMap:

  • 适用于对元素顺序没有要求的场景。
  • 高效的查找、插入和删除操作。
  • 内存占用较少。

• LinkedHashMap:

  • 需要维护元素顺序的场景。
  • 实现 LRU（最近最少使用）缓存。
  • 适合需要顺序遍历的场景，且可以按插入顺序或访问顺序遍历。
  • 较高的内存开销。