大聪明教你学Java | 深入浅出聊 LinkedHashMap

前言

🍊作者简介： 不肯过江东丶，一个来自二线城市的程序员，致力于用“猥琐”办法解决繁琐问题，让复杂的问题变得通俗易懂。
🍊支持作者： 点赞👍、关注💖、留言💌~

在开发过程中，我们经常需要使用到哈希表（HashMap）来存储键值对数据。HashMap 提供了快速的插入、查找和删除操作，但是它并不保证元素的顺序。如果我们需要按照插入顺序或者访问顺序来遍历元素，那么 LinkedHashMap 就是一个很好的选择。LinkedHashMap 是 HashMap 的一个子类，它在 HashMap 的基础上增加了双向链表的功能。这个链表可以按照插入顺序或者访问顺序连接所有的元素。通过使用LinkedHashMap，我们可以方便地实现LRU（Least Recently Used）缓存、保持元素的插入顺序等功能。今天就跟各位小伙伴深入浅出的聊聊 LinkedHashMap 。

LinkedHashMap 简介

LinkedHashMap 是 Java 提供的一个集合类，它继承自 HashMap，并在 HashMap 基础上维护一条双向链表，所以 LinkedHashMap 就拥有了以下特性：

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

LinkedHashMap 逻辑结构如下图所示👇

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

LinkedHashMap 使用

插入顺序遍历

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

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

访问顺序遍历

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

LRU 缓存

在前言中提到，通过使用LinkedHashMap，我们可以方便地实现LRU（Least Recently Used，最近最少使用）缓存，确保当存放的元素超过容器容量时，将最近最少访问的元素移除。

LRU 缓存的实现思路也非常简单，我们就是通过 LinkedHashMap 中的排序模式来实现移除最近最少使用元素的功能，即访问元素时会把该元素移动到链表尾部，那么链表首元素就是最近最少被访问的元素，我们只需要移除链表首部的元素就可以了。

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

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 个元素。从输出结果来看，由于缓存容量为 2 ，那么在添加第 3 个元素时，第 1 个元素会被删除。添加第 4 个元素时，第 2 个元素会被删除。

深入浅出聊 LinkedHashMap 源码

在看 LinkedHashMap 源码前，我们先来聊聊 LinkedHashMap 节点 Entry 的设计。我们都知道 HashMap中的桶（bucket）采用了链表和红黑树的结构来存储哈希冲突的键值对。当某个桶中的链表长度超过阈值（默认为8），且HashMap的容量大于64时，会将链表转换为红黑树。

而 LinkedHashMap 是在 HashMap 的基础上为 bucket 上的每一个节点建立一条双向链表，这就使得转为红黑树的树节点也需要具备双向链表节点的特性，即每一个树节点都需要拥有两个引用存储前驱节点和后继节点的地址。

我们通过上面的类图就可以看到 LinkedHashMap 的节点内部类 Entry 基于 HashMap 的基础上，增加 before 和 after 指针使节点具备双向链表的特性，并且 HashMap 的树节点 TreeNode 继承了具备双向链表特性的 LinkedHashMap 的 Entry。

❓ 可能看到这里，有些小伙伴会提出疑问：为什么 HashMap 的树节点 TreeNode 要通过 LinkedHashMap 获取双向链表的特性呢？为什么不直接在 Node 上实现前驱和后继指针呢？

先来看第一个问题，我们都知道 LinkedHashMap 是在 HashMap 基础上对节点增加双向指针实现双向链表的特性，所以 LinkedHashMap 内部链表转红黑树时，对应的节点会转为树节点 TreeNode，为了保证使用 LinkedHashMap 时树节点具备双向链表的特性，所以树节点 TreeNode 需要继承 LinkedHashMap 的 Entry。

再来说说第二个问题，我们直接在 HashMap 的节点 Node 上直接实现前驱和后继指针，然后 TreeNode 直接继承 Node 获取双向链表的特性为什么不行呢？其实这样做也是可以的，只不过这种做法会使得使用 HashMap 时存储键值对的节点类 Node 多了两个没有必要的引用，占用没必要的内存空间。所以为了保证 HashMap 底层的节点类 Node 没有多余的引用，又要保证 LinkedHashMap 的节点类 Entry 拥有存储链表的引用，设计者就让 LinkedHashMap 的节点 Entry 去继承 Node 并增加存储前驱后继节点的引用 before、after，让需要用到链表特性的节点去实现需要的逻辑。然后树节点 TreeNode 再通过继承 Entry 获取 before、after 两个指针。

构造方法

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

/**
 * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
 * with the specified initial capacity and load factor.
 *
 * @param  initialCapacity the initial capacity
 * @param  loadFactor      the load factor
 * @throws IllegalArgumentException if the initial capacity is negative
 *         or the load factor is nonpositive
 */
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

/**
 * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
 * with the specified initial capacity and a default load factor (0.75).
 *
 * @param  initialCapacity the initial capacity
 * @throws IllegalArgumentException if the initial capacity is negative
 */
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}

/**
 * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
 * with the default initial capacity (16) and load factor (0.75).
 */
public LinkedHashMap() {
    super();
    accessOrder = false;
}

/**
 * Constructs an insertion-ordered <tt>LinkedHashMap</tt> instance with
 * the same mappings as the specified map.  The <tt>LinkedHashMap</tt>
 * instance is created with a default load factor (0.75) and an initial
 * capacity sufficient to hold the mappings in the specified map.
 *
 * @param  m the map whose mappings are to be placed in this map
 * @throws NullPointerException if the specified map is null
 */
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}

/**
 * Constructs an empty <tt>LinkedHashMap</tt> instance with the
 * specified initial capacity, load factor and ordering mode.
 *
 * @param  initialCapacity the initial capacity
 * @param  loadFactor      the load factor
 * @param  accessOrder     the ordering mode - <tt>true</tt> for
 *         access-order, <tt>false</tt> for insertion-order
 * @throws IllegalArgumentException if the initial capacity is negative
 *         or the load factor is nonpositive
 */
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

我们上面也提到了，默认情况下 accessOrder 为 false，如果我们要让 LinkedHashMap 实现键值对按照访问顺序排序（即将最近未访问的元素排在链表首部、最近访问的元素移动到链表尾部），需要调用第 5 个构造方法将 accessOrder 设置为 true 即可。

get 方法

/**
  * Returns the value to which the specified key is mapped,
  * or {@code null} if this map contains no mapping for the key.
  *
  * <p>More formally, if this map contains a mapping from a key
  * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
  * key.equals(k))}, then this method returns {@code v}; otherwise
  * it returns {@code null}.  (There can be at most one such mapping.)
  *
  * <p>A return value of {@code null} does not <i>necessarily</i>
  * indicate that the map contains no mapping for the key; it's also
  * possible that the map explicitly maps the key to {@code null}.
  * The {@link #containsKey containsKey} operation may be used to
  * distinguish these two cases.
  */
 public V get(Object key) {
     Node<K,V> e;
     if ((e = getNode(hash(key), key)) == null)
         return null;
     //若accessOrder为true，则调用afterNodeAccess将当前元素移到链表末尾
     if (accessOrder)
         afterNodeAccess(e);
     return e.value;
 }

从源码可以看出，get 的执行步骤非常简单：

1. 调用父类即 HashMap 的 getNode 获取键值对，若为空则直接返回。
2. 判断 accessOrder 是否为 true，若为 true 则说明需要保证 LinkedHashMap 的链表访问有序性，执行步骤 3。
3. 调用 LinkedHashMap 重写的 afterNodeAccess 将当前元素添加到链表末尾。

下面我们再来看看 afterNodeAccess 方法的源码 👇

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

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

1. 如果 accessOrder 为 true 且链表尾部不为当前节点 p，我们则需要将当前节点移到链表尾部。
2. 获取当前节点 p、以及它的前驱节点 b 和后继节点 a。
3. 将当前节点 p 的后继指针设置为 null，使其和后继节点 p 断开联系。
4. 尝试将前驱节点指向后继节点，若前驱节点为空，则说明当前节点 p 就是链表首节点，故直接将后继节点 a 设置为首节点，随后我们再将 p 追加到 a 的末尾。
5. 再尝试让后继节点 a 指向前驱节点 b。
6. 上述操作让前驱节点和后继节点完成关联，并将当前节点 p 独立出来，这一步则是将当前节点 p 追加到链表末端，如果链表末端为空，则说明当前链表只有一个节点 p，所以直接让 head 指向 p 即可。
7. 上述操作已经将 p 成功到达链表末端，最后我们将 tail 指针即指向链表末端的指针指向 p 即可。

remove 方法

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

/**
 * Implements Map.remove and related methods.
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to match if matchValue, else ignored
 * @param matchValue if true only remove if value is equal
 * @param movable if false do not move other nodes while removing
 * @return the node, or null if none
 */
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        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;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

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

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 即可。

put 方法

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

1. 重写 afterNodeAccess，如果当前被插入的 key 已存在与 map 中，因为 LinkedHashMap 的插入操作会将新节点追加至链表末尾，所以对于存在的 key 则调用 afterNodeAccess 将其放到链表末端。
2. 重写了 HashMap 的 afterNodeInsertion 方法，当 removeEldestEntry 返回 true 时，会将链表首节点移除。

/**
 * Implements Map.put and related methods.
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

这里我们再看看 afterNodeInsertion 方法的源码👇

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

从源码可以看出， 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 回收。

小结

本人经验有限，有些地方可能讲的没有特别到位，如果您在阅读的时候想到了什么问题，欢迎在评论区留言，我们后续再一一探讨🙇‍

希望各位小伙伴动动自己可爱的小手，来一波点赞+关注 (✿◡‿◡) 让更多小伙伴看到这篇文章~ 蟹蟹呦(●’◡’●)

如果文章中有错误，欢迎大家留言指正；若您有更好、更独到的理解，欢迎您在留言区留下您的宝贵想法。

你在被打击时，记起你的珍贵，抵抗恶意；
你在迷茫时，坚信你的珍贵，抛开蜚语；
爱你所爱 行你所行 听从你心 无问东西