一、前言
LinkedHashMap 继承于 HashMap,因此,建议在学习本篇内容前,先学习 HashMap系列,这样使得更加容易理解。
HashMap系列
(一)HashMap系列:负载因子0.75
(二)HashMap系列:树化阀值8,退化阀值6
(三)HashMap系列:2次方扩容
(四)HashMap系列:put元素(不看完将后悔一生!)
二、LinkedHashMap使用
可能很多人会说,LinkedHashMap谁不会用?你真的确定你会用?
上例子之前,先写几个工具方法,以便后面理解方便:
public class Main {
// 字符串左对齐(未考虑中英文长度,仅便于观看)
private static String spaceFill(Object object) {
return String.format("%-20s", object);
}
// 反射获取 HashMap 中的数组对象
// 啥?你不知道数组对象名称?
// 建议去看看源码,或是看看我写的 HashMap 系列
private static Map.Entry<Integer, String>[] getArray(Object object, Field field) throws Exception {
return (Map.Entry<Integer, String>[]) field.get(object);
}
// 反射获取 Map.Entry
// 因为 HashMap.Node 是私有静态类
private static Map.Entry<Integer, String> getObject(Object object, String name) throws Exception {
Field field = getField(object.getClass(), name);
return (Map.Entry<Integer, String>) field.get(object);
}
// 反射获取指定字段
private static Field getField(Class<?> clazz, String name) {
if (clazz == null) {
return null;
}
Field field = null;
try {
field = clazz.getDeclaredField(name);
field.setAccessible(true);
} catch (NoSuchFieldException e) {
field = getField(clazz.getSuperclass(), name);
}
return field;
}
}
好了,上面的工具方法已经完成,后面的所有例子都会使用上面的方法。
我们来看两个例子:
2.1、例子一
public class Main {
public static void main(String[] args) {
// 一般大家都使用默认构造函数
LinkedHashMap<Integer, String> map = new LinkedHashMap<>();
map.put(1, "chris");
map.put(2, "qingye");
map.put(3, "24854015@qq.com");
// 反射获取 table 数组对象
Field field = getField(map.getClass(), "table");
if (field != null && field.getType().isArray()) {
try {
// 类型强转
Map.Entry<Integer, String>[] table = getArray(map, field);
for (int i = 0; i < table.length; i ++) {
if (table[i] != null) {
// LinkedHashMap.Node 特有的 before & after 指针
Map.Entry<Integer, String> before = getObject(table[i], "before");
Map.Entry<Integer, String> after = getObject(table[i], "after");
if (before == null) {
System.out.print("This is Head ");
} else if (after == null) {
System.out.print("This is Tail ");
} else {
System.out.print("\t\t\t ");
}
System.out.println("[" + i + "] => " + spaceFill(table[i]) + ", before => " + spaceFill(before) + ", after => " + spaceFill(after));
}
}
} catch (Exception e) {
}
}
}
}
输出结果:
This is Head [1] => 1=chris , before => null , after => 2=qingye
[2] => 2=qingye , before => 1=chris , after => 3=24854015@qq.com
This is Tail [3] => 3=24854015@qq.com , before => 2=qingye , after => null
2.2、例子二
public class Main {
public static void main(String[] args) {
// 指定构造函数来初始化
LinkedHashMap<Integer, String> map = new LinkedHashMap<>(16, 0.75f, true);
map.put(1, "chris");
map.put(2, "qingye");
map.put(3, "24854015@qq.com");
map.get(1); // 注意:这里仅仅 get 了一下
Field field = getField(map.getClass(), "table");
if (field != null && field.getType().isArray()) {
try {
Map.Entry<Integer, String>[] table = getArray(map, field);
for (int i = 0; i < table.length; i ++) {
if (table[i] != null) {
Map.Entry<Integer, String> before = getObject(table[i], "before");
Map.Entry<Integer, String> after = getObject(table[i], "after");
if (before == null) {
System.out.print("This is Head ");
} else if (after == null) {
System.out.print("This is Tail ");
} else {
System.out.print("\t\t\t ");
}
System.out.println("[" + i + "] => " + spaceFill(table[i]) + ", before => " + spaceFill(before) + ", after => " + spaceFill(after));
}
}
} catch (Exception e) {
}
}
}
}
输出结果:
This is Tail [1] => 1=chris , before => 3=24854015@qq.com , after => null
This is Head [2] => 2=qingye , before => null , after => 3=24854015@qq.com
[3] => 3=24854015@qq.com , before => 2=qingye , after => 1=chris
WTF ?!发生了啥?怎么[1]元素从『Head』变成了『Tail』?
这就是 LinkedHashMap 的其妙之处!
三、深入解读 LinkedHashMap 的奥秘
3.1、LinkedHashMap 与 HashMap 的关系
本篇开头也说了,前者继承于后者,因此,LinkedHashMap 的 putXXX 和 getXXX 都直接继承于 HashMap,并没有重载,其 put & get 的逻辑也就和 HashMap 一样。HashMap 的 put & get 是啥逻辑?如果大家忘记了,建议去看看我写的《HashMap系列:put元素》。既然是继承,同样的,它们的数组结构也就几乎一致(99%的一致):
数据结构:数组 + 链表 <---> 红黑树
那 1% 的不一致在哪?
3.2、Map.Entry
HashMap 的节点实现了 Map.Entry:
public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
那 LinkedHashMap的节点呢?
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
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 !
3.3、HashMap.TreeNode
之前再讲 HashMap 时,并没有提到 TreeNode 这个类型,因为涉及到 LinkedHashMap,所以有所调整,这里进行补充:
public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}
完美的继承:
Entry-Node.png3.4、before & after
根据这两个字段的名称,我们就能很容易的猜测出,分别指向前一个节点和后一个节点(事实上,我们开头的两个例子,已经证实了这种关系),那么,具体是如何在数据结构或者说,节点对象上表现出关联关系的呢?
LinkedHashMap.png画图很辛苦......
LinkedHashMap 之所以加了 before 与 after 节点索引,主要目的:
- 双向链表(即可以双向访问),从头结点可以一直遍历到最后一个节点,而不需要中途定位到桶;
- 可以按照插入顺序来访问(默认),【例子一】;
四、LinkedHashMap 特殊之处
/**
* The iteration ordering method for this linked hash map: true for access-order, false for insertion-order.
*/
final boolean accessOrder;
该字段含义:
- true时,遍历双向链表中元素是按照访问顺序来遍历(LRU);
- false时,遍历双向链表中的元素是按照插入顺序来遍历(默认);
Android系统中的 LRU 的实现,其实就是基于 LinkedHashMap,并采用了【例子二】的方式来初始化对象实例。
五、LinkedHashMap索引的源码实现
我们同样从 put元素还是分析源码,还记得我们分析 HashMap 的 putVal 时,有两个空函数么?
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
......
else {
......
if (e != null) { // 元素已经存在
......
afterNodeAccess(e); // 调整节点顺序
return oldValue;
}
}
......
afterNodeInsertion(evict); // 新增元素,调整节点顺序
return null;
}
}
5.1、LinkedHashMap.afterNodeAccess
该方法会被多个其它方法触发,例如:put一个已存在的节点对象,get对象,replace对象等等,该方法就是判断是否需要调整的遍历访问顺序。
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// accessOrder = true,表示 LRU
// 将要移动的节点已经在最后一个,那么就不用调整了
if (accessOrder && (last = tail) != e) {
// p 指向 e本身,b 指向 e前一个,a 指向 e后一个
LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
// 如果 e的前一个为null,表示 e 是头节点,那么将头节点指向 e的下一个元素
if (b == null)
head = a;
else
b.after = a; // 否则 e的上一个元素,其下一个指向从 e 改为 e的下一个
// a 为null 则表示 e 是尾节点
// 否则将 e的下一个元素,其上一个指向从 e 改为 e的上一个
if (a != null)
a.before = b;
else
last = b; // 否则,尾节点指向 e 的上一个元素
// 总之,上面判断:b,a 不为null,则互指
// 如果 last 为null,则表示整个 LinkedHashMap 只有一个元素
if (last == null)
head = p;
else {
// 否则,将 p 移至最后一个(访问顺序上,即逻辑上最后一个,实际位置不会变)
p.before = last;
last.after = p;
}
tail = p; // 最后,尾指向最后一个元素
++modCount;
}
}
}
5.2、LinkedHashMap.afterNodeInsertion
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
// 新增节点后,调用此方法判断是否需要移除最老的节点
// 因为 accessOrder = true 时,访问次数多的节点一定是在链尾,而访问次数最少的则在链头
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
// 如果需要移除最老的,则先从链头开始移除
// 移除节点,调用的是 HashMap.removeNode 方法
// 同样是从数组开始,再红黑树,再链表查找,删除,调整
removeNode(hash(key), key, null, false, true);
}
}
}
5.3、LinkedHashMap.removeEldestEntry
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
// 该方法在 LinkedHashMap 中,默认返回 false,即不移除最老的元素
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
}
那为啥我还一直提到 LRU 呢?
因为,我们如果自己基于 LinkedHashMap 来实现 LRU,就可以重载此方法,返回 true ,这样就达到了 LRU 的效果。
好了,LinkedHashMap 就聊到这里!
网友评论