懂LruCache？你必须先懂LinkedHashMap，顺带给
2019-11-22 本文已影响0人
酱爆大头菜
上一篇 LruCache缓存机制，深入浅出，发现了一个源码bug 中我们介绍了LruCache的使用和原理，同时也提到了LruCache本质就是在维护一个LinkedHashMap，具体为什么是LinkedHashMap而不是其他对象，我们通过以下几个问题来解释原因。
-
1. LinkedHashMap是个什么东西？
-
2. LinkedHashMap是干什么用的？
-
3. LinkedHashMap怎么用？
-
4. LinkedHashMap的原理是什么？怎么实现的?
1.LinkedHashMap是个什么东西？
-
LinkedHashMap是一个继承于HashMap，实现Map接口且有可预知迭代顺序的键值对存储列表。与HashMap的不同之处在于LinkedHashMap多维护了一个所有键值对的双向链表，而这个双向链表就定义了迭代顺序，和访问顺序。
-
简单来说就是：LinkedHashMap = HashMap + 双向链表。
2. LinkedHashMap是干什么用的？
- LinkedHashMap主要用于需要知道访问顺序的场景，比如LruCache中，需要按put顺序或者访问时间顺序进行数据维护。又或者需要使用定长的缓存。
3. LinkedHashMap怎么用？
- 我们先看一个LinkedHashMap普通使用的例子
例 1
public class LinkedHashMapActivity extends AppCompatActivity {
LinkedHashMap<Integer, Integer> linkedHashMap;
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_linked_hash_map);
linkedHashMap = new LinkedHashMap<Integer, Integer>(2);
linkedHashMap.put(1, 1);
linkedHashMap.put(2, 2);
linkedHashMap.put(3, 3);
for (Map.Entry<Integer, Integer> a : linkedHashMap.entrySet()) {
Log.e("TAG", "key->" + a.getKey() + "");
Log.e("TAG", "value->" + a.getValue() + "");
}
}
}
2019-11-21 14:32:17.332 3310-3310/com.we.we E/TAG: key->1
2019-11-21 14:32:17.333 3310-3310/com.we.we E/TAG: value->1
2019-11-21 14:32:17.333 3310-3310/com.we.we E/TAG: key->2
2019-11-21 14:32:17.333 3310-3310/com.we.we E/TAG: value->2
2019-11-21 14:32:17.333 3310-3310/com.we.we E/TAG: key->3
2019-11-21 14:32:17.333 3310-3310/com.we.we E/TAG: value->3
- 其实普通的使用中LinkedHashMap和HashMap没有任何不同，都是实例化后进行put数据，而初始化时我们设置的初始容量是2，但是put了三个数据，实际打印的结果也是3条数据，因此初始化的2并不代表LinkedHashMap的最大容量。
- 那LinkedHashMap和HashMap到底有什么不同？我们再看一个例子
例 2
public class LinkedHashMapActivity extends AppCompatActivity {
LinkedHashMap<Integer, Integer> linkedHashMap;
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_linked_hash_map);
linkedHashMap = new LinkedHashMap<Integer, Integer>(2) {
@Override
protected boolean removeEldestEntry(Entry eldest) {
return linkedHashMap.size() > 2;
}
};
linkedHashMap.put(1, 1);
linkedHashMap.put(2, 2);
linkedHashMap.put(3, 3);
for (Map.Entry<Integer, Integer> a : linkedHashMap.entrySet()) {
Log.e("TAG", "key->" + a.getKey() + "");
Log.e("TAG", "value->" + a.getValue() + "");
}
}
}
2019-11-21 14:34:17.708 3421-3421/com.we.we E/TAG: key->2
2019-11-21 14:34:17.708 3421-3421/com.we.we E/TAG: value->2
2019-11-21 14:34:17.708 3421-3421/com.we.we E/TAG: key->3
2019-11-21 14:34:17.708 3421-3421/com.we.we E/TAG: value->3
- 和第一个例子相比，在LinkedHashMap实例化的过程中，重写了removeEldestEntry()方法，并根据当前linkedHashMap.size()和设置容量的判断结果返回数据，明明put了3条数据，打印却只打印了最后put的2条，这一结果证实了2点.
- LinkedHashMap的容量是可控的。
- LinkedHashMap是有插入顺序的。
- 那LinkedHashMap访问有序是怎么体现的呢？是直接调用get()方法就会自动排序么？我们写代码测试一下。
例 3
public class LinkedHashMapActivity extends AppCompatActivity {
LinkedHashMap<Integer, Integer> linkedHashMap;
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_linked_hash_map);
linkedHashMap = new LinkedHashMap<Integer, Integer>(2) {
@Override
protected boolean removeEldestEntry(Entry eldest) {
return linkedHashMap.size() > 2;
}
};
linkedHashMap.put(1, 1);
linkedHashMap.put(2, 2);
//调用get进行排序
linkedHashMap.get(1);
for (Map.Entry<Integer, Integer> a : linkedHashMap.entrySet()) {
Log.e("TAG", "key->" + a.getKey() + "");
Log.e("TAG", "value->" + a.getValue() + "");
}
}
}
2019-11-21 14:55:08.481 3843-3843/com.we.we E/TAG: key->1
2019-11-21 14:55:08.481 3843-3843/com.we.we E/TAG: value->1
2019-11-21 14:55:08.481 3843-3843/com.we.we E/TAG: key->2
2019-11-21 14:55:08.481 3843-3843/com.we.we E/TAG: value->2
- 还是以上的例子，我们在put完以后调用了get(1)再打印日志发现并没有按我们预想的顺序将1放在最后，因为LinkedHashMap按访问顺序排序默认是关闭的，可通过构造函数实例化的时候打开。比如这样：
例 4
public class LinkedHashMapActivity extends AppCompatActivity {
LinkedHashMap<Integer, Integer> linkedHashMap;
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_linked_hash_map);
//主要看最后这个参数，默认是false。
linkedHashMap = new LinkedHashMap<Integer, Integer>(2,0.75f,true) {
@Override
protected boolean removeEldestEntry(Entry eldest) {
return linkedHashMap.size() > 2;
}
};
linkedHashMap.put(1, 1);
linkedHashMap.put(2, 2);
//调用get进行排序
linkedHashMap.get(1);
for (Map.Entry<Integer, Integer> a : linkedHashMap.entrySet()) {
Log.e("TAG", "key->" + a.getKey() + "");
Log.e("TAG", "value->" + a.getValue() + "");
}
}
}
2019-11-21 15:07:46.672 4071-4071/com.we.we E/TAG: key->2
2019-11-21 15:07:46.672 4071-4071/com.we.we E/TAG: value->2
2019-11-21 15:07:46.672 4071-4071/com.we.we E/TAG: key->1
2019-11-21 15:07:46.672 4071-4071/com.we.we E/TAG: value->1
-
在初始化过程开启访问排序后，在通过日志发现，1已经排在的最后，达到了访问排序的效果。
-
以上的几个例子是LinkedHashMap的基本使用，但是具体为什么能达到这种效果，接下来我们深入源码了解LinkedHashMap的原理。
4. LinkedHashMap的原理是什么？怎么实现的?
4.1. 首先我们了解LinkedHashMap的继承关系图,实线代表继承关系，虚线代表实现接口。
LinkedHashMap继承关系图.jpg
- 以上的继承关系中可以发现LinkedHashMap继承于HashMap，因此LinkedHashMap底层也是基于链表，如果JDK1.8以上就是链表+红黑树。
- 而LinkedHashMap的不同之处就在于它又多维护了一个双向链表。
4.2. LinkedHashMap的双向链表对象都包含什么属性？
- LinkedHashMap的双向链表对象是通过LinkedHashMapEntry对象来维护的，具体我们看下源码。
//LinkedHashMap.LinkedHashMapEntry
//继承于 HashMap.Node，获得普通链表的能力，同时通过内部属性 before, after;维护双向链表。
static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
//用来维护双向链表。
LinkedHashMapEntry<K,V> before, after;
LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
// HashMap.Node
// 链表元素对象
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
//元素的key
final K key;
//值value
V value;
//下一个元素的数据
Node<K,V> next;
...省略若干代码
}
// HashMap.TreeNode
//红黑树对象，主要看继承关系，如需了解内部逻辑可通过HashMap原理进行了解。
static final class TreeNode<K,V> extends LinkedHashMap.LinkedHashMapEntry<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);
}
}
- 以上源码中LinkedHashMapEntry就是LinkedHashMap中的每一个键值对对象，其中通过before, after两个属性维护了当前键值对的一前一后两个对象。以上源码的继承关系如下图所示：
LinkedHashMap.LinkedHashMapEntry继承关系图.jpg
补充一点小知识
- HashMap.TreeNode继承LinkedHashMap.LinkedHashMapEntry，而LinkedHashMap.LinkedHashMapEntry又继承HashMap.Node，那为什么 HashMap.TreeNode不直接继承HashMap.Node？绕这一圈为的是什么？
- 其实LinkedHashMapEntry有组成双向链表的能力，继承了它就获得了这个能力，但是TreeNode 就多了两个用不到的引用 (LinkedHashMapEntry<K,V> before, after;)；同时内存占用也会比较大，这么做是为啥？
- 官方解释是说TreeNode是Node内存占用的2倍左右，但是TreeNode是在HashMap的桶中的节点足够多的时候才会使用，（JDK1.8 当一个桶中的元素超过8才会转换为红黑树（TreeNode），<6又转回链表（Node）） 如果hash算法不是很差的话TreeNode使用的几率是比较低的，因此浪费那一点空间换取了组成双向链表的能力是值得的。
- 如果TreeNode直接 extends Node 则需要Node extentds LinkedHashMapEntry，Node使用是很频繁的，这样空间浪费的就太多了。
4.3. LinkedHashMap对象是怎么维护每一个双向链表对象的?
- 既然LinkedHashMap内的每一个元素都包含其前后两个元素对象，那必然在put对象的过程中就进行了维护，因此我们先看下LinkedHashMap.put方法。
- 因为LinkedHashMap继承于HashMap，并且LinkedHashMap没有重写put()，因此调用的就是父类HashMap的put，我们看下源码。
//HashMap的put()方法，同时也是LinkedHashMap的put方法
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)
//调用了newNode()方法，这里用到了一个面向对象里多态的特性，而LinkedHashMap重写了newNode()方法
//如果是LindedHashMap对象调用，触发的是LinkedHashMap重写的newNode()
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;
}
}
//有重复的key，则用待插入值进行覆盖，返回旧值。
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//HashMap中该方法没做任何操作，LinkedHashMap进行了重写实现，并调用。
//该方法主要将当前节点移动到双向链表尾部，后续进行详细分析
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
//每次put新元素都会调用（如果是更新已有元素则不调用，因为没有新增元素，不会导致size+1）
//但是HashMap中该方法没做任何操作, LinkedHashMap进行了重写实现.
//主要用于移除最早的元素，后续详细解析
afterNodeInsertion(evict);
return null;
}
//HashMap内的newNode
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
//LinkedHashMap重写的newNode
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
//构造带双向链表属性的对象。
LinkedHashMapEntry<K,V> p =
new LinkedHashMapEntry<K,V>(hash, key, value, e);
//双向链表维护
linkNodeLast(p);
return p;
}
private void linkNodeLast(LinkedHashMapEntry<K,V> p) {
//首先获取当前链表的最后一个元素
LinkedHashMapEntry<K,V> last = tail;
//当前插入的元素定义为最后一个元素
tail = p;
if (last == null)
//如果之前的最后元素是null，说明之前的链表就是空的，所以当前的元素是一个元素。
head = p;
else {
//如果之前的链表不是null
//put前的最后一个元素设置为当前put元素的前一个。
p.before = last;
//当前put元素设置为put前最后一个元素的下一个
last.after = p;
}
}
- 源码有点长，可以直接看我注释部分，注释部分完全可以描述新增键值对时双向链表的维护细节了
- 其实以上的大段逻辑做的事很简单。
-
1. 先创建新的元素，通过hash计算位置并存放。
-
2. 每次newNode创建元素时都连带调用linkNodeLast()将新插入元素的双向链表关系维护起来（新插入的放末尾）。
-
3. 每次put新元素均通过LinkedHashMap中重写的afterNodeInsertion()判断是否删除头节点元素。
-
//这个方法是在HashMap的代码里调用的，在put方法中调用的时候参数evict传的是true
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMapEntry<K,V> first;
//evict是true，(first = head)=true,而removeEldestEntry()方法默认返回的是false，因此if内的逻辑默认是不执行的。
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
//移除链表头部的元素
removeNode(hash(key), key, null, false, true);
}
}
//HashMap中的removeNode方法，主要用于删除某一个元素
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;
...省略若干代码
}
- 通过以上代码发现，其实每次调用afterNodeInsertion()方法，只是内部的if判断中removeEldestEntry()默认返回false ，因此移除链表头部元素的逻辑没能执行，但是可通过重写removeEldestEntry()方法手动返回true,这样可以做到每添加一个元素都移除头部的元素。
- 4. 如果put的key已存在则用新值覆盖并调用LinkedHashMap重写的afterNodeAccess()将新值移动到链表尾部。
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMapEntry<K,V> last;
//accessOrder 是LinkedHashMap实例化的时候的入参，需手动传true该方法的逻辑才会启用。
if (accessOrder && (last = tail) != e) {
LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
//p为当前尾节点，因此p.after = null;
p.after = null;
//p.before==null，说明p以前是头节点，但是现在需要把p放在尾节点，则以前p.after就变成了头节点。
if (b == null)
head = a;
else
//原来的顺序是b <-> p <-> a...现在p需要移动到尾部，则就变成了b <-> a...... <->p
b.after = a;
if (a != null)
//原来a.before是p，现在p移动走了，那p.before就变成了a.before
a.before = b;
else
//如果之前p就是尾节点，则将last引用p.before
last = b;
if (last == null)
//如果原来尾节点是空，则说明当前链表只有一个节点，因此head引用p
head = p;
else {
//之前尾节点不为空，因为p移动到了最后，因此p.before引用原尾节点，原尾节点.after引用p
p.before = last;
last.after = p;
}
tail = p;
//计数器自增1
++modCount;
}
}
- 以上复杂的操作均是处理链表移动的各种异常情况，最终目的是将put的元素移动到链表末端。
- 注意：在afterNodeAccess()函数中，会修改modCount变量,迭代LinkedHashMap时，如果同时查询访问数据，也会导致fail-fast，因为迭代的顺序已经改变。
4.4. LinkedHashMap为什么调用get()就会触发排序?
- 以上例 4已经展示了调用get()排序的场景，如不记得例4的逻辑，可上翻查看。
- 老规矩吧，点看源码一顿瞅....
//LinkedHashMap重写的get方法
public V get(Object key) {
Node<K,V> e;
//getNode()调用是HashMap.getNode()
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
//哈哈哈，看到这我一下子就明白他怎么做的排序了。
afterNodeAccess(e);
return e.value;
}
- LinkedHashMap每次调用get方法，在结果返回前就触发了afterNodeAccess()，而afterNodeAccess()作用就是将当前元素移动到尾节点。
4.4. LinkedHashMap调用remove()后链表怎么维护?
- 首先我们猜下，如果是我们自己实现这个逻辑需要怎么操作？比如现在调用remove()，删了了链表中间的一个元素，应该怎么维护？
- 首先我们通过当前元素前后的元素获取前后节点，然后让前后节点做关联，但是需要注意首位节点。
- 如果LinkedHashMap重写了remove()则在重写的方法里实现逻辑，如果调用的是HashMap.remove()则需要有和afterNodeAccess()类似的after...()方法进行重写实现，且after...()方法需在remove()方法中调用。
- 我们验证下猜想是否正确。
//HashMap.remove()
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
//HashMap.removeNode（），核心的删除方法
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)
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;
++modCount;
--size;
//维护双向链表的after...（）方法，在HashMap中该方法是空方法。
afterNodeRemoval(node);
return node;
}
}
return null;
}
//LinkedHashMap重写的afterNodeRemoval()方法
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
//首先删除元素的前后节点引用置空
p.before = p.after = null;
if (b == null)
//如果当前元素的前节点是null，则证明当前元素原来是头节点。
//因此删除当前元素后，当前元素的后节点就变成了头节点。
head = a;
else
//如果前节点不为null，则前节点的after引用后节点。
b.after = a;
if (a == null)
//如果当前元素的后节点为null，则说明当前元素为尾节点，删除当前元素后，尾节点变成当前元素的前节点。
tail = b;
else
//尾节点不为null，尾节点的前节点引用删除元素的前节点。
a.before = b;
}
- 通过以上源码可见跟我们猜想一致，我们简单总结下。
- LinkedHashMap.remove()其实调用的是HashMap.remove()
- HashMap.remove()中调用了HashMap.removeNode()。
- HashMap.removeNode()中调用了afterNodeRemoval(),而LinkedHashMap中重写了afterNodeRemoval()，因此最终的维护链表逻辑是在LinkedHashMap.afterNodeRemoval()中。
至此，LinkedHashMap的继承关系，添加，获取，移除三大主要方法，以及内部的排序处理逻辑已经分析完了，HashMap凭借强大的设计模式，让LinkedHashMap重写了以下3个必要方法就基本实现了全部功能。
- void afterNodeAccess(Node<K,V> p) { }
- void afterNodeInsertion(boolean evict) { }
- void afterNodeRemoval(Node<K,V> p) { }
接下来我们针对一些LinkedHashMap的特性补充一点小知识。
- 1. LinkedHashMap的containsValue(）进行了重写，相对HashMap大幅度提升了性能。
//LinkedHashMap.containsValue()
public boolean containsValue(Object value) {
//循环查找所有键值对的中和value重复的数据
for (LinkedHashMapEntry<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;
}
//HashMap.containsValue()
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
//双重for循环查找数据
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
-
以上两个containsValue()方法中，LinkedHashMap针对的是链表循环，循环的是所有有效的数据，而HashMap中，是双重for循环，先循环桶，后循环每个桶的数据，双重for循环这一点效率就偏低，其次HashMap循环的是所有的桶，但并不是所有桶都有数据。
-
2. LinkedHashMap.LinkedHashIterator.nextNode()相对HashMap.HashIterator.nextNode()大幅度提升了性能。
// LinkedHashMap.LinkedHashIterator.nextNode()
final LinkedHashMapEntry<K,V> nextNode() {
LinkedHashMapEntry<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
current = e;
next = e.after;
return e;
}
//HashMap.HashIterator.nextNode()
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
//循环HashMap中给每一个桶
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
- 同样的道理，LinkedHashMap循环的是有效链表数据，HashMap循环了所有的桶，不管桶里有没有数据。
总结和一点小建议
- LinkedHashMap的各个维度已经分析完了，篇幅较长，如果你已经看到了这里，那么对LinkedHashMap就有了相对全面的了解，但是还是建议多写代码多测试，实践才是检验原理的唯一标准。
- 上篇 LruCache缓存机制，深入浅出，发现了一个源码bug 中提到LruCache本质就是在维护一个LinkedHashMap，且LruCache具备控制缓存大小的能力。其实上文提到的removeEldestEntry()方法就是移除最早元素的开关方法，只要重写该方法即可控制是否移除最早数据。但LruCache中并没有使用。而是通过每次put()连带调用trimToSize()方法进行了手动移除数据。其实这块可以做下改进。
