LinkedHashMap源码分析
2019-04-01 本文已影响0人
冷冷DerFan
LinkedHashMap源码分析
概述
LinkedHashMap是HashMap的子类
LinkedHashMap继承树.png
它能够实现两大功能：
1.按照插入顺序访问
2.按照访问顺序调整元素顺序 （实现LRU）
首先看两个使用的示例：
public class LinkedHashMapTest {
public static void main(String[] args) {
// 按照插入顺序访问
Map<Integer, String> m = new LinkedHashMap<>();
m.put(1, "a");
m.put(2, "b");
m.put(3, "c");
m.put(4, "d");
m.put(5, "e");
m.put(6, "f");
// 访问元素不会调整该元素的顺序
m.put(3, "cc");
Set<Map.Entry<Integer, String>> entries = m.entrySet();
for (Map.Entry<Integer, String> entry : entries) {
System.out.println(entry);
}
System.out.println();
// 按照访问顺序调整顺序
Map<Integer, String> m2 = new LinkedHashMap<>(16, 0.75f, true);
m2.put(1, "aa");
m2.put(2, "bb");
m2.put(3, "cc");
m2.put(4, "dd");
printMap(m2);
System.out.println(m2.get(3));
printMap(m2);
System.out.println(m2.get(2));
printMap(m2);
}
public static void printMap(Map<Integer, String> map) {
System.out.println(map);
}
}
输出结果
1=a
2=b
3=cc
4=d
5=e
6=f
{1=aa, 2=bb, 3=cc, 4=dd}
cc
{1=aa, 2=bb, 4=dd, 3=cc}
bb
{1=aa, 4=dd, 3=cc, 2=bb}
可以看到 两次实验使用了LinkedHashMap 构造函数的不同参数，主要为accessOrder 参数。该参数为true表示访问时调整它的顺序。
构造一个LRU
public class LruCache<K, V> extends LinkedHashMap<K, V> {
private int maxSize;
public LruCache(int maxSize) {
super(16, 0.75f, true);
this.maxSize = maxSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > maxSize;
}
public static void main(String[] args) {
LruCache<Integer, String> lru = new LruCache<>(5);
lru.put(1, "a");
lru.put(2, "b");
lru.put(3, "c");
lru.put(4, "d");
lru.put(5, "e");
System.out.println(lru);
lru.get(3);
System.out.println(lru);
lru.put(6, "f");
System.out.println(lru);
}
}
输出结果为：
{1=a, 2=b, 3=c, 4=d, 5=e}
{1=a, 2=b, 4=d, 5=e, 3=c}
{2=b, 4=d, 5=e, 3=c, 6=f}
可以看到
1.访问元素后，该被访问的元素会被添加到链表的最后位置
2.重写removeEldestEntry方法后，按照策略删除最少访问的元素，即头部元素
而该链表为一个双向链表，后面源码分析部分会详细说明。
和HashMap的关系
（1）数据结构
LinkedHashMap继承自HashMap，有如下特殊数据结构
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);
}
}
transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> tail;
final boolean accessOrder;
Entry为LinkedHashMap中的节点，内部维护两个指针，分别指向后一个和前一个元素，可以组成一个双向链表。
另有两个节点保存头节点和尾节点
一个bool类型维护是否根据访问顺序调整节点顺序
（2）方法
在HashMap中使用了模板方法模式，有几个钩子方法，供子类实现
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
值得一提的是LinkedHashMap的节点为Entry，而不是HashMap的HashMap.Node。LinkedHashMap节点的创建是在自己的newNode方法中
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中的newNode实现，HashMap中的newNode是在put方法中被调用。
而且LinkedHashMap中的newNode添加了linkNodeLast方法调整被访问节点的顺序，将它放到链表尾部。
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
// 取出维护的 tail 指针，last指向的是现有的尾部元素
LinkedHashMap.Entry<K,V> last = tail;
// 指向新创建的元素
tail = p;
// 元素为空，head也指向该元素，链表中只有一个元素
if (last == null)
head = p;
// 尾元素不为null，新增元素维护双向链表结构
else {
// 新元素的before指向最后一个元素
p.before = last;
// 最后一个元素after指向新元素
last.after = p;
}
}
HashMap中的钩子方法我们来分析下源码
首先是按照访问有序时，将被访问元素放到链表尾端的方法afterNodeAccess
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// 按照 访问有序规则并且 刚才访问的元素不是尾元素，需要调整结构
if (accessOrder && (last = tail) != e) {
// p指向刚才访问的节点，b指向p的前驱，a指向p的后继
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// p的后驱为null
p.after = null;
// p为双向链表头节点，则头节点指向p的后继a
if (b == null)
head = a;
// p不为头节点，则p的前驱直接指向p的后继
else
b.after = a;
// 下面为维护向前的指针
// 后继不为null，后继的前驱指向p的前驱
if (a != null)
a.before = b;
// 后继为null，last指针指向前驱节点
else
last = b;
// last指针为null，头节点为p，只有一个元素
if (last == null)
head = p;
// 不只有p这个元素，则将p的前向指针指向最后一个节点，last的后继指向p
// 把p添加在双向链表的尾部
else {
p.before = last;
last.after = p;
}
// 尾指针指向p
tail = p;
// 维护修改次数变量
++modCount;
}
}
接着是插入元素后，将最老的元素删除，该方法的调用时机在hashMapput元素的最后，默认的put方法会将evict置为true
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
// evict为true，头节点不为null，重写的removeEldestEntry为true，则删除头部元素
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
接着调用HashMap的remove方法，可以看到其中afterNodeRemoval也是一个钩子方法
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;
// 链表不为null，hash值对应的元素不为null，p为hash路由到的table中的元素
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;
// 哈希值相同，key相同，没有hash冲突，node为p
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
// 产生了hash冲突，hash值不一样
else if ((e = p.next) != null) {
// p是红黑树
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);
}
}
// 查找到元素，value不为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;
// 钩子方法
afterNodeRemoval(node);
return node;
}
}
return null;
}
afterNodeRemoval方法在LinkedHashMap删除节点后，会从LinedHashMap的双向链表中去除该节点。
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.before = p.after = null;
// 待删除为头，则后继修改为头
if (b == null)
head = a;
// 待删除不为头，则前驱指向后继
else
b.after = a;
// 待删除为尾，则前驱修改为尾
if (a == null)
tail = b;
// 待删除不为尾，则后继的前驱指针指向前驱
else
a.before = b;
}
还有一个get方法也会访问元素，LinkedHashMap重写了该方法
public V get(Object key) {
Node<K,V> e;
// 先从HashMap的getNode中获取元素，为null则返回
if ((e = getNode(hash(key), key)) == null)
return null;
// 按访问顺序
if (accessOrder)
// 调用afterNodeAccess，将访问元素放到双向链表尾部
afterNodeAccess(e);
return e.value;
}
containsValue也是LinkedHashMap重写的方法
通过双向链表直接遍历元素是否存在
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;
}
总结：
1.LinkedHashMap可以实现按插入顺序访问
2.LinkedHashMap可以实现按照访问调整元素顺序，实现LRU
3.模板方法模式的使用，钩子方法的使用
