前言
今天写一下经常拿来与HashMap对比的LinkedHashMap源码分析。那么LinkedHashMap存在的意义在哪？我们从HashMap文章里可以知道HashMap是无序的，而LinkedHashMap正是为了解决这一问题的。LinkedHashMap是继承自HashMap，因此HashMap的相关操作其实在HashMap中都已经实现了。它对于HashMap的扩展主要是其内部还维护了一个双向链表，在每次插入数据，或者访问、修改数据时，会增加节点、或调整链表的节点顺序。以决定迭代时输出的顺序，也就是说LinkedHashMap在HashMap的基础上实现了有序性。
（以下分析注重于LinkedHashMap的对于HashMap扩展）
对于Node的封装
LinkedHashMap中Entry<K,V>继承于Map.Node，在父类基础上增加了before与aftre用于实现集合元素的有序排列
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);
}
}
accessOrder字段
构造函数增加了accessOrder字段，用于标记迭代顺序是否与访问顺序有关
accessOrder为false：迭代时输出的顺序是插入节点的顺序（先->后）
accessOrder为true：迭代时输出的顺序是访问节点的顺序（元素每次被访问都置于尾部）
重写newNode方法
每次put元素，都将其他置于双向链表尾部
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;
}
}
实现HashMap中用于回调的三个钩子方法
在相应操作发生后得到回调，更新双向链表
void afterNodeAccess(Node<K,V> p) { } // 访问（查）
void afterNodeInsertion(boolean evict) { } // 插入（增）
void afterNodeRemoval(Node<K,V> p) { } // 移除（删）
afterNodeAccess方法
每当有元素被访问时，更新集合顺序
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) { // accessOrder为true且末尾不是当前传入节点
// 删除节点在双向链表中的位置
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// p现在是尾节点，所以after为null
p.after = null;
// 如果b为null，表示p以前是头节点
if (b == null)
head = a; // 将头节点设置为a
else
b.after = a; // 将下个节点设置为a
// 如果a不是null，则更新其前置节点为b
if (a != null)
a.before = b;
// a为null表示p以前是尾节点，将last设置为b
else
last = b;
// a与b均为null，则表示之前链表只有一个节点
if (last == null)
head = p;
else { // 否则将p放到末尾
p.before = last;
last.after = p;
}
tail = p; // 更新尾节点
++modCount; // 修改modCount
}
}
afterNodeInsertion方法
根据 evict与removeEldestEntry返回值判断是否需要删除最早添加的节点（最老）,其实就是LRUCache的实现，LRUCache就是利用了LinkedHashMap
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
// evict 默认为true，在put方法中得知
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; // 默认不删除
}
afterNodeRemoval方法
在删除元素后同时将其他从双向链表中移除
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; // 将头节点设置为a
else
b.after = a;
if (a == null) // 目标节点之前是尾
tail = b; // 将尾设置为b
else
a.before = b;
}
重写get等方法
重写了相关查询方法，在条件满足情况下调用afterNodeAccess
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;
}
重写containsValue
利用双向链表循环，比HashMap的双重循环高效
public boolean containsValue(Object value) {
for (LinkedHashMap.Entry<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;
}
元素迭代
使用双向链表，保证有序性
abstract class LinkedHashIterator {
LinkedHashMap.Entry<K,V> next;
LinkedHashMap.Entry<K,V> current;
int expectedModCount;
......
// 从双向链表表头开始循环
final LinkedHashMap.Entry<K,V> nextNode() {
LinkedHashMap.Entry<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
current = e;
next = e.after;
return e;
}
｝
特性总结
LinkedHashMap是HashMap子类，在父类基础上维护了双向链表，重写了相关方法，保证集合元素的有序性（重写newNode方法，每次put元素放置到双向链表尾部；重写查询相关方法，保证能够将被访问元素置于双向链表尾部；重写了afterNodeAccess、afterNodeInsertion、afterNodeRemoval方法，顺序调整回调，操作双向链表）
提供了accessOrder属性，可设置元素顺序是否与访问顺序有关
优化了containsValue方法，直接使用双向链表进行循环查找
Android中LruCache的实现即是通过LinkedHashMap进行实现
（LRU（Least recently used，最近最少使用）算法）
网友评论