LinkedHashMap
是HashMap
的子类,所以也具备HashMap
的诸多特性。不同的是,LinkedHashMap
还维护了一个双向链表,以保证通过Iterator
遍历时顺序与插入顺序一致。除此之外,它还支持Access Order,即按照元素被访问的顺序来排序,我们熟知的LRUCache
底层就依赖于此。以下是文档中需要我们注意的点:
Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order). Note that insertion order is not affected if a key is re-inserted into the map.
A special LinkedHashMap(int,float,boolean) constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order). This kind of map is well-suited to building LRU caches.
The removeEldestEntry(Map.Entry) method may be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map.
Note, however, that the penalty for choosing an excessively high value for initial capacity is less severe for this class than for HashMap, as iteration times for this class are unaffected by capacity.
下面我们就从构造函数和成员变量开始分析其具体实现。
构造函数与成员变量
成员变量
在分析成员变量前,我们先看下其存储元素的结构。
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);
}
}
这个Entry
在HashMap
中被引用过,主要是为了能让LinkedHashMap
也支持树化。在这里则是用来存储元素。
// 双向链表的头,用作AccessOrder时也是老的元素
transient LinkedHashMap.Entry<K,V> head;
// 双向链表的尾,用作AccessOrder时也是新的元素
transient LinkedHashMap.Entry<K,V> tail;
// true则为访问顺序,false则为插入顺序
final boolean accessOrder;
构造函数
关于LinkedHashMap
的构造函数我们只关注一个,其他的都和HashMap
类似,只是把accessOrder
设置为了false。在上边的文档说过,initialCapacity并没有在HashMap
中那般重要,因为链表不需要像数组那样必须先声明足够的空间。下面这个构造函数是支持访问顺序的。
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
重要方法
LinkedHashMap
并没有再实现一整套增删改查的方法,而是通过复写HashMap
在此过程中定义的几个方法来实现的。对此不熟悉的可以查看文末关于HashMap
分析的文章,或者对照HashMap
的源码来看。
插入一个元素
HashMap
在插入时,调用了newNode
来新建一个节点,或者是通过replacementNode
来替换值。在树化时也有两个对应的方法,分别是newTreeNode
和replacementTreeNode
。完成之后,还调用了afterNodeInsertion
方法,这个方法允许我们在插入完成后做些事情,默认是空实现。
为了方便分析,我们会对比HashMap
中的实现与LinkedHashMap
的实现,来摸清它是如何做的。
// HashMap中的实现
Node<K, V> newNode(int hash, K key, V value, Node<K, V> next) {
return new Node<>(hash, key, value, next);
}
// 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;
}
// HashMap中的实现
Node<K, V> replacementNode(Node<K, V> p, Node<K, V> next) {
return new Node<>(p.hash, p.key, p.value, next);
}
// LinkedHashMap中的实现
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
LinkedHashMap.Entry<K,V> t =
new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next);
transferLinks(q, t);
return t;
}
// newTreeNode和replacementTreeNode和此类似
通过以上对比,可以发现,LinkedHashMap
在新增时,调用了linkNodeLast
,再替换时调用了transferLinks
。以下是这两个方法的实现。
// 就是将元素挂在链尾
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;
}
}
// 用dst替换src
private void transferLinks(LinkedHashMap.Entry<K,V> src,
LinkedHashMap.Entry<K,V> dst) {
LinkedHashMap.Entry<K,V> b = dst.before = src.before;
LinkedHashMap.Entry<K,V> a = dst.after = src.after;
if (b == null)
head = dst;
else
b.after = dst;
if (a == null)
tail = dst;
else
a.before = dst;
}
后我们看下afterNodeInsertion
做了哪些事情吧:
// evict在HashMap中说过,为false表示是创建阶段
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
// 不是创建阶段
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
// 自动删除老的元素,也就是head元素
removeNode(hash(key), key, null, false, true);
}
}
removeEldestEntry
是当想要在插入元素时自动删除老的元素时需要复写的方法。其默认实现如下:
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
查询
因为要支持访问顺序,所以获取元素的方法和HashMap
也有所不同。下面我们看下其实现:
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;
}
getNode
方法是在HashMap
中实现的,所以这是包装了一下HashMap
的方法,并添加了一个afterNodeAccess
,其实现如下:
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// e元素不在末尾
if (accessOrder && (last = tail) != e) {
// p是e,b是前一个元素,a是后一个元素
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// e要放在末尾,所以没有after
p.after = null;
// 把e去掉,把b和a接起来
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
//把e接在末尾
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
关于LinkedHashMap
的分析就到这里了,其他关于Iterator
的内容都和Collection
是大同小异的,感兴趣的可以去查看相关源码。
更多文章正在火速连载中,感谢您的关注!