序
这周感觉有点堕落，晚上都没怎么好好利用，看B站，突然还玩起了游戏，哎，视频真好看，游戏真好玩。
每天最少一个小时的学习时间，好不容易养成的习惯，可不能贪玩丢弃了。自勉，今天看了几期《棋魂》，下围棋动辄好几年都在练习，职业选手更是天天就是对着棋盘，这份毅力，热爱真是令人惊叹。
概述
LinkedHashMap 继承了 HashMap,具备 HashMap 的所有功能，不同点是，LinkedHashMap 还维护了一个双向链表，这个链表决定了迭代顺序。可以是插入的顺序和访问顺序。
可以查看前篇剖析Java 集合框架(二)-HashMap
本篇源码基于JDK 1.8
数据结构
LinkedHashMap
类的申明和成员属性
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
// 双向链表的头结点
transient LinkedHashMap.Entry<K,V> head;
// 双向链表的尾节点
transient LinkedHashMap.Entry<K,V> tail;
// 双向链表顺序 是否为访问顺序 默认false
final boolean accessOrder;
还是HashMap那套数据结构，只是每个 entry 节点还是有 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);
}
}
默认情况下，before 和 after 维护的就是插入顺序。
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);
linkNodeLast(p);
return p;
}
// 把新创建的节点 放到链表的最后
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;
}
}
理解LinkedHashMap 源码基本思路就是--多态，重写。LinkedHashMap重写了大量HaspMap的方法。
初始化
列出两个代表，默认构造方法 和 最多参数构造方法,可以发现双向链表的顺序默认为插入顺序,而且自身没做什么，全都都是调用的 HashMap 的方法
public LinkedHashMap() {
super();
accessOrder = false;
}
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
添加元素
在IDEA里Ctrl+F3或者Ctrl+O 可以调出该类的所有方法，可以发现LinkedHashMap没有put方法，所以肯定调用的 HashMap 的 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)
// LinkedHashMap 重写了
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;
// LinkedHashMap 重写了
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
// LinkedHashMap 重写了
afterNodeInsertion(evict);
return null;
}
着重注意 newNode,afterNodeAccess,afterNodeInsertion这几个方法, LinkedHashMap 都重写了这些方法，所以实际调用的是LinkedHashMap的方法。
newNode方法在前面已经分析过了，现在先分析 afterNodeAccess:
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// 如果是访问顺序 并且双向链表的尾节点不是传入的节点
// 这将e节点移动到双向链表的最后
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;
}
}
这个方法通过名称也能看出一二，访问节点之后。如果是双向链表的顺序为访问顺序，所以每一层访问节点，都需要把节点移动到链表最后。
再来分析 afterNodeInsertion,插入之后的逻辑
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默认返回false,这是实现LUR算法的关键，我们自己重写这个方法，逻辑为：map里的元素个数大于某个值时返回true。则会执行移除双向链表的操作。
removeNode是 HaspMap里面的方法,删除元素.需要注意的是，里面调用了 afterNodeRemoval方法，而该方法LinkedHashMap也重写了:
// 将e从双向链表中移除
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;
}
一个put方法几乎把所有操作都覆盖了，过程大体如下：
- 通过key的hash定位到桶的位置。
- 如果key已存在，直接替换value。并访问 LinkedHashMap的
afterNodeAccess方法，如果双向链表的顺序为访问顺序，则讲元素移动到链表尾部。 - 如果key不存在：
- 使用 LinkedHashMap的
newNode方法创建节点，并把改节点添加到双向链表的尾部。 -
LinkedHashMap.
afterNodeInsertion方法 和removeEldestEntry方法 判断是否移除掉双向链表的头结点。
- 使用 LinkedHashMap的
其他方法
其他方法基本都是调用 HashMap 方法和上面分析的方法。比如 get,先获取到元素，然后判断是否执行afterNodeAccess，删除方法类似。
LUR 算法
我们用 LinkedHashMap实现一个LUR淘汰策略算法实例。
class LRUCache<K, V> extends LinkedHashMap<K, V> {
private static final int MAX_SIZE = 10;
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_SIZE;
}
LRUCache() {
super(MAX_SIZE, 0.75f, true);
}
}
可以看到代码就几行，就实现最近最久未使用淘汰策略算法。
- 继承了 LinkedHashMap，构造方法将
accessOrder设置为 true，开启访问顺序。 - 最大容量
MAX_SIZE限制为10个。 - 重写了removeEldestEntry方法，当前map里的容量大于
MAX_SIZE时触发移除头结点方法。
当然也可以不用集成 LinkedHashMap实现，就是一个HashMap+linkedList。
总结
LinkedHashMap保证了元素有序(插入顺序/访问顺序)，有序是通过双向链表实现的，链表的元素即为HashMap的节点，只是多了两个前后驱节点属性。维护数据时之后使用HashMap 的方法，维护顺序时，通过 HashMap 的方法定位到元素之后再通过前后驱属性操作链表。实现了插入，删除，访问时维护顺序也能控制在O(1)时间复杂度。
量变引发质变，经常进步一点点，期待蜕变的自己。
网友评论