DEMO
LinkedHashMap是LinkedList和HashMap的结合体，它内部的存储结构可以简单表示为下面这样：
文章源自灵鲨社区-https://www.0s52.com/bcjc/javajc/16636.html
LinkedHashMap内部存储的Entry在HashMap的基础上增加了两个指针：before和after。这两个节点可以对插入的节点进行链接，以此来维护顺序性。同时，链表结构为了方便插入，也会持有“头尾节点”这两个指针。文章源自灵鲨社区-https://www.0s52.com/bcjc/javajc/16636.html
LinkedHashMap的优点。文章源自灵鲨社区-https://www.0s52.com/bcjc/javajc/16636.html
- 一个是降低了遍历实现的复杂度。我们对比一下，HashMap的遍历是首先遍历哈希槽，然后遍历链表；但LinkedHashMap则可以基于头节点遍历，复杂度明显降低。
- 引入链表的第二个优点则是提供了顺序性。
LinkedHashMap提供了两种顺序性机制：文章源自灵鲨社区-https://www.0s52.com/bcjc/javajc/16636.html
- 按节点插入顺序，是LinkedHashMap的默认行为；
- 按节点的访问性顺序，最新访问的节点将被放到链表的末尾。
arduino
public class LinkedHashMapDemo {
public static void main(String[] args) {
//按插入顺序排序
orderOfWrite();
System.out.println("---------");
//按访问顺序排序
orderOfRreader();
}
public static void orderOfWrite() {
LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
map.put("Apple", 1);
map.put("Banana", 2);
map.put("Cherry", 3);
System.out.println("按插入顺序排序:");
for (Map.Entry<String, Integer> entry : map.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
}
public static void orderOfRreader() {
LinkedHashMap<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true);
map.put("Apple", 1);
map.put("Banana", 2);
map.put("Cherry", 3);
System.out.println("按插入顺序排序:");
// 访问"Banana"
System.out.println(map.get("Banana"));
for (Map.Entry<String, Integer> entry : map.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
}
}
makefile
按插入顺序排序:
Apple: 1
Banana: 2
Cherry: 3
---------
按插入顺序排序:
2
Apple: 1
Cherry: 3
Banana: 2
概述
文章源自灵鲨社区-https://www.0s52.com/bcjc/javajc/16636.html
事实上LinkedHashMap是HashMap的直接子类，二者唯一的区别是 LinkedHashMap 在 HashMap 的基础上，采用双向链表(doubly-linked list)的形式将所有entry连接起来，这样是为保证元素的迭代顺序跟插入顺序相同。上图给出了LinkedHashMap的结构图，主体部分跟HashMap完全一样，多了header指向双向链表的头部(是一个哑元)，该双向链表的迭代顺序就是entry的插入顺序。文章源自灵鲨社区-https://www.0s52.com/bcjc/javajc/16636.html
除了可以保迭代历顺序，这种结构还有一个好处 : 迭代 LinkedHashMap 时不需要像 HashMap 那样遍历整个table，而只需要直接遍历header指向的双向链表即可，也就是说LinkedHashMap的迭代时间就只跟entry的个数相关，而跟table的大小无关。文章源自灵鲨社区-https://www.0s52.com/bcjc/javajc/16636.html
有两个参数可以影响LinkedHashMap的性能: 初始容量(inital capacity)和负载系数(load factor)。初始容量指定了初始table的大小，负载系数用来指定自动扩容的临界值。当entry的数量超过capacity*load_factor时，容器将自动扩容并重新哈希。对于插入元素较多的场景，将初始容量设大可以减少重新哈希的次数。文章源自灵鲨社区-https://www.0s52.com/bcjc/javajc/16636.html
将对象放入到LinkedHashMap，有两个方法需要特别关心: hashCode()和equals()。hashCode()方法决定了对象会被放到哪个bucket里，当多个对象的哈希值冲突时，equals()方法决定了这些对象是否是“同一个对象” 。所以，如果要将自定义的对象放入到LinkedHashMap或LinkedHashSet中，需要重写 hashCode()和equals()方法。文章源自灵鲨社区-https://www.0s52.com/bcjc/javajc/16636.html
出于性能原因，LinkedHashMap是非同步的(not synchronized)，如果需要在多线程环境使用，需要程序员手动同步；或者通过如下方式将LinkedHashMap包装成(wrapped)同步的:文章源自灵鲨社区-https://www.0s52.com/bcjc/javajc/16636.html
ini
Map m = Collections.synchronizedMap(new LinkedHashMap(...));
源码分析
LinkedHashMap 是一个关联数组、哈希表，它是线程不安全的，允许key为null,value为null。它继承自HashMap，实现了Map<K,V>接口。其内部还维护了一个双向链表，在每次插入数据，或者访问、修改数据时，会增加节点、或调整链表的节点顺序。以决定迭代时输出的顺序。
默认情况，遍历时的顺序是按照插入节点的顺序。这也是其与HashMap最大的区别。也可以在构造时传入accessOrder参数，使得其遍历顺序按照访问的顺序输出。
LinkedHashMap实现了Map接口，即允许放入key为null的元素，也允许插入value为null的元素。从名字上可以看出该容器是linked list和HashMap的混合体，也就是说它同时满足HashMap和linked list的某些特性。可将 LinkedHashMap 看作采用 linked list 增强的 HashMap 。
双向链表
scala
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{
// 这段代码定义了一个静态内部类Entry，它继承了HashMap.Node类，
// 用于表示哈希表中的键值对节点。Entry类添加了两个指向相邻节点的引用before和after，
// 用于双向链表的维护。构造函数用于初始化节点的哈希值、键、值和下一个节点
static class Entry<K,V> extends HashMap.Node<K,V> {
// 新加成员变量before、after，用于双向链表的连接
Entry<K,V> before, after;
//构造方法
Entry(int hash, K key, V value, Node<K,V> next) {
//父类构造方法
super(hash, key, value, next);
}
}
}
同时类里有两个成员变量head tail,分别指向内部双向链表的表头、表尾。
ini
//双向链表的头结点
transient LinkedHashMap.Entry<K,V> head;
//双向链表的尾结点
transient LinkedHashMap.Entry<K,V> tail;
//排序方式，true-访问顺序 false-插入顺序
//默认是插入顺序存储：accessOrder = false;
//accessOrder = true时表示访问顺序存储，就是最新访问的数据会放到链表尾部！
//（访问顺序的LinkedHashMap进行了get操作以后，重新排序，把get的Entry移动到双向链表的表尾。）
final boolean accessOrder;
LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>，可发现LinkedHashMap相比较HashMap多维护了2个成员变量head、tail，这2个变量就是LinkedHashMap实现双向链表的关键变量。
LinkedHashMap 重写了父类新建节点的方法，在新建节点之后调用 linkNodeLast 方法将新添加的节点链接到双向链表的末尾：
ini
//HashMap.put()方法创建新Node会调用newNode()方法，LinkedHashMap重写了HashMap的newNode()
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
//将新节点加入双向链表尾部
linkNodeLast(p);
return p;
}
//将新节点加入双向链表尾部
// link at the end of list
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;//旧尾节点作为新节点的before
last.after = p;//新节点作为旧尾节点的after
}
}
HashMap.put()方法创建新Node会调用newNode()方法，LinkedHashMap重写了HashMap的newNode()。所以，往LinkedHashMap中put()数据时会调用linkNodeLast()，将新节点加入双向链表。
get()
默认情况下，LinkedHashMap 是按插入顺序维护链表。不过我们可以在初始化 LinkedHashMap，指定 accessOrder 参数为 true，即可让它按访问顺序维护链表。访问顺序的原理上并不复杂，当我们调用get/getOrDefault/replace等方法时，只需要将这些方法访问的节点移动到链表的尾部即可。相应的源码如下：
ini
// LinkedHashMap 中覆写
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
// 如果 accessOrder 为 true，则调用 afterNodeAccess 将被访问节点移动到链表最后
if (accessOrder)
//访问后调用回调方法调整双链表
afterNodeAccess(e);
return e.value;
}
/**
* 根据给定的哈希值和键获取对应的节点。
* 此方法用于在HashMap中查找特定键值对的节点，首先检查哈希表是否为空，然后按照哈希值定位到链表或红黑树的起始节点，
* 并遍历链表或红黑树直到找到匹配的键值对节点或遍历结束。
*
* @param hash 节点的哈希值
* @param key 要查找的键
* @return 对应的节点，如果找不到则返回null
*/
final Node<K,V> getNode(int hash, Object key) {
// 获取table数组以及长度，同时检查table是否已经被初始化
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 当table不为空且长度大于0时，进行进一步的查找
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 如果第一个节点的哈希值、键与输入参数匹配，则直接返回该节点
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 如果第一个节点是一个TreeNode（表示当前段是一个红黑树），则使用特定的算法在树中查找
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 遍历链表，查找匹配的节点
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
// 如果没有找到匹配的节点，则返回null
return null;
}
// LinkedHashMap 中覆写
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;
// 如果 b 为 null，表明 p 为头节点
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
/*
* 这里存疑，父条件分支已经确保节点 e 不会是尾节点，
* 那么 e.after 必然不会为 null，不知道 else 分支有什么作用
*/
else
last = b;
if (last == null)
head = p;
else {
// 将 p 接在链表的最后
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
下面举例演示一下，帮助大家理解。假设我们访问下图键值为3的节点，访问前结构为：
访问后，键值为3的节点将会被移动到双向链表的最后位置，其前驱和后继也会跟着更新。访问后的结构如下：
put()
插入有两重含义:
- 从table的角度看，新的entry需要插入到对应的bucket里，当有哈希冲突时，采用头插法将新的entry插入到冲突链表的头部。
- 从header的角度看，新的entry需要插入到双向链表的尾部。
put(K key, V value)方法是将指定的key, value对添加到map里。该方法首先会对map做一次查找，看是否包含该元组，如果已经包含则直接返回，查找过程类似于get()方法；如果没有找到，则会通过addEntry(int hash, K key, V value, int bucketIndex)方法插入新的entry。
LinkedHashMap并没有重写任何put方法。但是其重写了构建新节点的newNode()方法,通过linkNodeLast(p);将新节点链接在内部双向链表的尾部。
newNode()会在HashMap的putVal()方法里被调用，putVal()方法会在批量插入数据putMapEntries(Map<? extends K, ? extends V> m, boolean evict)或者插入单个数据public V put(K key, V value)时被调用。
ini
// HashMap 中实现
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// HashMap 中实现
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) {...}
// 通过节点 hash 定位节点所在的桶位置，并检测桶中是否包含节点引用
if ((p = tab[i = (n - 1) & hash]) == 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) {...}
else {
// 遍历链表，并统计链表长度
for (int binCount = 0; ; ++binCount) {
// 未在单链表中找到要插入的节点，将新节点接在单链表的后面
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) {...}
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) {...}
afterNodeAccess(e); // 回调方法
return oldValue;
}
}
++modCount;
if (++size > threshold) {...}
afterNodeInsertion(evict); // 回调方法
return null;
}
// HashMap 中实现
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
// LinkedHashMap 中覆写
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
// 将 Entry 接在双向链表的尾部
linkNodeLast(p);
return p;
}
// LinkedHashMap 中实现
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
// last 为 null，表明链表还未建立
if (last == null)
head = p;
else {
// 将新节点 p 接在链表尾部
p.before = last;
last.after = p;
}
}
Map 类型的集合类是通过 put(K,V) 方法插入键值对，LinkedHashMap 本身并没有覆写父类的 put 方法，而是直接使用了父类的实现。但在 HashMap 中，put 方法插入的是 HashMap 内部类 Node 类型的节点，该类型的节点并不具备与 LinkedHashMap 内部类 Entry 及其子类型节点组成链表的能力。那么，LinkedHashMap 是怎样建立链表的呢？
LinkedHashMap重写了newNode()方法。 在这个方法中，LinkedHashMap 创建了 Entry，并通过 linkNodeLast 方法将 Entry 接在双向链表的尾部，实现了双向链表的建立。
remove()
删除有两重含义:
- 从table的角度看，需要将该entry从对应的bucket里删除，如果对应的冲突链表不空，需要修改冲突链表的相应引用。
- 从header的角度来看，需要将该entry从双向链表中删除，同时修改链表中前面以及后面元素的相应引用。
LinkedHashMap 删除操作相关的代码也是直接用父类的实现。在删除节点时，父类的删除逻辑并不会修复 LinkedHashMap 所维护的双向链表，这不是它的职责。那么删除及节点后，被删除的节点该如何从双链表中移除呢？当然，办法还算是有的， HashMap 中三个回调方法运行 LinkedHashMap 对一些操作做出响应。所以，在删除及节点后，回调方法 afterNodeRemoval 会被调用。LinkedHashMap 覆写该方法，并在该方法中完成了移除被删除节点的操作。相关源码如下：
ini
// HashMap 中实现
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
// HashMap 中实现
final Node<K,V> 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) {...}
else {
// 遍历单链表，寻找要删除的节点，并赋值给 node 变量
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) {...}
// 将要删除的节点从单链表中移除
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node); // 调用删除回调方法
return node;
}
}
return null;
}
// LinkedHashMap 中覆写
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// 将 p 节点的前驱后后继引用置空
p.before = p.after = null;
// b 为 null，表明 p 是头节点
if (b == null)
head = a;
else
b.after = a;
// a 为 null，表明 p 是尾节点
if (a == null)
tail = b;
else
a.before = b;
}
删除的过程并不复杂，上面这么多代码其实就做了三件事：
- 根据 hash 定位到桶位置
- 遍历链表或调用红黑树相关的删除方法
- 从 LinkedHashMap 维护的双链表中移除要删除的节点
举个例子说明一下，假如我们要删除下图键值为 3 的节点。
根据 hash 定位到该节点属于3号桶，然后在对3号桶保存的单链表进行遍历。找到要删除的节点后，先从单链表中移除该节点。如下：
然后再双向链表中移除该节点：
删除及相关修复过程并不复杂，结合上面的图片，大家应该很容易就能理解，这里就不多说了。
如何维护插入序和访问序？
在 LinkedHashMap 中，所有的 Entry 都被串联在一个双向链表中。每次在新建一个节点时都会将新建的节点链接到双向链表的末尾。这样从双向链表的尾部向头部遍历就可以保证插入顺序了，头部节点是最早添加的节点，而尾部节点则是最近添加的节点。那么，访问顺序要怎么实现呢？
之前我们在分析 HashMap 的源码的时候，在添加及更新、查找、删除等操作中可以看到 afterNodeAccess、afterNodeInsertion、afterNodeRemoval 等几个方法的调用，不过在 HashMap 中这几个方法中没有任何操作。实际上，这几个方法就是供 LinkedHashMap 的重写的，我们不妨看一下在 HashMap 中这几个方法的声明：
typescript
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
在 LinkedHashMap 中对这几个方法进行了重写：
ini
//移除节点的回调函数
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;
}
//插入节点的回调函数
//构造函数中调用，evict为false
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
//first是头元素，也是最老的元素
//在插入序中，就是最先插入的元素
//在访问序中，就是最远被访问的元素
//这里removeEldestEntry(first)始终返回true，即不删除最老的元素
//如果是一个容量固定的cache，可调整removeEldestEntry(first)的实现
if (evict && (first = head) != null && removeEldestEntry(first)) {
//不是构造方法中
//头元素不为空
//要删除最老的元素
//在LinkedHashMap的实现中，不会进入这里
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
//访问节点的回调函数
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
//如果是访问序，且当前节点并不是尾节点
//将该节点置为双向链表的尾部
if (accessOrder && (last = tail) != e) {
//p 当前节点， b 前驱结点， a 后继结点
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null; //设为尾节点，则没有后继
if (b == null)
head = a; //p是头节点，调整后其后继结点变为头节点
else
b.after = a;//p不是头节点，前驱和后继结点相连
if (a != null)
a.before = b;
else
last = b;//应该不会出现这种情况，p是尾节点
if (last == null)
head = p;
else {
//将p置于尾节点之后
p.before = last;
last.after = p;
}
tail = p;//调整tail指向
++modCount;//结构性改变
}
}
在插入节点、删除节点和访问节点后会调用相应的回调函数。可以看到，在 afterNodeAccess 方法中，如果该 LinkedHashMap 是访问序，且当前访问的节点不是尾部节点，则该节点会被置为双链表的尾节点。即，在访问序下，最近访问的节点会是尾节点，头节点则是最远访问的节点。
在 afterNodeInsertion 中，如果 removeEldestEntry(first) 节点返回 true，则会将头部节点删除。如果想要实现一个固定容量的 Map，可以在继承 LinkedHashMap 后重写 removeEldestEntry 方法。在 LinkedHashMap 中，该方法始终返回 false。
typescript
//返回false
//是否移除最老的Entry
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
在 HashMap 中，在 putVal 和 removeNode 中都调用了相应的回调函数，而 get 则没有，因而在 LinkedHahsMap 中进行了重写：
kotlin
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;
}
遍历及迭代器
因为 LinkeHashMap 的所有的节点都在一个双向链表中，因而可以通过该双向链表来遍历所有的 Entry。而在 HashMap 中，要遍历所有的 Entry，则要依次遍历所有桶中的单链表。相比较而言，从时间复杂度的角度来看，LinkedHashMap 的复杂度为 O(size())，而 HashMap 则为 O(capacity + size())。
ini
//因为所有的节点都被串联在双向链表中，迭代器在迭代时可以利用双向链表的链接关系进行
//双向链表的顺序是按照插入序或访问序排列的
//相比于HashMap中的迭代，LinkedHashMap更为高效，O(size())
//HashMapde 迭代，O(capacity + size())
abstract class LinkedHashIterator {
LinkedHashMap.Entry<K,V> next;
LinkedHashMap.Entry<K,V> current;
int expectedModCount;
LinkedHashIterator() {
next = head;
expectedModCount = modCount;
current = null;
}
public final boolean hasNext() {
return next != null;
}
final LinkedHashMap.Entry<K,V> nextNode() {
LinkedHashMap.Entry<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
current = e;
next = e.after;
return e;
}
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}
可以看到，在遍历所有节点时是通过节点的 after 引用进行的。这样，可以双链表的头部遍历到到双链表的尾部，就不用像 HahsMap 那样访问空槽了。
在 containsValue 和 internalWriteEntries 中也使用了双向链表进行遍历。
java
public boolean containsValue(Object value) {
//使用双向链表进行遍历
for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
V v = e.value;
if (v == value || (value != null && value.equals(v)))
return true;
}
return false;
}
//覆盖父类方法
//序列化，Called only from writeObject, to ensure compatible ordering.
void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
//调整元素的遍历方式，使用双链表遍历
for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
s.writeObject(e.key);
s.writeObject(e.value);
}
}
LinkedHashMap经典用法
在LinkedHashMap中，如果顺行性机制选择“按访问顺序”，那么当元素被访问时，元素会默认被放到链表的尾部，并且在向LinkedHashMap添加元素时会调用afterNodeInsertion方法。这个方法的具体实现代码如下：
从代码中可以看出，如果removeEldestEntry函数返回true，则会删除LinkedHashMap中的第一个元素，这样就淘汰了旧的数据，实现了LRU的效果。removeEledestEntry方法的代码如下：
可以看到，默认返回的是false，表示LinkedHashMap并不会启用节点的淘汰机制。为了实现LRU算法，我们需要继承LinkedHashMap并重写该方法，具体实现代码如下：
scala
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int maxCapacity;
public LRUCache(int maxCapacity) {
super(maxCapacity, 0.75f, true);
this.maxCapacity = maxCapacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
//如果超过了最大容量，则启动剔除机制
return size() > maxCapacity;
}
}
arduino
public class LRUCacheTest {
public static void main(String[] args) {
LRUCache<String, String> cache = new LRUCache<>(5);
for (int i = 0; i < 10; i++) {
cache.put(String.valueOf(i), String.valueOf(i * i));
}
System.out.println("插入10个键值对后，缓存内容：");
System.out.println(cache + "n");
System.out.println("访问键值为7的节点后，缓存内容：");
cache.get("7");
System.out.println(cache + "n");
System.out.println("插入键值为11的键值对后，缓存内容：");
cache.put(String.valueOf(11), String.valueOf(11 * 11));
System.out.println(cache);
}
}
ini
插入10个键值对后，缓存内容：
{5=25, 6=36, 7=49, 8=64, 9=81}
访问键值为7的节点后，缓存内容：
{5=25, 6=36, 8=64, 9=81, 7=49}
插入键值为11的键值对后，缓存内容：
{6=36, 8=64, 9=81, 7=49, 11=121}
评论