LinkedHashMap
LinkedHashMap概述
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
LinkedHashMap继承自HashMap，它的多种操作都是建立在HashMap操作的基础上的。同HashMap不同的是，LinkedHashMap维护了一个Entry的双向链表，保证了插入的Entry中的顺序。这也是Linked的含义。结构图如下：
加入插入顺序为key1，key2，key3，key4，那么就会维护一个红线所示的双向链表。
为了实现双向链表，LinkedHashMap中提供了如下的Entry：
/**
* LinkedHashMap中的node直接继承自HashMap中的Node。并且增加了双向的指针
*/
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);
}
}
如果可以说，LinkedHashMap=HashMap+双向链表
LinkedHashMap原理
主要元素
/**
* 头指针，指向第一个node
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* 尾指针，指向最后一个node
*/
transient LinkedHashMap.Entry<K,V> tail;
/**
* 一个条件变量，它控制了是否在get操作后需要将新的get的节点重新放到链表的尾部
* LinkedHashMap可以维持了插入的顺序，但是这个顺序不是不变的，可以被get操作打乱。
*
* @serial
*/
final boolean accessOrder;
其他的元素就是直接继承HashMap中的。
构造函数
/**
* Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
* with the specified initial capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
/**
* 构造一个空的，按插入序（accessOrder = false）的LinkedHashMap，使用默认初始大小和负载因子0.75
*
* @param initialCapacity the initial capacity
* @throws IllegalArgumentException if the initial capacity is negative
*/
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
/**
* 默认构造函数也是关闭了get改变顺序，使用插入序。
*/
public LinkedHashMap() {
super();
accessOrder = false;
}
/**
* Constructs an insertion-ordered <tt>LinkedHashMap</tt> instance with
* the same mappings as the specified map. The <tt>LinkedHashMap</tt>
* instance is created with a default load factor (0.75) and an initial
* capacity sufficient to hold the mappings in the specified map.
*
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException if the specified map is null
*/
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
/**
* 这个构造方法指定了accessOrder
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @param accessOrder the ordering mode - <tt>true</tt> for
* access-order, <tt>false</tt> for insertion-order
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
注意，构造函数如果不明确传入accessOrder的话，默认都是按插入序的。
维护链表的操作
维护链表主要使用三个方法。
afterNodeRemoval，afterNodeInsertion，afterNodeAccess。这三个方法的主要作用是，在删除，插入，获取节点之后，对链表进行维护。简单来说，这三个方法中执行双向链表的操作：
afterNodeRemoval
顾名思义，在节点remove操作后进行调用：
//在节点删除后，维护链表，传入删除的节点
void afterNodeRemoval(Node<K,V> e) { // unlink
//p指向待删除元素，b执行前驱，a执行后驱
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//这里执行双向链表删除p节点操作，很简单。
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
afterNodeAccess
//在节点被访问后根据accessOrder判断是否需要调整链表顺序
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
//如果accessOrder为false，什么都不做
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;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
//这里执行将p放到尾部
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;
//removeEldestEntry(first)默认返回false，所以afterNodeInsertion这个方法其实并不会执行
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
为什么不执行也可以呢，这个要到put操作的时候就能看出来了。
那么removeEldestEntry这个方法有什么用呢，看名字可以知道是删除最久远的节点，也就是head节点，这个方法实际是给我们自己扩展的。默认是没有用的，接下来实现LRU的代码中将可以看到它的作用。
get操作
LinkedHashMap重写了HashMap的get方法，如下：
/**
* 调用hashmap的getNode方法获取到值之后，维护链表
* @param key
* @return
*/
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;
}
这个方法的实现简单易懂。
put操作
LinkedHashMap没有重写HashMap的put方法，所以执行put操作的时候，还是使用的是HashMap的put方法。那么这样如何保证链表的逻辑呢？原因就是HashMap的putVal方法中实际调用了维护链表的方法，下面是关键代码：HashMap的putVal()方法
HashMap#putVal(…)
//默认的传入的evict是true
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
................
................
................
................
if (e != null) { // existing mapping for key
//如果e不为null，此时的e指向的就是在map中的那个插入点，所以这个时候来赋值。
V oldValue = e.value;
// onlyIfAbsent入口参数，为true，则不更新value（前面已说明）。
//这个地方的主要作用主要控制如果map中已经有那个key了，是否需要需要更新值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//这里其实是插入成功后执行的，获得的效果就是将e放到了链表结尾。
//所以afterNodeInsertion方法就算什么都不做也可以。
//但是如果accessOrder为false，那么我们新插入的节点，都不会进入链表了
afterNodeAccess(e);
return oldValue;
}
}
//fast-fail机制的实现，为了保证并发读安全。
++modCount;
//容器中的键值对数自增，如果大于了阈值，开始扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
在put方法中，HashMap会在合适的位置使用 afterNodeAccess(e)，和afterNodeInsertion(evict);方法。因为在HashMap中也定义了这三个函数，但是都是为空函数，在LInkedHashMap中只是重写了这3个方法。我们在使用map.put(key,value)的时候，实际调用HashMap#putVal(key,value)方法，然后再调用afterNodeAccess方法，那么这个时候调用的会是子类的afterNodeAccess方法吗？
这个就要涉及到多态的知识了，可以从虚拟机方面去解释：在虚拟机加载类的解析过程中，对方法调用有两种分派方式，静态分派对应重载，动态分派对应重写。这里对应的就是动态分派。动态分配是在运行时发生的，它对于方法是按照实际类型来首先寻找的。找不到再往父类走。这里的实际类型其实值new 后面跟着的类。所以这里不用担心会调用到父类的方法。
afterNodeInsertion方法不是没有用，而是留给扩展用的，下面会展示。
还有一点，put操作中使用afterNodeAccess来将新插入的节点放到尾部。但是这个方法要受到accessOrder的控制，如果accessOrder为false（默认就为false）那么新插入的节点应该就不能插入到链表中了。这样设计有什么特殊的意义吗？
Remove操作
HashMap#removeNode(…)
和put操作一样，也是直接使用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;
//判断table是否为空，该key对应的桶是否为空
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);
}
}
//到这里了其实node就已经指向了要删除的节点了
//matchValue的作用是指现在是否需要值匹配。因为可能没有传入value，所以判断一下
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;
//调用维护链表的操作
afterNodeRemoval(node);
return node;
}
}
return null;
}
LinkedHashMap用作实现LRU
LRU，即最近最少使用。LRU中保存的数据如果满了，那么就会将最近最少使用的数据删除。
LinkedHashMap通过使accessOrder为true，可以满足这种特性。代码如下：
leetcode 146. LRU缓存机制
class LRUCache extends LinkedHashMap {
private int capacity;
public LRUCache(int capacity) {
//accessOrder为true
super(capacity, 0.75F, true);
this.capacity = capacity;
}
public int get(int key) {
return (int)super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > capacity;
}
}
这里重写了removeEldestEntry方法，然后removeEldestEntry方法在afterNodeInsertion中被调用，如果这个方法返回真，那么就会删除head指向的节点。根据每次get的节点都会放到尾部的特性，所以head指向的节点就是最久没有使用到的节点，所以可以删除。由于我们每次put完（HashMap#putVal()）都会调用这个afterNodeInsertion方法，所以可以上面的设计可以使put过后如果size超了，将删除最久没有使用的一个节点，从而腾出空间给新的节点。
总结
一句话总结，LinkedHashMap就是HashMap中将其node维护成了一个双向链表。只要搞懂了HashMap就可以很容易搞懂LinkedHashMap。
1061
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
