LinkedHashMap详解

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:

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