1. 简介

LinkedHashMap 是 Java 提供的一个集合类，它继承自 HashMap，并在 HashMap 基础上维护一条双向链表，使得具备如下特性:

  • 支持遍历时会按照插入顺序有序进行迭代。
  • 支持按照元素访问顺序排序,适用于封装 LRU 缓存工具。
  • 因为内部使用双向链表维护各个节点，所以遍历时的效率和元素个数成正比，相较于和容量成正比的 HashMap 来说，迭代效率会高很多。

LinkedHashMap 逻辑结构如下图所示，它是在 HashMap 基础上在各个节点之间维护一条双向链表，使得原本散列在不同 bucket 上的节点、链表、红黑树有序关联起来。

LinkedHashMap 逻辑结构

2. 使用示例

2.1 插入顺序遍历

插入顺序遍历如下所示，我们按照顺序往 LinkedHashMap 添加元素然后进行遍历。

1
2
3
4
5
6
7
8
9
HashMap < String, String > map = new LinkedHashMap < > ();
map.put("a", "2");
map.put("g", "3");
map.put("r", "1");
map.put("e", "23");

for (Map.Entry < String, String > entry: map.entrySet()) {
    System.out.println(entry.getKey() + ":" + entry.getValue());
}

输出：

1
2
3
4
a:2
g:3
r:1
e:23

可以看出，LinkedHashMap 的迭代顺序是和插入顺序一致的,这一点是 HashMap 所不具备的。

2.2 访问顺序遍历

LinkedHashMap 定义了排序模式 accessOrder(boolean 类型，默认为 false)，访问顺序则为 true，插入顺序则为 false。为了实现访问顺序遍历，我们可以使用传入 accessOrder 属性的 LinkedHashMap 构造方法，并将 accessOrder 设置为 true，表示其具备访问有序性。

1
2
3
4
5
6
7
8
9
10
11
12
13
LinkedHashMap<Integer, String> map = new LinkedHashMap<>(16, 0.75f, true);
map.put(1, "one");
map.put(2, "two");
map.put(3, "three");
map.put(4, "four");
map.put(5, "five");
//访问元素2,该元素会被移动至链表末端
map.get(2);
//访问元素3,该元素会被移动至链表末端
map.get(3);
for (Map.Entry<Integer, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " : " + entry.getValue());
}

输出：

1
2
3
4
5
1 : one
4 : four
5 : five
2 : two
3 : three

可以看出，LinkedHashMap 的迭代顺序是和访问顺序一致的。

2.3 LRU缓存

从上一个我们可以了解到通过 LinkedHashMap 我们可以封装一个简易版的 LRU（Least Recently Used，最近最少使用） 缓存，确保当存放的元素超过容器容量时，将最近最少访问的元素移除。
img
具体实现思路如下：

  • 继承 LinkedHashMap;
  • 构造方法中指定 accessOrder 为 true ，这样在访问元素时就会把该元素移动到链表尾部，链表首元素就是最近最少被访问的元素；
  • 重写removeEldestEntry 方法，该方法会返回一个 boolean 值，告知 LinkedHashMap 是否需要移除链表首元素（缓存容量有限）。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    public class LRUCache<K, V> extends LinkedHashMap<K, V> {
        private final int capacity;

        public LRUCache(int capacity) {
            super(capacity, 0.75f, true);
            this.capacity = capacity;
        }

        /**
         * 判断size超过容量时返回true，告知LinkedHashMap移除最老的缓存项(即链表的第一个元素)
         */
        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > capacity;
        }
    }
    测试代码如下，笔者初始化缓存容量为 2，然后按照次序先后添加 4 个元素。
    1
    2
    3
    4
    5
    6
    7
    8
    LRUCache < Integer, String > cache = new LRUCache < > (2);
    cache.put(1, "one");
    cache.put(2, "two");
    cache.put(3, "three");
    cache.put(4, "four");
    for (int i = 0; i < 4; i++) {
        System.out.println(cache.get(i));
    }
    输出：
    1
    2
    3
    4
    null
    null
    three
    four
    从输出结果来看，由于缓存容量为 2 ，因此，添加第 3 个元素时，第 1 个元素会被删除。添加第 4 个元素时，第 2 个元素会被删除。

3. 源码解析

3.1 Node的设计

  • LinkedHashMap 的节点内部类 Entry 基于 HashMap 的基础上，增加 before 和 after 指针使节点具备双向链表的特性。
  • HashMap 的树节点 TreeNode 继承了具备双向链表特性的 LinkedHashMap 的 Entry。

LinkedHashMap 和 HashMap 之间的关系

为什么 HashMap 的树节点 TreeNode 要通过 LinkedHashMap 获取双向链表的特性呢?

LinkedHashMap 是在 HashMap 基础上对节点增加双向指针实现双向链表的特性,所以 LinkedHashMap 内部链表转红黑树时，对应的节点会转为树节点 TreeNode,为了保证使用 LinkedHashMap 时树节点具备双向链表的特性，所以树节点 TreeNode 需要继承 LinkedHashMap 的 Entry。

为什么不直接在 Node 上实现前驱和后继指针呢?

在 HashMap 的节点 Node 上直接实现前驱和后继指针,然后 TreeNode 直接继承 Node 获取双向链表的特性为什么不行呢？其实这样做也是可以的。只不过这种做法会使得使用 HashMap 时存储键值对的节点类 Node 多了两个没有必要的引用，占用没必要的内存空间。

所以，为了保证 HashMap 底层的节点类 Node 没有多余的引用，又要保证 LinkedHashMap 的节点类 Entry 拥有存储链表的引用，设计者就让 LinkedHashMap 的节点 Entry 去继承 Node 并增加存储前驱后继节点的引用 before、after，让需要用到链表特性的节点去实现需要的逻辑。然后树节点 TreeNode 再通过继承 Entry 获取 before、after 两个指针。

1
2
3
4
5
6
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);
    }
}

但是这样做，不也使得使用 HashMap 时的 TreeNode 多了两个没有必要的引用吗?这不也是一种空间的浪费吗？

1
2
3
4
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
  //略

}

对于这个问题,引用作者的一段注释，作者们认为在良好的 hashCode 算法时，HashMap 转红黑树的概率不大。就算转为红黑树变为树节点，也可能会因为移除或者扩容将 TreeNode 变为 Node，所以 TreeNode 的使用概率不算很大，对于这一点资源空间的浪费是可以接受的。

3.2 构造方法

LinkedHashMap 构造方法有 4 个实现也比较简单，直接调用父类即 HashMap 的构造方法完成初始化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public LinkedHashMap() {
    super();
    accessOrder = false;
}

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

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 为 false，如果我们要让 LinkedHashMap 实现键值对按照访问顺序排序(即将最近未访问的元素排在链表首部、最近访问的元素移动到链表尾部)，需要调用第 4 个构造方法将 accessOrder 设置为 true。

3.3 get方法

LinkedHashMap 构造方法有 4 个实现也比较简单，直接调用父类即 HashMap 的构造方法完成初始化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public LinkedHashMap() {
    super();
    accessOrder = false;
}

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

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 为 false，如果我们要让 LinkedHashMap 实现键值对按照访问顺序排序(即将最近未访问的元素排在链表首部、最近访问的元素移动到链表尾部)，需要调用第 4 个构造方法将 accessOrder 设置为 true。

LinkedHashMap 移动元素 13 到链表尾部

3.4 remove方法的后置操作–afterNodeRemoval

LinkedHashMap 并没有对 remove 方法进行重写，而是直接继承 HashMap 的 remove 方法，为了保证键值对移除后双向链表中的节点也会同步被移除，LinkedHashMap 重写了 HashMap 的空实现方法 afterNodeRemoval。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        //略
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                //HashMap的removeNode完成元素移除后会调用afterNodeRemoval进行移除后置操作
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }
//空实现
void afterNodeRemoval(Node<K,V> p) { }

可以看到从 HashMap 继承来的 remove 方法内部调用的 removeNode 方法将节点从 bucket 删除后，调用了 afterNodeRemoval。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void afterNodeRemoval(Node<K,V> e) { // unlink

    //获取当前节点p、以及e的前驱节点b和后继节点a
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    //将p的前驱和后继指针都设置为null，使其和前驱、后继节点断开联系
        p.before = p.after = null;

    //如果前驱节点为空，则说明当前节点p是链表首节点，让head指针指向后继节点a即可
        if (b == null)
            head = a;
        else
        //如果前驱节点b不为空，则让b直接指向后继节点a
            b.after = a;

    //如果后继节点为空，则说明当前节点p在链表末端，所以直接让tail指针指向前驱节点a即可
        if (a == null)
            tail = b;
        else
        //反之后继节点的前驱指针直接指向前驱节点
            a.before = b;
}

从源码可以看出， afterNodeRemoval 方法的整体操作就是让当前节点 p 和前驱节点、后继节点断开联系，等待 gc 回收，整体步骤为:

  1. 获取当前节点 p、以及 e 的前驱节点 b 和后继节点 a。
  2. 让当前节点 p 和其前驱、后继节点断开联系。
  3. 尝试让前驱节点 b 指向后继节点 a，若 b 为空则说明当前节点 p 在链表首部，我们直接将 head 指向后继节点 a 即可。
  4. 尝试让后继节点 a 指向前驱节点 b，若 a 为空则说明当前节点 p 在链表末端，所以直接让 tail 指针指向前驱节点 a 即可。

可以结合这张图理解，展示了 key 为 13 的元素被删除，也就是从链表中移除了这个元素。

LinkedHashMap 删除元素 13

3.5 put方法后置操作–afterNodeInsertion

LinkedHashMap 并没有实现插入方法，而是直接继承 HashMap 的所有插入方法交由用户使用，但为了维护双向链表访问的有序性，它做了这样两件事:

  1. 重写 afterNodeAccess(上文提到过),如果当前被插入的 key 已存在与 map 中，因为 LinkedHashMap 的插入操作会将新节点追加至链表末尾，所以对于存在的 key 则调用 afterNodeAccess 将其放到链表末端。
  2. 重写了 HashMap 的 afterNodeInsertion 方法，当 removeEldestEntry 返回 true 时，会将链表首节点移除。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
          //略
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                 //如果当前的key在map中存在，则调用afterNodeAccess
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
         //调用插入后置方法，该方法被LinkedHashMap重写
        afterNodeInsertion(evict);
        return null;
    }

上述步骤的源码上文已经解释过了，所以这里我们着重了解一下 afterNodeInsertion 的工作流程，假设我们的重写了 removeEldestEntry，当链表 size 超过 capacity 时，就返回 true。

1
2
3
4
5
6
/**
 * 判断size超过容量时返回true，告知LinkedHashMap移除最老的缓存项(即链表的第一个元素)
 */
protected boolean removeEldestEntry(Map.Entry < K, V > eldest) {
    return size() > capacity;
}

以下图为例，假设笔者最后新插入了一个不存在的节点 19,假设 capacity 为 4，所以 removeEldestEntry 返回 true，我们要将链表首节点移除。

LinkedHashMap 中插入新元素 19

移除的步骤很简单，查看链表首节点是否存在，若存在则断开首节点和后继节点的关系，并让首节点指针指向下一节点，所以 head 指针指向了 12，节点 10 成为没有任何引用指向的空对象，等待 GC。

LinkedHashMap 中插入新元素 19

1
2
3
4
5
6
7
8
9
10
void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        //如果evict为true且队首元素不为空以及removeEldestEntry返回true，则说明我们需要最老的元素(即在链表首部的元素)移除。
        if (evict && (first = head) != null && removeEldestEntry(first)) {
          //获取链表首部的键值对的key
            K key = first.key;
            //调用removeNode将元素从HashMap的bucket中移除，并和LinkedHashMap的双向链表断开，等待gc回收
            removeNode(hash(key), key, null, false, true);
        }
}

从源码可以看出， afterNodeInsertion 方法完成了下面这些操作:

  1. 判断 eldest 是否为 true，只有为 true 才能说明可能需要将最年长的键值对(即链表首部的元素)进行移除，具体是否具体要进行移除，还得确定链表是否为空((first = head) != null)，以及 removeEldestEntry 方法是否返回 true，只有这两个方法返回 true 才能确定当前链表不为空，且链表需要进行移除操作了。
  2. 获取链表第一个元素的 key。
  3. 调用 HashMap 的 removeNode 方法，该方法我们上文提到过，它会将节点从 HashMap 的 bucket 中移除，并且 LinkedHashMap 还重写了 removeNode 中的 afterNodeRemoval 方法，所以这一步将通过调用 removeNode 将元素从 HashMap 的 bucket 中移除，并和 LinkedHashMap 的双向链表断开，等待 gc 回收。

4. 常见面试题

4.1 什么是LinkedHashMap？

LinkedHashMap 是 Java 集合框架中 HashMap 的一个子类，它继承了 HashMap 的所有属性和方法，并且在 HashMap 的基础重写了 afterNodeRemoval、afterNodeInsertion、afterNodeAccess 方法。使之拥有顺序插入和访问有序的特性。

4.2 LinkedHashMap如何按照插入顺序迭代？

LinkedHashMap 按照插入顺序迭代元素是它的默认行为。LinkedHashMap 内部维护了一个双向链表，用于记录元素的插入顺序。因此，当使用迭代器迭代元素时，元素的顺序与它们最初插入的顺序相同。

4.3 LinkedHashMap如何按照访问顺序迭代？

LinkedHashMap 可以通过构造函数中的 accessOrder 参数指定按照访问顺序迭代元素。当 accessOrder 为 true 时，每次访问一个元素时，该元素会被移动到链表的末尾，因此下次访问该元素时，它就会成为链表中的最后一个元素，从而实现按照访问顺序迭代元素。

4.4 LinkedHashMap如何实现LRU缓存？

将 accessOrder 设置为 true 并重写 removeEldestEntry 方法当链表大小超过容量时返回 true，使得每次访问一个元素时，该元素会被移动到链表的末尾。一旦插入操作让 removeEldestEntry 返回 true 时，视为缓存已满，LinkedHashMap 就会将链表首元素移除，由此我们就能实现一个 LRU 缓存。

4.5 LinkedHashMap和HashMap有什么区别？

LinkedHashMap 和 HashMap 都是 Java 集合框架中的 Map 接口的实现类。它们的最大区别在于迭代元素的顺序。HashMap 迭代元素的顺序是不确定的，而 LinkedHashMap 提供了按照插入顺序或访问顺序迭代元素的功能。此外，LinkedHashMap 内部维护了一个双向链表，用于记录元素的插入顺序或访问顺序，而 HashMap 则没有这个链表。因此，LinkedHashMap 的插入性能可能会比 HashMap 略低，但它提供了更多的功能并且迭代效率相较于 HashMap 更加高效。

快来参与讨论吧~

博客近期分类标签归档
项目软件开发札记人工智能Staller
社交友链
更多关于本站
本站由 卡卡龙 使用 Stellar 1.27.0 主题创建

本站访问量 次. 本文阅读量 次.

Stellar Copyright Licenses Hexo 备案 描述文字 描述文字