深入浅出Java中的数据结构：LinkedHashMap详解
原创
哈喽，各位小伙伴们，你们好呀，我是喵手。
今天我要给大家分享一些自己日常学习到的一些知识点，并以文字的形式跟大家一起交流，互相学习，一个人虽可以走的更快，但一群人可以走的更远。
我是一名后端开发爱好者，工作日常接触到最多的就是Java语言啦，所以我都尽量抽业余时间把自己所学到所会的，通过文章的形式进行输出，希望以这种方式帮助到更多的初学者或者想入门的小伙伴们，同时也能对自己的技术进行沉淀，加以复盘，查缺补漏。
小伙伴们在批阅的过程中，如果觉得文章不错，欢迎点赞、收藏、关注哦。三连即是对作者我写作道路上最好的鼓励与支持！
如下是Java集合体系架构图，近期几期内容都是围绕该体系进行知识讲解，以便于同学们学习Java集合篇知识能够系统化而不零散。
前言
在Java编程中，我们经常需要使用Map这个数据结构来存储键值对，而LinkedHashMap是Map的一个实现类，它在HashMap的基础上维护了一个双向链表，并且按照插入顺序或者访问顺序来迭代元素。LinkedHashMap既保证了HashMap的快速访问性能，又提供了顺序访问的能力，因此在某些场景下非常有用。
本文将从源代码解析、应用场景案例、优缺点分析等多个方面对LinkedHashMap进行详细介绍，希望能帮助读者更好地理解LinkedHashMap的实现原理和使用方法。
摘要
本文主要介绍了Java中的LinkedHashMap这个数据结构，并对其源代码进行了分析和解读。通过对LinkedHashMap的应用场景案例和优缺点分析，读者可以更好地理解LinkedHashMap的使用方法和使用场景。
LinkedHashMap
简介
LinkedHashMap是Java中Map接口的一个实现类，它继承了HashMap，并且在HashMap的基础上维护了一个双向链表。LinkedHashMap的特点是可以按照插入顺序或者访问顺序来迭代元素。按照插入顺序迭代时，元素的顺序和插入的顺序相同；按照访问顺序迭代时，访问过的元素会被移动到链表的尾部，最近访问的元素会排在链表的前面。
LinkedHashMap的构造方法有以下几种：
public LinkedHashMap() {
super();
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
}
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
}
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}其中，accessOrder参数表示是否按照访问顺序来迭代元素。如果accessOrder为true，表示按照访问顺序来迭代元素；如果accessOrder为false，表示按照插入顺序来迭代元素。如果不指定accessOrder参数，则默认按照插入顺序来迭代元素。
LinkedHashMap是线程不安全的，如果需要多线程并发访问，需要使用ConcurrentHashMap。
源代码解析
LinkedHashMap的源代码比HashMap的源代码要复杂一些，因为它需要维护一个双向链表。下面我们将对LinkedHashMap的源代码进行分析，帮助读者更好地理解它的实现原理。
数据结构
LinkedHashMap维护了一个双向链表，链表节点类型为Entry，继承了HashMap的Node类。Entry类的定义如下：
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);
}
}其中，before和after分别表示当前节点的前驱节点和后继节点。
实现原理
在LinkedHashMap中，每个Entry节点都维护了一个before和after指针，表示该节点的前驱节点和后继节点。因此，LinkedHashMap需要重写HashMap的put和remove方法，以保证在插入和删除元素时能够正确地更新链表。
put方法
当调用put方法插入一个新元素时，LinkedHashMap会调用父类HashMap的putVal方法来实现插入。在putVal方法中，如果插入的元素已经存在，则会更新该元素的value值，并返回旧的value值；如果插入的元素不存在，则会创建一个新节点，并将该节点插入到hash桶中。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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;
}在调用父类HashMap的put方法插入新元素之后，LinkedHashMap会在afterNodeInsertion方法中更新链表。具体更新流程如下：
void afterNodeInsertion(boolean evict) { // possibly remove eldest
Entry<K,V> eldest;
if (evict && (eldest = eldest()) != null && removeEldestEntry(eldest)) {
K key = eldest.key;
removeNode(hash(key), key, null, false, true);
}
else if (size > capacity && removeEldestEntry(head)) {
K key = head.key;
removeNode(hash(key), key, null, false, true);
}
}其中，removeEldestEntry方法用于判断是否需要删除最老的节点，该方法默认返回false，如果需要删除最老的节点，需要在继承LinkedHashMap的类中重写该方法。
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}如果需要删除最老的节点，则会调用removeNode方法来删除该节点。
final void 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;
--size;
afterNodeRemoval(node); // 更新链表
return;
}
}
}在LinkedHashMap中，每个节点都维护了一个before和after指针，表示该节点的前驱节点和后继节点。因此，在插入和删除元素时，需要更新链表以保证顺序的正确性。
在插入元素时，插入操作会调用父类HashMap的putVal方法，插入新节点；接着，在afterNodeInsertion方法中，会调用方法addEntry方法将新节点插入到链表的尾部。具体实现如下：
void afterNodeInsertion(boolean evict) { // possibly remove eldest
Entry<K,V> eldest;
if (evict && (eldest = eldest()) != null && removeEldestEntry(eldest)) {
K key = eldest.key;
removeNode(hash(key), key, null, false, true);
}
else if (size > capacity && removeEldestEntry(head)) {
K key = head.key;
removeNode(hash(key), key, null, false, true);
}
else {
Entry<K,V> tail = tail();
if (tail != null)
linkNodeLast(tail, newNode);
else
// 链表为空，把新节点作为头节点
head = newNode;
}
}其中，如果evict为true且需要删除最老的节点，则会调用removeNode方法删除最老的节点；如果链表长度超出了capacity则会调用removeEldestEntry方法删除头部节点（即最老的节点）。如果不需要删除节点，则会调用linkNodeLast方法将新节点插入到链表的尾部。
在删除节点时，调用removeNode方法删除节点后，会调用afterNodeRemoval方法来更新链表。如果需要删除的节点是头节点，则会将头节点更新为头节点的后继节点；否则，需要更新要删除节点的前驱节点的after指针和后继节点的before指针。具体实现如下：
void afterNodeRemoval(Node<K,V> e) { // unlink
Entry<K,V> p = (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;
}
迭代器
LinkedHashMap提供了按照插入顺序和访问顺序来迭代元素的能力。在按照插入顺序迭代时，只需要按照节点的插入顺序依次迭代即可；在按照访问顺序迭代时，需要按照节点的访问顺序来迭代，即最近访问的节点排在链表的前面。因此，LinkedHashMap需要重写HashMap的迭代器，实现按照访问顺序迭代元素的功能。
在LinkedHashMap中，Entry节点继承了HashMap的Node类，并且新增了before和after指针，因此LinkedHashMap需要重写HashMap的迭代器，实现按照访问顺序来迭代元素。
在创建迭代器时，需要判断是否按照访问顺序来迭代元素。如果按照访问顺序来迭代元素，则需要按照节点的访问顺序来排序，最近访问的节点排在链表的前面；否则，按照节点的插入顺序依次迭代。
具体实现如下：
Iterator<Entry<K,V>> newIterator() {
return new LinkedHashIterator();
}
final class LinkedHashIterator extends HashMapIterator<Entry<K,V>> {
public Entry<K,V> next() {
return nextNode();
}
public void remove() {
removeNode(lastReturned);
}
}
final class EntryIterator extends LinkedHashIterator {
public Entry<K,V> next() {
return nextNode();
}
}
final class KeyIterator extends LinkedHashIterator {
public K next() {
return nextNode().getKey();
}
}
final class ValueIterator extends LinkedHashIterator {
public V next() {
return nextNode().value;
}
}
final class LinkedKeyIterator extends KeyIterator {
public K next() {
return nextEntry().getKey();
}
}
final class LinkedValueIterator extends ValueIterator {
public V next() {
return nextEntry().value;
}
}
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
Entry<K,V> p = new Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
void linkNodeLast(Entry<K,V> p) {
Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}其中，newIterator方法用于创建迭代器对象，返回一个LinkedHashIterator对象；LinkedHashIterator继承了HashMap的迭代器类HashMapIterator，并且重写了next方法和remove方法，以实现按照访问顺序迭代元素的功能。
在nextNode方法中，如果按照访问顺序来迭代元素，则会将最近访问的节点移动到链表的尾部（即末尾），以实现最近访问的节点排在链表的前面。
final Node<K,V> nextNode() {
Entry<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
// 按照访问顺序来迭代元素
if (accessOrder)
lastReturned = e;
// 按照插入顺序迭代元素
else
lastReturned = next;
next = e.after;
return lastReturned;
}在removeNode方法中，如果需要删除的节点是最近访问的节点，则需要将指针last指向要删除节点的前驱节点，以便在下一次迭代时正确地返回要迭代的元素。
final void removeNode(Node<K,V> p) {
Entry<K,V> e = (Entry<K,V>)p, b = e.before, a = e.after;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
if (e == lastReturned)
next = a;
else
expectedModCount++;
modCount++;
size--;
e.value = null;
}应用场景案例
LinkedHashMap可以用于需要有序存储和访问的场景，比如LRU缓存、打印日志、调试信息存储等。下面以LRU缓存为例，介绍LinkedHashMap的应用。
在实现LRU缓存时，可以使用LinkedHashMap来存储数据，最近访问的元素会被移动到链表的尾部，最老的元素位于链表的头部。每当缓存中的元素数量超过了一定的阈值时，就可以通过removeEldestEntry方法删除最老的元素，以保证缓存中的元素不超过阈值。
public class LRUCache<K, V> extends LinkedHashMap<K,V> {
private int capacity;
private static final float LOAD_FACTOR = 0.75f;
public LRUCache(int capacity) {
super(capacity, LOAD_FACTOR, true);
this.capacity = capacity;
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return size() > capacity;
}
}在LRUCache的实现中，继承了LinkedHashMap，并重写了构造方法和removeEldestEntry方法。构造方法使用了accessOrder参数来指定按照访问顺序迭代元素，以便将最近访问的元素移动到链表的尾部。removeEldestEntry方法用于判断是否需要删除最老的元素，如果缓存中的元素数量超过了阈值，则需要删除最老的元素。
优缺点分析
LinkedHashMap相对于HashMap的优点在于：
- 可以按照插入顺序和访问顺序迭代元素。
- 通过维护一个双向链表，可以实现LRU缓存等有序存储和访问的场景。
- 在保证HashMap的快速访问性能的同时，提供了顺序访问的能力。
LinkedHashMap相对于HashMap的缺点在于：
- 需要维护一个双向链表，因此占用内存更多。
- 删除节点时需要更新前驱节点的after指针和后继节点的before指针，比HashMap多了一些操作，因此性能可能略差一些。
- LinkedHashMap是线程不安全的，如果需要多线程并发访问，需要使用ConcurrentHashMap。
测试用例
测试代码演示
下面是一个使用LinkedHashMap的测试用例：
以下是一个简单的测试用例，演示如何使用 LinkedHashMap 来存储键值对，并打印出 LinkedHashMap 的值：
package com.example.javase.collection;
import java.util.LinkedHashMap;
import java.util.Map;
/**
* @author ms
* @date 2023/10/25 15:50
*/
public class LinkedHashMapTest {
public static void main(String[] args) {
// 创建一个 LinkedHashMap 对象
Map<String, String> linkedHashMap = new LinkedHashMap<>();
// 添加键值对到 LinkedHashMap
linkedHashMap.put("key1", "value1");
linkedHashMap.put("key2", "value2");
linkedHashMap.put("key3", "value3");
// 打印 LinkedHashMap 的键值对
for (Map.Entry<String, String> entry : linkedHashMap.entrySet()) {
System.out.println(entry.getKey() + " : " + entry.getValue());
}
}
}预计输出结果：
key1 : value1
key2 : value2
key3 : value3测试结果
根据如上测试用例，本地测试结果如下，仅供参考，你们也可以自行修改测试用例或者添加更多的测试数据或测试方法，进行熟练学习以此加深理解。
测试代码分析
根据如上测试用例，在此我给大家进行深入详细的解读一下测试代码，以便于更多的同学能够理解并加深印象。
首先，导入了java.util.LinkedHashMap 和 java.util.Map 包。在 main 方法中创建了一个 LinkedHashMap 对象。
然后，通过 put 方法向 LinkedHashMap 中添加了三组键值对。
最后，通过 for-each 循环遍历 LinkedHashMap 中的键值对，并打印出来。
LinkedHashMap 是基于哈希表和双向链表的数据结构，它可以保持插入顺序，因此可以按照插入顺序遍历。在插入新元素时，它将元素插入到链表的末尾，保持了元素的插入顺序。
这个测试用例主要演示了 LinkedHashMap的基本用法，包括如何创建一个 LinkedHashMap 对象、如何添加元素、如何遍历元素等。
小结
LinkedHashMap是Java中的一个数据结构，它在HashMap的基础上维护了一个双向链表，可以按照插入顺序或者访问顺序来迭代元素。LinkedHashMap在保证了HashMap的快速访问性能的同时，提供了顺序访问的能力，因此可以应用在需要有序存储和访问的场景，比如LRU缓存、打印日志、调试信息存储等。
在使用LinkedHashMap时，需要注意它占用的内存较HashMap更多，删除节点时需要更新前驱节点的after指针和后继节点的before指针，性能可能略差一些。此外，LinkedHashMap不是线程安全的，如果需要多线程并发访问，需要使用ConcurrentHashMap。
总结
本文详细介绍了Java中的LinkedHashMap这个数据结构，包括其构造方法、源代码解析、应用场景案例和优缺点分析等多个方面。LinkedHashMap继承了HashMap并在其基础上维护了一个双向链表，可以按照插入顺序或者访问顺序来迭代元素。LinkedHashMap可以应用在需要有序存储和访问的场景，比如LRU缓存、打印日志、调试信息存储等。
需要注意的是，LinkedHashMap占用的内存较HashMap更多，删除节点时需要更新前驱节点的after指针和后继节点的before指针，性能可能略差一些。此外，LinkedHashMap不是线程安全的，如果需要多线程并发访问，需要使用ConcurrentHashMap。
... ...
文末
好啦，以上就是我这期的全部内容，如果有任何疑问，欢迎下方留言哦，咱们下期见。
... ...
学习不分先后，知识不分多少；事无巨细，当以虚心求教；三人行，必有我师焉！！！
wished for you successed ！！！
⭐️若喜欢我，就请关注我叭。
⭐️若对您有用，就请点赞叭。
⭐️若有疑问，就请评论留言告诉我叭。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
