LinkedHashMap详解
# LinkedHashMap详解
基于JDK8 LinkedHashMap相比于HashMap最显著的一个特性就是维持了插入的顺序，也可以设置其按照访问顺序排序。
# 1、LinkedHashMap的继承体系
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
可以看到LinkedHashMap继承了HashMap,所以HashMap能做的事情LinkedHashMap都能做。
还记得HashMap详解 (opens new window)这篇文章里面提到的两个方法吗？
afterNodeAccess和afterNodeInsertion 在 LinkedHashMap中就有对应的实现。下面会详细说到。
# 2、LinkedHashMap的特性介绍和代码示例
LinkedHashMap 是 HashMap 的子类，与 HashMap 类似，它也基于哈希表来存储键值对。但是，LinkedHashMap 维护了一个双向链表来记录插入顺序或者访问顺序，因此具备一些特有的特性和功能。
双向链表在 LinkedList详解 (opens new window)这篇文章中有介绍。
LinkedHashMap 中使用双向链表维护顺序的图示： 绿色连线表示 双向链表的 pre和next指针。
# ①、特性
插入顺序：默认情况下，LinkedHashMap 按照键值对的插入顺序来维护顺序。 插入顺序代码示例
public static void main(String[] args) {
LinkedHashMap<String, String> map = new LinkedHashMap<>();
// ========== 演示插入顺序 ===============
map.put("a","1");
map.put("b","2");
map.put("c","3");
map.put("d","4");
System.out.println("插入顺序遍历:");
for (Map.Entry<String, String> entry : map.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
// 插入顺序遍历:
//a: 1
//b: 2
//c: 3
//d: 4
}
访问顺序：可以通过构造函数设置 accessOrder 参数为 true，使其按照访问顺序来维护顺序。
访问顺序代码示例：
public static void main(String[] args) {
Map<String, String> map = new LinkedHashMap<>(16, 0.75f, true);
// ========== 插入元素 ===============
map.put("a","1");
map.put("b","2");
map.put("c","3");
map.put("d","4");
// ========== 访问其中一些元素 ===============
map.get("c");
map.get("a");
System.out.println("访问顺序遍历:");
for (Map.Entry<String, String> entry : map.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
// ========= 最新一次访问的排在最后
// 访问顺序遍历:
//b: 2
//d: 4
//c: 3
//a: 1
}
# ②、适用场景
**需要有序遍历的场景：**当需要按插入顺序或访问顺序遍历键值对时，LinkedHashMap 是一个很好的选择。
**缓存：**由于 LinkedHashMap 可以按照访问顺序来维护键值对的顺序，因此非常适合用来实现 LRU（Least Recently Used，最近最少使用）缓存。
# 使用LinkedHashMap 实现最简单的 LRU缓存
import java.util.LinkedHashMap;
import java.util.Map;
public class TestA {
public static void main(String[] args) {
// 创建一个容量为 3 的 LRUCache
LRUCache<Integer, String> cache = new LRUCache<>(3);
// 添加一些键值对到缓存中
cache.put(1, "one");
cache.put(2, "two");
cache.put(3, "three");
// 打印当前缓存内容
System.out.println("Cache: " + cache); // Cache: {1=one, 2=two, 3=three}
// 访问键 1 的值，使其成为最近访问的条目
cache.get(1);
System.out.println(cache); // {2=two, 3=three, 1=one}
// 添加新的键值对 4 -> "four" 由于超过缓存容量 所以会删除 最近最久没使用的数据
cache.put(4, "four");
// 打印当前缓存内容，观察最老的条目是否被移除 （2被删除）
System.out.println("访问1 添加 4 后的缓存: " + cache); // 访问1 添加 4 后的缓存: {3=three, 1=one, 4=four}
// 访问键 3 的值，使其成为最近访问的条目
cache.get(3);
System.out.println(cache); // {1=one, 4=four, 3=three}
// 添加新的键值对 5 -> "five" 由于超过缓存容量 所以会删除 最近最久没使用的数据
cache.put(5, "five");
// 打印当前缓存内容，观察最老的条目是否被移除 （1被删除）
System.out.println("访问3 添加5 后的缓存: " + cache); // 访问3 添加5 后的缓存: {4=four, 3=three, 5=five}
}
}
// LRUCache 类，继承 LinkedHashMap 实现最近最少使用 (LRU) 缓存
class LRUCache<K, V> extends LinkedHashMap<K, V> {
// 缓存的最大容量
private final int capacity;
// 构造函数，接受缓存的最大容量作为参数
public LRUCache(int capacity) {
// 调用父类的构造函数
// initialCapacity: 初始容量，设置为传入的 capacity
// loadFactor: 负载因子，设置为默认值 0.75F
// accessOrder: 设置为 true，表示按照访问顺序排序
super(capacity, 0.75F, true);
this.capacity = capacity; // 初始化缓存容量
}
// 重写 LinkedHashMap 的 removeEldestEntry 方法
// 当添加一个新的键值对时，此方法会被调用，以判断是否需要删除最老的条目
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
// 当缓存元素个数大于我们设置的容量时 删除 最近最少使用的缓存元素
return size() > capacity;
}
}
# 3、LinkedHashMap的构造函数
- ①、空参构造
public LinkedHashMap() {
super(); // 调用父类(HashMap)的空参构造
accessOrder = false; // 不按照访问顺序排序
}
- ②、有参构造1 接收 initialCapacity 初始容量 loadFactor 负载因子
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor); // 设置自定义的哈希表容量 和负载因子
accessOrder = false; // 不按照访问顺序排序
}
- ③、有参构造2
接收 initialCapacity: 初始容量 loadFactor: 负载因子 accessOrder: 是否按照访问顺序排序
上面实现的LRUCache就是用的这个构造方法。
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
- ④、有参构造3 接收一个Map的实现。
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super(); // 调用父类(HashMap)的空参构造
accessOrder = false; // 不按照访问顺序排序
putMapEntries(m, false); // 调用HashMap的 putMapEntries方法
}
上面只列举了4个构造函数，还有一个直接收initialCapacity参数的就不列举了。
# 4、LinkedHashMap是如何存储元素的，底层数据结构是什么？
在HashMap详解的文章中 我们知道 HashMap的数组存储的是 Node<K,V>。
而我们看LinkedHashMap的put方法是直接调用的父类HashMap的put方法。
上面已经介绍过了，LinkedHashMap使用双向链表维护每一个元素的插入顺序。
那么LinkedHashMap是如何实现双向链表的，LinkedHashMap的底层数据结构是什么？
下面就来探讨这两个问题。
在看LinkedHashMap源码之前，我们可以把HashMap和LinkedHashMap 类比ArrayList和LinkedList。
先猜测下LinkedHashMap里面一定也有类似LinkedList的Node节点，并且有pre和next指针实现双向链接。
# LinkedHashMap的属性注释
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{
// 指向双向链表的头节点，即最早插入的键值对
transient LinkedHashMap.Entry<K,V> head;
// 指向双向链表的尾节点，即最后插入或访问的键值对
transient LinkedHashMap.Entry<K,V> tail;
// 标识链表是否按访问顺序维护
// 如果为 true，则每次访问（get 或 put）某个键值对时，该键值对将被移到链表尾部
final boolean accessOrder;
}
可以看到LinkedHashMap是通过 LinkedHashMap.Entry<K,V>这个内部类 来保存链表节点的。
# LinkedHashMap的静态内部类Entry<K,V>
// LinkedHashMap 的静态内部类 Entry，继承自 HashMap.Node
// 此类在 LinkedHashMap 中用于维护双向链表，以记录键值对的插入顺序或访问顺序
static class Entry<K,V> extends HashMap.Node<K,V> {
// 指向链表中前一个节点的引用
Entry<K, V> before;
// 指向链表中后一个节点的引用
Entry<K, V> after;
// 构造函数，用于创建一个新的 Entry 节点
// hash: 键的哈希值
// key: 键
// value: 值
// next: 指向哈希表中下一个节点的引用（用于处理哈希冲突）
Entry(int hash, K key, V value, Node<K, V> next) {
// 调用父类 HashMap.Node 的构造函数，初始化 hash, key, value 和 next
super(hash, key, value, next);
}
}
可以看到不仅LinkedHashMap继承了HashMap，就连LinkedHashMap保存的元素 Entry都是继承HashMap的Node Entry<K,V> extends HashMap.Node<K,V> ，LinkedHashMap.Entry在HashMap.Node的基础上 添加了两个属性before和after用来保存链表的前一个和后一个引用。
可以看下内部类的继承图：
图中可以看到，还有个TreeNode(红黑树的节点)是继承Entry的。
我在HashMap详解的文章中并没有去看 TreeNode的源码，因为实现红黑树数据库结构的源码比较多，也比较难理解。要想写好注释 比较费力。
# 从TreeNode的继承结构引发一个关于设计类继承关系的思考？
为什么在TreeNode和Node之间 还要搞个Entry来实现链表的功能，不如直接在Node节点加上before和after属性实现双向链表功能得了，这样还省事就不用再写一个Entry夹在中间了是不是。
这样做当然是可以的，只不过这样设计会使得HashMap本身不需要链表结构的每个元素都有before和after属性,当元素存储很多的是时候对于空间来说是浪费的。 如果再设计个Entry夹在中间，LinkedHashMap需要双向链表结构就用Entry，但是TreeNode有时候需要双向链表(比如LinkedHashMap需要转红黑树的时候)，有时候不需要双向链表(比如HashMap需要转红黑树的时候)。这个时候的TreeNode不管需不需要双向链表结构，都是已经继承Entry的了，所以会多出before和after属性。 在HashMap需要转红黑树的情况下继承Entry实际上是一种空间浪费，但是别忘了概率， hash 值如果足够随机，则在 hash 表内按泊松分布，在负载因子 0.75 的情况下，长度超过8的链表出现概率是0.00000006。这么低的概率正常情况下注定红黑树节点在哈希表中不会有很多。
所以这么分析下来 搞个Entry夹在中间是个非常不错的设计。 既节省了HashMap的Node节点的空间占用，Entry又复用了Node的代码，TreeNode又复用了Entry的代码，实在是妙呀！
# 5、LinkedHashMap的put方法
是的你没有看错，LinkedHashMap并没有重写HashMap的put方法，直接调用的就是HashMap的put方法。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
那LinkedHashMap在put元素的时候又是如何把每个元素都链在一块形成双向链表的呢？
LinkedHashMap实际上并不需要整体重写put方法，只需要重写newNode方法即可。
HashMap的newNode方法
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
LinkedHashMap在重写的newNode方法中新建LinkedHashMap.Entry<K,V>元素。然后把元素链接到链表的尾部。
# newNode方法
@Override
Node<K, V> newNode(int hash, K key, V value, Node<K, V> e) {
// 创建一个新的 LinkedHashMap.Entry 节点，并初始化其哈希值、键、值和下一个节点指针
LinkedHashMap.Entry<K, V> p = new LinkedHashMap.Entry<>(hash, key, value, e);
// 将新节点插入到双向链表的尾部
linkNodeLast(p);
// 返回新创建的节点
return p;
}
# linkNodeLast方法
private void linkNodeLast(LinkedHashMap.Entry<K, V> p) {
// 当前的尾节点
LinkedHashMap.Entry<K, V> last = tail;
// 将新节点设置为尾节点
tail = p;
if (last == null) {
// 如果链表为空，新节点即为头节点
head = p;
} else {
// 否则，将当前尾节点的 after 指针指向新节点
p.before = last;
last.after = p;
}
}
# afterNodeAccess方法
还记得 HashMap详解 (opens new window)这篇文章中提过这个方法吗 LinkedHashMap就重写了 HashMap给的扩展方法。
afterNodeAccess 方法在访问节点后调用，用于将被访问的节点移动到双向链表的尾部。
这对于按访问顺序维护的 LinkedHashMap 特别重要。
@Override
void afterNodeAccess(Node<K, V> e) { // move node to last
LinkedHashMap.Entry<K, V> last;
// 检查是否按访问顺序维护链表，并且被访问的节点不是当前的尾节点
if (accessOrder && (last = tail) != e) {
// 将节点 e 转换为 LinkedHashMap.Entry 类型
LinkedHashMap.Entry<K, V> p = (LinkedHashMap.Entry<K, V>) e;
// 获取节点 p 的前一个和后一个节点
LinkedHashMap.Entry<K, V> b = p.before, a = p.after;
// 将 p 的 after 指针置为 null，表示它将成为新的尾节点
p.after = null;
// 更新前一个节点和后一个节点的指针
if (b == null)
head = a; // 如果 p 没有前一个节点，则它是头节点，更新头节点为 a
else
b.after = a; // 否则，将前一个节点的 after 指针指向 a
if (a != null)
a.before = b; // 如果 p 有后一个节点，将后一个节点的 before 指针指向 b
else
last = b; // 如果 p 是当前的尾节点，更新 last 为 b
// 如果 last 为空，表示链表为空，将 p 设置为头节点
if (last == null)
head = p;
else {
// 否则，将 p 插入到链表尾部
p.before = last;
last.after = p;
}
// 更新尾节点为 p
tail = p;
// 增加修改计数，以反映结构性修改
++modCount;
}
}
# afterNodeInsertion方法
afterNodeInsertion 方法在插入节点后调用，用于检查是否需要移除最老的节点（头节点）。
这对于按插入顺序维护的 LinkedHashMap 特别重要。
@Override
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);
}
}
看了上面的代码注释就会明白，afterNodeAccess和afterNodeInsertion方法的主要目的都是为了实现按照访问顺序处理元素的位置。
# 6、LinkedHashMap的get方法
LinkedHashMap重写了 HashMap的get方法，主要新增了按访问顺序维护链表的功能。
@Override
public V get(Object key) {
Node<K, V> e;
// 调用 HashMap 的 getNode 方法，使用键的哈希值查找节点
if ((e = getNode(hash(key), key)) == null)
// 如果节点不存在，返回 null
return null;
// 如果 accessOrder 为 true，表示按访问顺序维护链表
if (accessOrder)
// 调用 afterNodeAccess 方法，将访问的节点移动到链表尾部
afterNodeAccess(e);
// 返回节点的值
return e.value;
}
afterNodeAccess在上面已经详细注释了。
# 7、LinkedHashMap的remove方法
LinkedHashMap的remove方法在设计上和put方法有相似之处，LinkedHashMap并没有重写HashMap的remove方法，而是重写了afterNodeRemoval方法，在删除节点时维护双向链表。
void afterNodeRemoval(Node<K, V> e) { // unlink
// 将节点 e 转换为 LinkedHashMap.Entry 类型
LinkedHashMap.Entry<K, V> p = (LinkedHashMap.Entry<K, V>) e;
// 获取节点 p 的前一个和后一个节点
LinkedHashMap.Entry<K, V> b = p.before, a = p.after;
// 将节点 p 的 before 和 after 指针置为 null
p.before = p.after = null;
// 更新前一个节点和后一个节点的指针
if (b == null)
head = a; // 如果 p 没有前一个节点，则它是头节点，更新头节点为 a
else
b.after = a; // 否则，将前一个节点的 after 指针指向 a
if (a == null)
tail = b; // 如果 p 没有后一个节点，则它是尾节点，更新尾节点为 b
else
a.before = b; // 否则，将后一个节点的 before 指针指向 b
}
最后再整体看下HashMap中留给LinkedHashMap扩展的几个方法：
// Callbacks to allow LinkedHashMap post-actions
// 在访问节点（即调用 get 方法）后调用。
// 主要用途：LinkedHashMap 重写此方法，用于在访问一个节点后将其移动到双向链表的尾部，以维护访问顺序
void afterNodeAccess(Node<K,V> p) { }
// 在插入新节点后调用
// 主要用途：LinkedHashMap 重写此方法，用于在插入新节点后检查并移除最老的节点，以维护固定大小的缓存或按照插入顺序迭代。
void afterNodeInsertion(boolean evict) { }
// 在删除节点后调用
// 主要用途：LinkedHashMap 重写此方法，用于在删除节点后调整双向链表的指针，确保链表的完整性。
void afterNodeRemoval(Node<K,V> p) { }
其中afterNodeInsertion方法的参数 boolean evict,该参数指示当前的操作是否在创建模式下。如果为 false，表示哈希表处于创建模式；如果为 true，表示哈希表处于正常操作模式。此参数通常在初始化哈希表时使用，以避免在创建模式中触发删除操作。
evict 参数为 false 的情况：
在哈希表初始化时，通过 putMapEntries 方法调用 putVal，设置 evict 为 false。 HashMap的readObject反序列化方法也会调用 putVal，设置 evict 为 false。
evict 参数为 true 的情况：
正常操作（非创建模式）下，插入或更新元素时，evict 为 true，允许执行淘汰策略。
# 8、LinkedHashMap的迭代器
LinkedHashMap的迭代器可以对比 HashMap详解 (opens new window) 这篇文章的 HashMap的迭代器来学习。
二者本质的区别是由 LinkedHashMap 维护了双向链表而决定的。 LinkedHashMap的迭代器不会像HashMap的迭代器那样遍历全部的数组节点，而是通过双向链表的头结点，以及after指针一个一个往下遍历，这种方式就少了HashMap那种遍历全部数组节点的过程，直接通过after指针就能遍历全部的元素,这种方式比 HashMap 的迭代更为直接高效。
abstract class LinkedHashIterator {
// 下一个要返回的节点
LinkedHashMap.Entry<K,V> next;
// 当前的节点
LinkedHashMap.Entry<K,V> current;
// 用于快速失败的期望修改计数
int expectedModCount;
// 构造方法
LinkedHashIterator() {
// 初始化下一个节点为链表的头节点
next = head;
// 初始化期望的修改计数，等于当前的修改计数
expectedModCount = modCount;
// 初始化当前节点为null
current = null;
}
// 判断是否有下一个元素
public final boolean hasNext() {
return next != null;
}
// 获取下一个节点
final LinkedHashMap.Entry<K,V> nextNode() {
// e用于存储当前的下一个节点
LinkedHashMap.Entry<K,V> e = next;
// 如果哈希表的修改计数与期望的修改计数不同，抛出并发修改异常
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
// 如果下一个节点为空，抛出没有元素异常
if (e == null)
throw new NoSuchElementException();
// 将当前节点设为下一个节点
current = e;
// 更新下一个节点为当前节点的下一个节点（after）
next = e.after;
// 返回当前的节点
return e;
}
}
# 9、LinkedHashMap的一些常见问题
# LinkedHashMap 和 HashMap 的区别及适用场景
# 数据结构对比
| 特性 | HashMap | LinkedHashMap |
|---|---|---|
| 数据结构 | 数组 + 链表（红黑树） | 数组 + 链表（红黑树）+ 双向链表 |
| 顺序保证 | 无 | 按插入顺序或访问顺序 |
| 空间开销 | 较低 | 较高（需要额外维护链表指针） |
# 插入和迭代性能
| 操作 | HashMap | LinkedHashMap |
|---|---|---|
| 插入 | O(1) 平均，O(n) 最坏（哈希冲突） | O(1) 平均，O(n) 最坏（哈希冲突） |
| 删除 | O(1) 平均，O(n) 最坏(未转红黑树的情况) | O(1) 平均，O(n) 最坏(未转红黑树的情况) |
| 查找 | O(1) 平均，O(n) 最坏(未转红黑树的情况) | O(1) 平均，O(n) 最坏(未转红黑树的情况) |
| 迭代 | 与数据插入顺序无关，但是要循环数组 | 按插入顺序或访问顺序，直接遍历链表，性能稍好 |
# 适用场景
| 场景 | HashMap | LinkedHashMap |
|---|---|---|
| 快速查找和插入 | ✔ | ✔ |
| 需要保证元素顺序 | ✖ | ✔ |
| LRU 缓存实现 | ✖ | ✔ |
| 内存使用较少的场景 | ✔ | ✖ |
HashMap:
- 适用于对元素顺序没有要求的场景。
- 高效的查找、插入和删除操作。
- 内存占用较少。
LinkedHashMap:
- 需要维护元素顺序的场景。
- 实现 LRU（最近最少使用）缓存。
- 适合需要顺序遍历的场景，且可以按插入顺序或访问顺序遍历。
- 较高的内存开销。