LinkedHashMap 源码分析

JavaJuice约 1277 字大约 4 分钟

LinkedHashMap 源码分析

1. 概述

LinkedHashMap 是 Java 中的一个哈希表和链表实现，继承自 HashMap，提供了在遍历时保持元素插入顺序或访问顺序的特性。它具有 HashMap 的所有优点，并且维护了元素的顺序，适用于需要按插入顺序或访问顺序遍历元素的场景。

LinkedHashMap 主要由以下两部分组成：

哈希表：负责键值对的存储，提供高效的查找和插入。
双向链表：记录元素的插入顺序或访问顺序，支持按顺序遍历。

2. 主要成员变量

private transient Node<K,V> header; // 双向链表的头部节点
private transient int accessOrder;   // 是否按访问顺序排序，0：按插入顺序，1：按访问顺序

header：双向链表的头部节点，链表的结构用于维护顺序。
accessOrder：控制元素的排序方式。如果为 true，则会按照访问顺序排序；如果为 false，则按照插入顺序排序。

3. 核心数据结构

LinkedHashMap 内部使用 Node 类来表示每个条目（键值对）和它在链表中的位置：

static class Node<K,V> extends HashMap.Entry<K,V> {
    Node<K,V> before, after; // 前一个和后一个元素（双向链表）

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

继承自 HashMap.Entry 类，增加了 before 和 after 指针，用于在双向链表中链接前后节点。
每个 Node 不仅存储键值对信息，还需要维护链表的前后节点引用。

4. 重要方法分析

4.1 插入操作（`put` 方法）

put 方法用于向 LinkedHashMap 中插入键值对，以下是核心代码实现：

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

final V putVal(K key, V value, boolean onlyIfAbsent) {
    Node<K,V> e;
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    if ((e = table[i]) == null) {
        createEntry(key, value, hash, i);
    } else {
        Node<K,V> p = e;
        while (p != null) {
            K k;
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
                V oldValue = p.value;
                if (!onlyIfAbsent) {
                    p.value = value;
                }
                afterNodeAccess(p); // 访问顺序更新
                return oldValue;
            }
            p = p.next;
        }
        createEntry(key, value, hash, i); // 新增元素
    }
    afterNodeInsertion(true); // 新节点插入后更新
    return null;
}

关键步骤：

查找键值对：首先根据哈希值查找桶中是否已经存在该键。
键冲突处理：如果发生哈希冲突，遍历链表查找相同键的节点并进行更新，否则创建新的节点。
顺序更新：调用 afterNodeAccess 或 afterNodeInsertion 方法，更新访问顺序或插入顺序。

4.2 访问顺序或插入顺序更新

LinkedHashMap 提供了两种顺序更新方式，插入顺序和访问顺序。这里主要分析 afterNodeAccess 和 afterNodeInsertion 方法。

`afterNodeAccess` 方法（访问顺序更新）

void afterNodeAccess(Node<K,V> p) {
    if (accessOrder) {
        // 访问顺序更新
        moveNodeToFront(p);
    }
}

如果 accessOrder 为 true，表示启用了访问顺序排序，每次访问节点时，都会将该节点移动到链表的前端。

`afterNodeInsertion` 方法（插入顺序更新）

void afterNodeInsertion(boolean evict) {
    // 插入顺序更新，不需要做任何特别操作
}

插入顺序更新时，仅在插入新节点时进行操作（如果启用了访问顺序，则需要移动节点到链表头部）。

`moveNodeToFront` 方法

private void moveNodeToFront(Node<K,V> p) {
    // 移动节点到双向链表的头部
    p.before = header;
    p.after = header.after;
    header.after.before = p;
    header.after = p;
}

将访问过的节点移动到链表的前面，保证 LinkedHashMap 按照访问顺序维护节点。

4.3 删除操作（`remove` 方法）

public V remove(Object key) {
    Node<K,V> e;
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    if ((e = table[i]) != null) {
        Node<K,V> p = e;
        while (p != null) {
            if (p.hash == hash && (p.key == key || key.equals(p.key))) {
                V oldValue = p.value;
                removeNode(p);
                return oldValue;
            }
            p = p.next;
        }
    }
    return null;
}

删除节点时，先根据哈希值查找节点，然后通过链表遍历找到该节点并删除。
删除节点后，还需要调整链表中的前后节点关系。

`removeNode` 方法

private void removeNode(Node<K,V> p) {
    // 调整双向链表
    if (p.before != null)
        p.before.after = p.after;
    if (p.after != null)
        p.after.before = p.before;
}

删除操作主要是修改双向链表中的前后指针，确保链表结构正确。

4.4 遍历顺序

由于 LinkedHashMap 使用了双向链表，遍历操作会按照插入顺序或访问顺序进行。遍历时，每次访问或插入都会更新链表的顺序，因此可以非常方便地按照预期的顺序遍历元素。

5. 总结

插入顺序和访问顺序：
- LinkedHashMap 通过一个双向链表来维护元素的顺序。
- 通过 accessOrder 控制顺序类型，false 为插入顺序，true 为访问顺序。
性能：
- LinkedHashMap 在插入、删除和查找的性能上与 HashMap 相似，都是 O(1) 的时间复杂度。
- 双向链表的插入和删除操作是 O(1)，但遍历操作会有额外的开销。
适用场景：
LinkedHashMap 适用于那些需要按照元素插入顺序或访问顺序遍历的场景。例如，缓存实现中，可以通过访问顺序来实现 LRU（最近最少使用）缓存。