HashMap竟能与它完美结合？

文章标题：

HashMap竟能与它巧妙结合？

文章内容：

LinkedHashMap集合由HashMap继承而来，学习LinkedHashMap的关键在于对比它和HashMap之间的异同之处

特别要着重剖析两者的Entry（节点）数据结构、因数据结构差异引发的特性不同、HashMap的后置处理机制以及最少访问删除策略。

LinkedHashMap是否等同于HashMap加上LinkedList呢？

恰似这幅图所呈现的那样？

1. Entry（节点）数据结构

1.1. HashMap.Node

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    // … 构造、getKey/getValue/setValue、equals/hashCode 等 …
}

字段释义：hash为key的哈希值，key与value用于存储键值对，next是链表或树化时的链表指针。

1.2. LinkedHashMap.Entry

// 头节点
transient LinkedHashMap.Entry<K,V> head;
// 尾节点
transient LinkedHashMap.Entry<K,V> tail;
// 节点类
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);
    }
}

新增字段说明：before和after用于维护插入或访问顺序的双向链表；

链表头尾：在LinkedHashMap中，存在head和tail指针来进行维护，插入时会追加到尾部。

LinkedHashMap的数据结构正如其名称所暗示的，是Linked与HashMap的结合体，它在HashMap的基础上维护了一个双向链表。这个双向链表如同LinkedList一般，能够维持节点的插入顺序。

LinkedHashMap的数据结构是两种形态共存的结构

• 你可以忽略双向链表，将其视作普通的HashMap；
• 也可以忽略HashMap，把它当作双向链表来看待。

倘若你不想使用LinkedHashMap，但又期望维持HashMap的插入顺序，那么你可以在HashMap.put元素后，同时将该元素保存到LinkedList.add集合中，但这需要你保证集合的一致性，例如插入和删除操作。由此可见，直接运用LinkedHashMap集合会更为稳妥。

实际上，LinkedHashMap的部分源码是为了维护HashMap和双向链表的一致性，以及在操作过程中进行一些拓展。比如节点创建时在双向链表尾部插入以及HashMap的后置处理等。

1.3. 两者对比

1.4. 详细的数据结构案例

通过下面的案例图，能够清晰地看到每个节点的指向情况。

假设插入顺序为： 22、23、45、89、25、38、49、28

插入完成后的数据结构如图所示，

图中信息含义：
当前节点信息仅显示key值，next为下一个映射冲突节点；before是双链结构的上一节点，after是双链结构的下一节点；绿色虚线代表整个LinkedHashMap的双链结构的连接关系。

可以明显发现，相较于HashMap每个节点需要多维护before和after节点，LinkedHashMap需要更多的空间。

2. 节点创建和转化重写

2.1. 创建Entry节点

在链表节点创建时，通过linkNodeLast(p)方法来维护双链结构的尾部插入

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;
}

2.2. 树节点创建

红黑树节点创建时，同样通过linkNodeLast(p)方法来维护双链结构的尾部插入

TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
    TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
    linkNodeLast(p);
    return p;
}

2.3. 节点转化

对树节点转化为Entry节点和Entry节点转化树节点都进行了重写，通过transferLinks(q, t);方法来完成节点转化

Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
    LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
    LinkedHashMap.Entry<K,V> t =
        new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next);
    transferLinks(q, t);
    return t;
}

TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
    TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next);
    transferLinks(q, t);
    return t;
}

这些是多态的简单应用，HashMap引用指向不同的实例化子类，从而实现不同的功能。

3. HashMap 的后置处理（post-processing）

HashMap自身在节点插入、访问、删除后不会进行额外操作。而LinkedHashMap通过重写以下钩子方法，在插入、访问或删除时维护自己的双链表结构。

3.1. 插入后

仅在evict=true并且removeEldestEntry(first)==true时，插入后才需要移除头部节点

void afterNodeInsertion(boolean evict) { // 可能移除最老的
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

3.2. 访问后

仅在accessOrder = true时，访问后需要调整顺序；需要在LinkedHashMap的构造方法中设置accessOrder的值。

void afterNodeAccess(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e;
    // 将 p 移到双向链表尾部
    moveNodeToLast(p);
}

3.3. 删除后

只要节点被删除，LinkedHashMap集合就必须从双链表中删除对应的Entry节点

void afterNodeRemoval(Node<K,V> e) {
    // 将 e 从双向链表中摘除
    unlinkNode((LinkedHashMap.Entry<K,V>)e);
}

这三步合称为 后置处理，确保在put、get、remove等操作时链表结构的正确维护。

然而，

为何LinkedHashMap集合在插入完成后需要多执行一步删除头节点的操作？

为何访问完成后需要将访问节点移动到双链表的尾部？

4. 最少访问删除策略

👉 为何是LinkedHashMap而非HashMap：

LinkedHashMap在HashMap的基础上增添了双向链表，用于记录插入顺序（默认）或访问顺序（当accessOrder = true时）

如此便可实现：记录最近访问的节点（最近访问的放到链表尾部）；删除最久未访问的节点（链表头）

4.1. 核心方法

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false; // 默认不删除
}

这是一个钩子，在插入后缀处理中调用removeEldestEntry(first)，LinkedHashMap的源码如下：

void afterNodeInsertion(boolean evict) { // 可能移除最老的
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

你可以自行重写，制定属于自己的处理策略：

LinkedHashMap<K,V> lru = new LinkedHashMap<K,V>(16, 0.75f, true) {
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return size() > 100; // 超过100个就删除最老的
    }
};

每次put后：afterNodeInsertion会调用removeEldestEntry，若返回true，就从链表头删除最老节点

总结：

LinkedHashMap借助removeEldestEntry和accessOrder=true能够实现简单的LRU缓存。

HashMap本身不具备任何访问追踪或自动删除机制，必须由使用者自行实现。

4.2. LRU缓存例子

LRU缓存（Least Recently Used Cache，最近最少使用缓存）是一种常用的缓存淘汰策略，其核心思想是：

如果数据最近被访问过，那么未来被访问的可能性也更高；反之则淘汰。

规定固定大小为4的缓存容器，源码如下

public class LRUDemo {
    public static void main(String[] args) {
        // 指定只能缓存四个数据
        LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<>(16, 0.75f, true) {
            protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
                return size() > 4;
            }
        };

        linkedHashMap.put("A","1");
        linkedHashMap.put("B","2");
        linkedHashMap.put("C","3");
        linkedHashMap.put("D","4");
        printOrder(linkedHashMap);
        linkedHashMap.get("B"); // B被访问，移到末尾
        printOrder(linkedHashMap);
        linkedHashMap.put("E","5");   // 淘汰最老的A
        printOrder(linkedHashMap);
    }
    public static void printOrder(LinkedHashMap<String, String> linkedHashMap ) {
        System.out.print("数据结构：" + "\n[head]");
        for (Map.Entry<String, String> entry : linkedHashMap.entrySet()) {
            System.out.print(" ⇄ " + entry.getKey());
        }
        System.out.println(" ⇄ [tail]\n");
    }
}

执行输出结果如下：

数据结构：

[head] ⇄ A ⇄ B ⇄ C ⇄ D ⇄ [tail]

数据结构：

[head] ⇄ A ⇄ C ⇄ D ⇄ B ⇄ [tail]

数据结构：

[head] ⇄ C ⇄ D ⇄ B ⇄ E ⇄ [tail]

5. HashMap与LinkedHashMap区别汇总

通过上述对比，可见LinkedHashMap只是对HashMap的轻量增强：

1. 核心额外逻辑：在每次增删改查操作后，钩入双向链表进行维护；
2. 额外空间开销：每个节点多两个指针；
3. 功能收益：可提供插入顺序或访问顺序的迭代、可实现基于访问顺序的缓存淘汰（如LRU）。

6. 总结

LinkedHashMap集合继承自HashMap，重点对比LinkedHashMap和HashMap因数据结构不同产生的特性差异；为何需要LinkedHashMap这种两种形态共存的数据结构；以及通过HashMap的后置处理机制实现数据结构的功能扩展；并且对LinkedHashMap的最少访问删除策略LRU进行了简单案例演示。