您的位置: 首页  >  文章  >  LinkedHashMap源码分析

LinkedHashMap源码分析

分类: 文章 • 2024-05-07 21:34:51

1. 概述：

  1. 众所周知，HashMap 提供的访问，是无序的。而在一些业务场景下，我们希望能够提供有序访问的 HashMap 。那么此时，我们就有两种选择：
  • TreeMap ：按照 key 进行排序。
  • LinkedHashMap ：按照 key 的插入和访问的顺序。
  1. LinkedHashMap ，在 HashMap 的基础之上，提供了顺序访问的特性。而这里的顺序，包括两种：
  • 按照 key-value 的插入顺序进行访问。
  • 按照 key-value 的访问顺序进行访问。通过这个特性，我们实现基于 LRU 算法的缓存。
  1. 实际上，LinkedHashMap 可以理解成是 LinkedList + HashMap 的组合。为什么这么说？接下来我将一次不死 并且超神！Let’s go

2. 类图

LinkedHashMap源码分析
LinkedHashMap 实现的接口、继承的类，只有两个：

  • 实现 java.util.Map 接口。
  • 继承 java.util.HashMap 类。

3. 属性

  • head + tail 属性，形成 LinkedHashMap 的双向链表。而访问的顺序，就是 head => tail 的过程。
  • accessOrder属性，决定了 LinkedHashMap 的顺序。也就是说:
    • true 时，当 Entry 节点被访问时，放置到链表的结尾，被 tail 指向，按照访问顺序进行访问，同样的也是实现LRU的关键。
    • false 时，当 Entry 节点被添加时，放置到链表的结尾，被 tail 指向。如果插入的 key 对应的 Entry 节点已经存在，也会被放到结尾，按照插入顺序进行访问。
  • 总结来说，就是如下的形式，主体是HashMap，访问或者是插入的顺序使用双向链表进行记录：
    LinkedHashMap源码分析
    LinkedHashMap源码分析
    然后看看 LinkedHashMap 实现了自定义的节点 Entry （支持指向前后节点的 Node 子类）
    LinkedHashMap源码分析
  • before 属性，指向前一个节点。after 属性，指向后一个节点。
  • 通过 before + after 属性，我们就可以形成一个以 Entry 为节点的链表。
    LinkedHashMap源码分析

4. 构造方法

  • LinkedHashMap 一共有 5 个构造方法，其中四个和 HashMap 相同，只是多初始化 accessOrder = false 。所以，默认使用插入顺序进行访问 要是没有看过的可以跳转到HashMap源码分析【4.构造方法】查看
  • 另外一个 LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) 构造方法，允许自定义 accessOrder 属性。代码如下：
    LinkedHashMap源码分析

5. 创建节点

在插入 key-value 键值对时，例如说 put(K key, V value) 方法，如果不存在对应的节点，则会调用 newNode(int hash, K key, V value, Node<K,V> e) 方法，创建节点。
因为 LinkedHashMap 自定义了 Entry 节点，所以必然需要重写该方法 代码如下：
LinkedHashMap源码分析

  • <1> 处，创建 Entry 节点。虽然此处传入 e 作为 Entry.next 属性，指向下一个节点。但是实际上，put(K key, V value) 方法中，传入的 e = null 。
  • <2> 处 linkNodeLast(LinkedHashMap.Entry<K,V> p) 方法，添加到结尾。代码如下：
    LinkedHashMap源码分析

6. 节点操作回调

在 HashMap 的读取、添加、删除时，分别提供了

  • afterNodeAccess(Node<K,V> e)
  • afterNodeInsertion(boolean evict)
  • afterNodeRemoval(Node<K,V> e)
    回调方法，LinkedHashMap 能通过它们实现自定义拓展逻辑

1. afterNodeAccess(Node<K,V> e)

在 accessOrder 属性为 true 时，当 Entry 节点被访问时，放置到链表的结尾，被 tail 指向。所以 afterNodeAccess(Node<K,V> e) 方法的代码如下
LinkedHashMap源码分析

  • 这个方法一共是分为两步：
    1. 将p从链表中移除
    2. 将p添加到链表的尾部
  • HashMap 提供的 getOrDefault(Object key, V defaultValue)和get(Object key) 方法，并未调用 afterNodeAccess(Node<K,V> e) 方法，这在按照读取顺序访问显然不行，所以 LinkedHashMap 重写这两方法的代码，如下：
    LinkedHashMap源码分析

2. afterNodeInsertion(boolean evict)

afterNodeInsertion(boolean evict) 方法 这个方法也是实现LRU缓存的关键，代码如下：
LinkedHashMap源码分析

  • <1> removeEldestEntry(Map.Entry<K,V> eldest) 方法，判断是否移除最老节点：
    • 默认情况下，都不移除最老的节点。LRU缓存中进行此方法的重写，判断 LinkedHashMap 是否超过缓存最大大小。如果是，则移除最老的节点。
  • <2> 处，如果满足条件，则调用 removeNode(...) 方法，移除最老的节点
    下面是LUR 缓存的简单实现：
    LinkedHashMap源码分析

3. afterNodeRemoval(Node<K,V> e)

在节点被移除时，LinkedHashMap 需要将节点也从链表中移除，所以重写 afterNodeRemoval(Node<K,V> e) 方法，实现该逻辑。代码如下：
LinkedHashMap源码分析

7. 转换成数组

LinkedHashMap 需要满足按顺序访问，所以需要重写 HashMap 提供的好多方法，keysToArray(T[] a) 方法，转换出 key 数组顺序返回，valuesToArray(T[] a) 方法，转换出 value 数组顺序返回。代码如下：
LinkedHashMap源码分析

8. 清空

clear() 方法，清空 LinkedHashMap 。代码如下：
LinkedHashMap源码分析

总结：

LinkedHashMap 做一个简单的小结：

  • LinkedHashMap 是 HashMap 的子类，增加了顺序访问的特性。
    • 【默认】当 accessOrder = false 时，按照 key-value 的插入顺序进行访问。
    • 当 accessOrder = true 时，按照 key-value 的读取顺序进行访问。
  • LinkedHashMap 的顺序特性，通过内部的双向链表实现，所以我们把它看成是 LinkedList + LinkedHashMap 的组合。
  • LinkedHashMap 通过重写 HashMap 提供的回调方法，从而实现其对顺序的特性的处理。同时，因为 LinkedHashMap 的顺序特性，需要重写 keysToArray(T[] a) 等遍历相关的方法。
  • LinkedHashMap 可以方便实现 LRU 算法的缓存，

相关推荐