一、LinkedHashMap 简介
LinkedHashMap 是 Java 提供的一个集合类，它继承自 HashMap，并在 HashMap 基础上维护一条双向链表，使得具备如下特性:
-
支持遍历时会按照插入顺序有序进行迭代。
-
支持按照元素访问顺序排序,适用于封装 LRU 缓存工具。
-
因为内部使用双向链表维护各个节点，所以遍历时的效率和元素个数成正比，相较于和容量成正比的 HashMap 来说，迭代效率会高很多。
LinkedHashMap 逻辑结构如下图所示，它是在 HashMap 基础上在各个节点之间维护一条双向链表，使得原本散列在不同 bucket 上的节点、链表、红黑树有序关联起来。
LinkedHashMap 逻辑结构
二、LinkedHashMap 使用示例
1、插入顺序遍历
如下所示，我们按照顺序往 LinkedHashMap 添加元素然后进行遍历。
public static void main(String[] args) {
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());
}
}输出：
a:2
g:3
r:1
e:23可以看出，LinkedHashMap 的迭代顺序是和插入顺序一致的,这一点是 HashMap 所不具备的。
2、访问顺序遍历
LinkedHashMap 定义了排序模式 accessOrder(boolean 类型，默认为 false)，访问顺序则为 true，插入顺序则为 false。
为了实现访问顺序遍历，我们可以使用传入 accessOrder 属性的 LinkedHashMap 构造方法，并将 accessOrder 设置为 true，表示其具备访问有序性。
public static void main(String[] args) {
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 : one
4 : four
5 : five
2 : two
3 : three可以看出，LinkedHashMap 的迭代顺序是和访问顺序一致的。
3、LRU 缓存
从上一个我们可以了解到通过 LinkedHashMap 我们可以封装一个简易版的 LRU（Least Recently Used，最近最少使用） 缓存，确保当存放的元素超过容器容量时，将最近最少访问的元素移除。
具体实现思路如下：
-
继承
LinkedHashMap; -
构造方法中指定
accessOrder为 true ，这样在访问元素时就会把该元素移动到链表尾部，链表首元素就是最近最少被访问的元素； -
重写
removeEldestEntry方法，该方法会返回一个 boolean 值，告知LinkedHashMap是否需要移除链表首元素（缓存容量有限）。
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;
}
}测试代码如下，笔者初始化缓存容量为 3，然后按照次序先后添加 4 个元素。
public static void main(String[] args) {
LRUCache<Integer, String> cache = new LRUCache<>(3);
cache.put(1, "one");
cache.put(2, "two");
cache.put(3, "three");
cache.put(4, "four");
cache.put(5, "five");
for (int i = 1; i <= 5; i++) {
System.out.println(cache.get(i));
}
}输出：
null
null
three
four
five从输出结果来看，由于缓存容量为 3 ，因此，添加第 4 个元素时，第 1 个元素会被删除。添加第 5 个元素时，第 2 个元素会被删除。
三、LinkedHashMap 源码解析
1、Node 的设计
在正式讨论 LinkedHashMap 前，我们先来聊聊 LinkedHashMap 节点 Entry 的设计,我们都知道 HashMap 的 bucket 上的因为冲突转为链表的节点会在符合以下两个条件时会将链表转为红黑树:
-
链表上的节点个数达到树化的阈值 7，即TREEIFY_THRESHOLD - 1。 -
bucket 的容量达到最小的树化容量即
MIN_TREEIFY_CAPACITY。
链表上的节点个数达到树化的阈值是 8 而非 7。因为源码的判断是从链表初始元素开始遍历，下标是从 0 开始的，所以判断条件设置为 8-1=7，其实是迭代到尾部元素时再判断整个链表长度大于等于 8 才进行树化操作。
而 LinkedHashMap 是在 HashMap 的基础上为 bucket 上的每一个节点建立一条双向链表，这就使得转为红黑树的树节点也需要具备双向链表节点的特性，即每一个树节点都需要拥有两个引用存储前驱节点和后继节点的地址,所以对于树节点类 TreeNode 的设计就是一个比较棘手的问题。
对此我们不妨来看看两者之间节点类的类图，可以看到:
-
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两个指针。
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 多了两个没有必要的引用吗?这不也是一种空间的浪费吗？
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
//略
}对于这个问题,引用作者的一段注释，作者们认为在良好的 hashCode 算法时，HashMap 转红黑树的概率不大。就算转为红黑树变为树节点，也可能会因为移除或者扩容将 TreeNode 变为 Node，所以 TreeNode 的使用概率不算很大，对于这一点资源空间的浪费是可以接受的。
2、get方法
get 方法是 LinkedHashMap 增删改查操作中唯一一个重写的方法， accessOrder 为 true 的情况下， 它会在元素查询完成之后，将当前访问的元素移到链表的末尾。
public V get(Object key) {
Node < K, V > e;
//获取key的键值对,若为空直接返回
if ((e = getNode(hash(key), key)) == null)
return null;
//若accessOrder为true，则调用afterNodeAccess将当前元素移到链表末尾
if (accessOrder)
afterNodeAccess(e);
//返回键值对的值
return e.value;
}从源码可以看出，get 的执行步骤非常简单:
-
调用父类即
HashMap的getNode获取键值对，若为空则直接返回。 -
判断
accessOrder是否为 true，若为 true 则说明需要保证LinkedHashMap的链表访问有序性，执行步骤 3。 -
调用
LinkedHashMap重写的afterNodeAccess将当前元素添加到链表末尾。
关键点在于 afterNodeAccess 方法的实现，这个方法负责将元素移动到链表末尾。
void afterNodeAccess(Node < K, V > e) { // move node to last
LinkedHashMap.Entry < K, V > last;
//如果accessOrder 且当前节点不未链表尾节点
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 指向前驱节点,这个 else其实 没有意义，因为最开头if已经确保了p不是尾结点了，自然after不会是null
last = b;
//如果last为空，则说明当前链表只有一个节点p，则将head指向p
if (last == null)
head = p;
else {
//反之让p的前驱指针指向尾节点，再让尾节点的前驱指针指向p
p.before = last;
last.after = p;
}
//tail指向p，自此将节点p移动到链表末尾
tail = p;
++modCount;
}
}从源码可以看出， afterNodeAccess 方法完成了下面这些操作:
-
如果
accessOrder为 true 且链表尾部不为当前节点 p，我们则需要将当前节点移到链表尾部。 -
获取当前节点 p、以及它的前驱节点 b 和后继节点 a。
-
将当前节点 p 的后继指针设置为 null，使其和后继节点 p 断开联系。
-
尝试将前驱节点指向后继节点，若前驱节点为空，则说明当前节点 p 就是链表首节点，故直接将后继节点 a 设置为首节点，随后我们再将 p 追加到 a 的末尾。
-
再尝试让后继节点 a 指向前驱节点 b。
-
上述操作让前驱节点和后继节点完成关联，并将当前节点 p 独立出来，这一步则是将当前节点 p 追加到链表末端，如果链表末端为空，则说明当前链表只有一个节点 p，所以直接让 head 指向 p 即可。
-
上述操作已经将 p 成功到达链表末端，最后我们将 tail 指针即指向链表末端的指针指向 p 即可。
可以结合这张图理解，展示了 key 为 13 的元素被移动到了链表尾部。
LinkedHashMap 移动元素 13 到链表尾部
3、构造方法
LinkedHashMap 构造方法有 4 个实现也比较简单，直接调用父类即 HashMap 的构造方法完成初始化
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 和 HashMap 遍历性能比较
LinkedHashMap 维护了一个双向链表来记录数据插入的顺序，因此在迭代遍历生成的迭代器的时候，是按照双向链表的路径进行遍历的。这一点相比于 HashMap 那种遍历整个 bucket 的方式来说，高效许多。
这一点我们可以从两者的迭代器中得以印证，先来看看 HashMap 的迭代器，可以看到 HashMap 迭代键值对时会用到一个 nextNode 方法，该方法会返回 next 指向的下一个元素，并会从 next 开始遍历 bucket 找到下一个 bucket 中不为空的元素 Node。
final class EntryIterator extends HashIteratorimplements Iterator < Map.Entry < K, V >> {
public final Map.Entry < K,V > next() {
return nextNode();
}
}
//获取下一个Node
final Node < K, V > nextNode() {
Node < K, V > [] t;
//获取下一个元素next
Node < K, V > e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
//将next指向bucket中下一个不为空的Node
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}相比之下 LinkedHashMap 的迭代器则是直接使用通过 after 指针快速定位到当前节点的后继节点，简洁高效许多。
final class LinkedEntryIterator extends LinkedHashIterator
implements Iterator < Map.Entry < K, V >> {
public final Map.Entry < K,V > next() {
return nextNode();
}
}
//获取下一个Node
final LinkedHashMap.Entry < K, V > nextNode() {
//获取下一个节点next
LinkedHashMap.Entry < K, V > e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
//current 指针指向当前节点
current = e;
//next直接当前节点的after指针快速定位到下一个节点
next = e.after;
return e;
}为了验证所说的观点，对这两个容器进行了压测，测试插入 1000w 和迭代 1000w 条数据的耗时，代码如下:
public static void main(String[] args) {
int count = 1000_0000;
Map<Integer, Integer> hashMap = new HashMap<>();
Map<Integer, Integer> linkedHashMap = new LinkedHashMap<>();
long start, end;
start = System.currentTimeMillis();
for (int i = 0; i < count; i++) {
hashMap.put(ThreadLocalRandom.current().nextInt(1, count), ThreadLocalRandom.current().nextInt(0, count));
}
end = System.currentTimeMillis();
System.out.println("map time putVal: " + (end - start));
start = System.currentTimeMillis();
for (int i = 0; i < count; i++) {
linkedHashMap.put(ThreadLocalRandom.current().nextInt(1, count), ThreadLocalRandom.current().nextInt(0, count));
}
end = System.currentTimeMillis();
System.out.println("linkedHashMap putVal time: " + (end - start));
start = System.currentTimeMillis();
long num = 0;
for (Integer v : hashMap.values()) {
num = num + v;
}
end = System.currentTimeMillis();
System.out.println("map get time: " + (end - start));
start = System.currentTimeMillis();
for (Integer v : linkedHashMap.values()) {
num = num + v;
}
end = System.currentTimeMillis();
System.out.println("linkedHashMap get time: " + (end - start));
System.out.println(num);
}从输出结果来看，因为 LinkedHashMap 需要维护双向链表的缘故，插入元素相较于 HashMap 会更耗时，但是有了双向链表明确的前后节点关系，迭代效率相对于前者高效了许多。不过，总体来说却别不大，毕竟数据量这么庞大。
结果：
-
map time putVal: 5880
-
linkedHashMap putVal time: 7567
-
map get time: 143
-
linkedHashMap get time: 67 63208969074998
五、LinkedHashMap 常见面试题
1、什么是 LinkedHashMap？
LinkedHashMap 是 Java 集合框架中 HashMap 的一个子类，它继承了 HashMap 的所有属性和方法，并且在 HashMap 的基础重写了 afterNodeRemoval、afterNodeInsertion、afterNodeAccess 方法。使之拥有顺序插入和访问有序的特性。
2、LinkedHashMap的基本特性是什么？
-
有序性：LinkedHashMap维护了一个双向链表，该链表按照元素的插入顺序（或访问顺序，取决于构造时的参数）进行排序。因此，LinkedHashMap是有序的。
-
键值对存储：与HashMap一样，LinkedHashMap也是基于键值对（key-value）进行存储的。
-
允许null值：LinkedHashMap允许使用一个null键和多个null值。
-
非线程安全：LinkedHashMap和HashMap一样，都不是线程安全的。如果在多线程环境下使用，需要进行额外的同步处理。
3、LinkedHashMap 如何按照插入顺序迭代元素？
LinkedHashMap 按照插入顺序迭代元素是它的默认行为。LinkedHashMap 内部维护了一个双向链表，用于记录元素的插入顺序。因此，当使用迭代器迭代元素时，元素的顺序与它们最初插入的顺序相同。
4、LinkedHashMap 如何按照访问顺序迭代元素？
LinkedHashMap 可以通过构造函数中的 accessOrder 参数指定按照访问顺序迭代元素。当 accessOrder 为 true 时，每次访问一个元素时，该元素会被移动到链表的末尾，因此下次访问该元素时，它就会成为链表中的最后一个元素，从而实现按照访问顺序迭代元素。
5、LinkedHashMap 如何实现 LRU 缓存？
将 accessOrder 设置为 true 并重写 removeEldestEntry 方法当链表大小超过容量时返回 true，使得每次访问一个元素时，该元素会被移动到链表的末尾。一旦插入操作让 removeEldestEntry 返回 true 时，视为缓存已满，LinkedHashMap 就会将链表首元素移除，由此我们就能实现一个 LRU 缓存。
6、LinkedHashMap 和 HashMap 有什么区别？
-
有序性：HashMap是无序的，而LinkedHashMap是有序的。
-
迭代顺序：HashMap的迭代顺序通常不保证与插入顺序一致，而LinkedHashMap的迭代顺序则与插入顺序（或访问顺序）一致。
-
性能：由于需要维护一个双向链表，LinkedHashMap的性能略低于HashMap。但在需要保持元素顺序的场景下，LinkedHashMap是一个更好的选择。
7、LinkedHashMap在什么情况下会触发扩容？
LinkedHashMap的扩容机制与HashMap相同。当元素数量超过阈值（容量乘以负载因子）时，LinkedHashMap会进行扩容操作。扩容后，数组的长度将变为原来的两倍，并重新计算每个元素的哈希值以确定其在新数组中的位置。同时，双向链表的结构也会得到相应的调整。
8、LinkedHashMap的底层实现原理是什么？
-
LinkedHashMap的底层实现原理与HashMap类似，都采用了数组+链表（或红黑树，在JDK 8及更高版本中）的结构。
-
但在HashMap的基础上，LinkedHashMap增加了一个双向链表来维护元素的顺序。
-
当向LinkedHashMap中添加元素时，该元素会被添加到哈希表的相应位置和双向链表的末尾（或头部）。
-
在访问某个元素时，如果该元素存在且accessOrder为true，则将其移动到链表的末尾。
扫一扫
3251
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
