十一、Map 子接口之 LinkedHashMap
11.1 LinkedHashMap
在日常开发中，我们使用频率最高的键值对集合应该就是 HashMap 了，但是它也有不足之处。比如现在我需要一个按照插入顺序来排列的键值对集合，显然 HashMap 就无能为力了。
为了提高查找效率，HashMap 在插入的时候对键做了一次哈希算法，这就导致插入的元素是无序的：
i = (n - 1) & hash;
按照这个公式计算后的值并不是按照 0、1、2、3、4 这样有序的下标将键值对插入到数组当中的，而具有一定的随机性。
LinkedHashMap 继承了 HashMap，可以实现键值对按照顺序插入：
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{}
另外，LinkedHashMap 内部又追加了双向链表，来维护元素的插入顺序。其中的 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);
}
}
11.2 插入顺序
在 HashMap 中，无论 null 值在第几次被插入，它都会插入到 HashMap 的第一位：
/**
* @author QHJ
* @date 2022/11/1 10:44
* @description: HashMapTest
*/
public class LinkedHashMapTest {
public static void main(String[] args) {
Map<String, String> hashMap = new HashMap<>();
hashMap.put("1", "青花椒");
hashMap.put("2", "张三");
hashMap.put("3", "李四");
hashMap.put(null, null);
for (String key : hashMap.keySet()) {
System.out.println(key + ":" + hashMap.get(key));
}
}
}
程序执行结果：
null:null
1:青花椒
2:张三
3:李四
从结果可以看出，虽然 null 是最后一个被 put 进去的，但是在遍历输出的时候是在第一位的。
对比一下 LinkedHashMap：
/**
* @author QHJ
* @date 2022/11/1 10:44
* @description: LinkedHashMapTest
*/
public class LinkedHashMapTest {
public static void main(String[] args) {
LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("1", "青花椒");
linkedHashMap.put("2", "张三");
linkedHashMap.put("3", "李四");
linkedHashMap.put(null, null);
for (String key : linkedHashMap.keySet()) {
System.out.println(key + ":" + linkedHashMap.get(key));
}
}
}
程序执行结果：
1:青花椒
2:张三
3:李四
null:null
null 在最后一位插入，就在最后一位输出。这就证明，HashMap 是无序的，LinkedHashMap 是可以维持插入顺序的。
扒 LinkedHashMap 的源码就会发现，它并没有重写 HashMap 的 put() 方法，而是重写了 put() 方法里面需要调用的 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;
}
在上面的介绍中我们知道，LinkedHashMap.Entry 继承了 HashMap.Node，并且追加了两个字段 before 和 after。然后来扒一下 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;
}
}
在添加第一个元素的时候，会把 head 赋值为第一个元素，等到第二个元素添加进来的时候，会把第二个元素的 before 赋值给第一个元素，第一个元素的 after 赋值为第二个元素。这样就保证了键值对是按照顺序排列的。
11.3 访问顺序
LinkedHashMap 不仅能够维持插入顺序，还能够维持访问顺序。访问包括调用 get() 方法、remove() 方法和 put() 方法。
要维护访问顺序的话，就需要我们在声明 LinkedHashMap 的时候指定三个参数（初始容量、负载因子、是否指定访问顺序）：
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
如果第三个参数指定为 true 的话，就表示 LinkedHashMap 要维护访问顺序；否则，维护插入顺序。默认是 false。
/**
* @author QHJ
* @date 2022/11/1 10:44
* @description: LinkedHashMapTest
*/
public class LinkedHashMapTest {
public static void main(String[] args) {
LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<>(16, 0.75f, true);
linkedHashMap.put("1", "青花椒");
linkedHashMap.put("2", "张三");
linkedHashMap.put("3", "李四");
linkedHashMap.put(null, null);
System.out.println(linkedHashMap); // {1=青花椒, 2=张三, 3=李四, null=null}
linkedHashMap.get("2");
System.out.println(linkedHashMap); // {1=青花椒, 3=李四, null=null, 2=张三}
linkedHashMap.get("1");
System.out.println(linkedHashMap); // {3=李四, null=null, 2=张三, 1=青花椒}
}
}
当我使用 get() 方法访问键位 “2” 的元素后，输出结果中 “2=张三” 在最后；当我使用 get() 方法访问键位 “1” 的元素后，输出结果中 “1=青花椒” 在最后，“2=张三” 在倒数第二位。
也就是说，最不经常访问的放在头部。
我们可以使用 LinkedHashMap 来实现 LRU 缓存，LRU 是 Least Recently Used 的缩写，即最近最少使用，也是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。
自定义一个 MyLinkedHashMap 类，让它继承 LinkedHashMap，并且重写 removeEldestEntry() 方法——使 Map 最多可容纳 5 个元素，超出后就淘汰：
/**
* @author QHJ
* @date 2022/11/1 16:36
* @description: MyLinkedHashMap
*/
public class MyLinkedHashMap<K, V> extends LinkedHashMap<K, V> {
private static final int MAX_ENTRIES = 5;
public MyLinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor, accessOrder);
}
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_ENTRIES;
}
}
测试类：
/**
* @author QHJ
* @date 2022/11/1 16:39
* @description: MyLinkedHashMapTest
*/
public class MyLinkedHashMapTest {
public static void main(String[] args) {
MyLinkedHashMap<String, String> map = new MyLinkedHashMap<>(16, 0.75f, true);
map.put("1", "青花椒");
map.put("2", "张三");
map.put("3", "李四");
map.put("4", "王五");
map.put(null, null);
System.out.println(map); // {1=青花椒, 2=张三, 3=李四, 4=王五, null=null}
map.put("beautiful", "美丽的程序猿");
System.out.println(map); // {2=张三, 3=李四, 4=王五, null=null, beautiful=美丽的程序猿}
map.put("cool", "酷酷的程序猿");
System.out.println(map); // {3=李四, 4=王五, null=null, beautiful=美丽的程序猿, cool=酷酷的程序猿}
}
}
由程序执行结果可以看出来，“1=青花椒” 和 “2=张三” 依次被淘汰出局。
那 LinkedHashMap 是如何来维持访问顺序的呢？主要就是依靠这三个方法：
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
afterNodeAccess() 会在调用 get() 方法的时候被调用，afterNodeInsertion() 会在调用 put() 方法的时候被调用，afterNodeRemoval() 会在调用 remove() 方法的时候被调用。
扒一下 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;
}
}
afterNodeAccess() 方法其实就是哪个元素被 get 就把哪个元素放在最后。
在插入元素的时候，需要调用 put() 方法，该方法最后会调用 afterNodeInsertion() 方法，这个方法被 LinkedHashMap 重写了：
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);
}
}
removeEldestEntry() 方法会判断第一个元素是否超过了可容纳的最大范围。如果超出，就会调用 removeNode() 方法对最不经常访问的那个元素进行删除。
在主动调用 remove() 方法进行删除的时候，会调用 removeNode() 方法，removeNode() 方法里会继续调用 afterNodeRemoval() 方法：
public final boolean remove(Object key) {
return removeNode(hash(key), key, null, false, true) != null;
}
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;
}
由于 LinkedHashMap 要维护双向链表，所以在插入、删除操作的时候，花费的时间要比 HashMap 多一些。
