Java LinkedHashMap的双向链表原理
Java LinkedHashMap 简介
LinkedHashMap 是 Java 集合框架中 HashMap 的一个子类，它在 HashMap 的基础上增加了双向链表的结构，用于维护插入顺序或者访问顺序。这使得 LinkedHashMap 不仅具备 HashMap 的快速查找特性，还能按照特定顺序遍历元素。
LinkedHashMap 实现了 Map 接口，提供了一种有序的键值对存储方式。其有序性体现在遍历时元素的顺序与插入顺序或者访问顺序一致。在 LinkedHashMap 中，每一个键值对不仅作为 HashMap 中的节点存在，还通过双向链表的形式相互连接，形成一个有序的序列。
双向链表结构在 LinkedHashMap 中的体现
在 LinkedHashMap 内部，除了继承自 HashMap 的哈希表结构外，还维护了一个双向链表。双向链表的节点是 LinkedHashMap.Entry，它继承自 HashMap.Node。
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);
}
}
上述代码展示了 LinkedHashMap.Entry 的结构，它在 HashMap.Node 的基础上增加了 before 和 after 两个引用，分别指向链表中的前一个节点和后一个节点。这样就形成了双向链表的结构，通过这两个引用可以方便地在链表中进行前后遍历。
插入顺序维护原理
当使用 LinkedHashMap 以插入顺序存储元素时，每次向 LinkedHashMap 中插入新的键值对时，新的节点会被添加到双向链表的尾部。
例如，以下代码展示了以插入顺序遍历 LinkedHashMap：
import java.util.LinkedHashMap;
import java.util.Map;
public class InsertionOrderLinkedHashMapExample {
public static void main(String[] args) {
LinkedHashMap<Integer, String> linkedHashMap = new LinkedHashMap<>(16, 0.75f, false);
linkedHashMap.put(1, "One");
linkedHashMap.put(2, "Two");
linkedHashMap.put(3, "Three");
for (Map.Entry<Integer, String> entry : linkedHashMap.entrySet()) {
System.out.println(entry.getKey() + " : " + entry.getValue());
}
}
}
在上述代码中，LinkedHashMap 的构造函数的第三个参数为 false，表示使用插入顺序。当遍历 linkedHashMap 时，输出结果为：
1 : One
2 : Two
3 : Three
这表明元素是按照插入的顺序进行遍历的。在插入新元素时，LinkedHashMap 会调用 linkNodeLast 方法将新节点添加到链表尾部：
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
此方法先获取当前链表的尾节点 last，将新节点 p 设置为尾节点 tail。如果 last 为 null，说明链表为空，此时新节点 p 就是头节点 head；否则，将新节点 p 的 before 指向 last，并将 last 的 after 指向 p，从而完成新节点在链表尾部的插入。
访问顺序维护原理
当 LinkedHashMap 以访问顺序存储元素时，每次访问（get 或者 put 已存在的键值对）一个元素，该元素会被移动到双向链表的尾部。
以下是使用访问顺序遍历 LinkedHashMap 的示例代码：
import java.util.LinkedHashMap;
import java.util.Map;
public class AccessOrderLinkedHashMapExample {
public static void main(String[] args) {
LinkedHashMap<Integer, String> linkedHashMap = new LinkedHashMap<>(16, 0.75f, true);
linkedHashMap.put(1, "One");
linkedHashMap.put(2, "Two");
linkedHashMap.put(3, "Three");
linkedHashMap.get(2);
for (Map.Entry<Integer, String> entry : linkedHashMap.entrySet()) {
System.out.println(entry.getKey() + " : " + entry.getValue());
}
}
}
在上述代码中，LinkedHashMap 的构造函数的第三个参数为 true，表示使用访问顺序。当获取键为 2 的元素后再进行遍历时，输出结果为：
1 : One
3 : Three
2 : Two
这表明键为 2 的元素因为被访问而移动到了链表的尾部。在 get 方法中，当获取到节点后会调用 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;
}
}
此方法首先判断是否是访问顺序（accessOrder 为 true），并且获取到的节点 e 不是尾节点 last。然后将节点 e 从当前位置移除，再将其添加到链表尾部。具体操作是先处理节点 e 的前后节点的连接关系，然后将节点 e 连接到链表尾部，更新 tail 以及修改次数 modCount。
双向链表与哈希表的协同工作
LinkedHashMap 中的双向链表与哈希表是紧密协同工作的。哈希表用于快速定位键值对，而双向链表用于维护顺序。
在插入操作时，首先根据键的哈希值在哈希表中找到对应的桶位，如果桶位为空则直接插入新节点；如果桶位不为空，则需要遍历桶中的链表（在 JDK 8 及以后，如果链表长度超过阈值会转换为红黑树）来查找是否存在相同键的节点。如果不存在，则插入新节点到哈希表中，并将其添加到双向链表尾部。
在查找操作时，通过哈希表快速定位到可能存在目标键值对的桶位，然后在桶内的链表或红黑树中查找。如果找到了目标节点，并且是访问顺序的 LinkedHashMap，则将该节点移动到双向链表的尾部。
例如，在 get 方法中，先通过哈希表查找节点：
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
先调用 getNode 方法在哈希表中查找节点，如果找到并且是访问顺序，则调用 afterNodeAccess 方法调整节点在双向链表中的位置。
在删除操作时，需要同时从哈希表和双向链表中移除节点。在 remove 方法中，先调用 removeNode 方法从哈希表中移除节点，然后在 afterNodeRemoval 方法中从双向链表中移除节点：
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
此方法将节点 e 从双向链表中移除，重新调整前后节点的连接关系。
LinkedHashMap 的性能分析
LinkedHashMap 的性能在很大程度上依赖于其继承的 HashMap。由于 LinkedHashMap 维护了双向链表结构，插入、删除和查找操作除了哈希表本身的开销外，还需要额外处理双向链表的操作。
在插入操作上，由于需要在双向链表尾部添加节点（插入顺序）或者调整节点位置（访问顺序），额外的时间复杂度为 O(1)，整体插入操作的平均时间复杂度与 HashMap 相同，为 O(1)，最坏情况下为 O(n)，其中 n 为哈希表中的元素个数。
在查找操作上，哈希表的查找时间复杂度为 O(1) 平均情况，O(n) 最坏情况，对于访问顺序的 LinkedHashMap，找到节点后还需要将节点移动到双向链表尾部，这一步的时间复杂度为 O(1)，所以整体查找操作的平均时间复杂度仍接近 O(1)。
在删除操作上，从哈希表中删除节点的时间复杂度为 O(1) 平均情况，O(n) 最坏情况，从双向链表中删除节点的时间复杂度为 O(1)，所以整体删除操作的平均时间复杂度也接近 O(1)。
空间复杂度方面，LinkedHashMap 除了哈希表占用的空间外，双向链表的每个节点还额外占用了两个引用（before 和 after）的空间，因此空间复杂度会比 HashMap 略高。
应用场景
- LRU 缓存实现：
LinkedHashMap非常适合实现最近最少使用（LRU）缓存。通过使用访问顺序的LinkedHashMap，当缓存满时，移除双向链表头部的节点（即最久未使用的节点），新访问或插入的节点会被移动到链表尾部。以下是一个简单的 LRU 缓存实现示例：
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;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
}
在上述代码中，LRUCache 继承自 LinkedHashMap，重写了 removeEldestEntry 方法，当缓存大小超过设定的容量时，返回 true，从而触发移除最久未使用的节点（链表头部节点）。
-
记录操作顺序：在一些需要记录操作顺序的场景中，例如记录用户的操作历史，
LinkedHashMap可以按照操作的先后顺序存储操作记录，方便后续按照顺序进行查看和分析。 -
有序输出：当需要按照插入顺序输出键值对时，
LinkedHashMap可以直接满足需求，而不需要对普通的HashMap进行额外的排序操作。
与其他集合类的比较
-
与 HashMap 的比较：
HashMap是无序的，其重点在于提供快速的查找和插入性能。而LinkedHashMap在HashMap的基础上增加了双向链表结构，用于维护顺序，这使得LinkedHashMap不仅具备快速查找能力，还能按照特定顺序遍历元素，但同时也增加了一定的空间开销。 -
与 TreeMap 的比较：
TreeMap是基于红黑树实现的有序Map，它按照键的自然顺序或者自定义顺序进行排序。而LinkedHashMap可以按照插入顺序或者访问顺序进行排序。TreeMap的查找、插入和删除操作的时间复杂度为 O(log n)，而LinkedHashMap的平均时间复杂度为 O(1)。此外，TreeMap适用于需要按键排序的场景，而LinkedHashMap更适用于需要按插入或访问顺序维护元素顺序的场景。
总结
LinkedHashMap 通过在 HashMap 的基础上引入双向链表结构，为开发者提供了一种既具备快速查找性能又能维护元素顺序的集合类。无论是插入顺序还是访问顺序的维护，都为解决实际应用中的各种需求提供了便利。在性能方面，虽然由于双向链表的维护带来了一定的额外开销，但整体上仍然保持了与 HashMap 相近的高效性。通过合理利用 LinkedHashMap，可以实现如 LRU 缓存等复杂而实用的功能，在不同的应用场景中发挥重要作用。理解 LinkedHashMap 的双向链表原理，有助于开发者更好地使用和优化相关代码，提高程序的性能和可维护性。