Java源码解析之LinkedHashMap

Java源码解析之LinkedHashMap

一、成员变量

先来看看存储元素的结构吧：

static class Entry extends HashMap.Node {

Entry before, after;

Entry(int hash, K key, V value, Node next) {

super(hash, key, value, next);

}

}

这个Entry在HashMap中被引用过，主要是为了能让LinkedHashMap也支持树化。在这里则是用来存储元素。

// 双向链表的头，用作AccessOrder时也是最老的元素

transient LinkedHashMap.Entry head;

// 双向链表的尾，用作AccessOrder时也是最新的元素

transient LinkedHashMap.Entry tail;

// true则为访问顺序，false则为插入顺序

final boolean accessOrder;

二、构造函数

关于LinkedHashMap的构造函数我们只关注一个，其他的都和HashMap类似，只是把accessOrder设置为了false。在上边的文档说过，initialCapacity并没有在HashMap中那般重要，因为链表不需要像数组那样必须先声明足够的空间。下面这个构造函数是支持访问顺序的。

// 双向链表的头，用作AccessOrder时也是最老的元素

transient LinkedHashMap.Entry head;

// 双向链表的尾，用作AccessOrder时也是最新的元素

transient LinkedHashMap.Entry tail;

// true则为访问顺序，false则为插入顺序

final boolean accessOrder;

三、重要方法

LinkedHashMap并没有再实现一整套增删改查的方法，而是通过复写HashMap在此过程中定义的几个方法来实现的。对此不熟悉的可以查看上一篇关于HashMap分析的文章，或者对照HashMap的源码来看。

1、插入一个元素

HashMap在插入时，调用了newNode来新建一个节点，或者是通过replacementNode来替换值。在树化时也有两个对应的方法，分别是newTreeNode和replacementTreeNode。完成之后，还调用了afterNodeInsertion方法，这个方法允许我们在插入完成后做些事情，默认是空实现。

为了方便分析，我们会对比HashMap中的实现与LinkedHashMap的实现，来摸清它是如何做的。

// HashMap中的实现

Node newNode(int hash, K key, V value, Node next) {

return new Node<>(hash, key, value, nHbVjYuzext);

}

// LinkedHashMap中的实现

Node newNode(int hash, K key, V value, Node e) {

LinkedHashMap.Entry p =

new LinkedHashMap.Entry(hash, key, value, e);

linkNodeLast(p);

return p;

}

// HashMap中的实现

Node replacementNode(Node p, Node next) {

return new Node<>(p.hash, p.key, p.value, next);

}

// LinkedHashMap中的实现

Node replacementNode(Node p, Node next) {

LinkedHashMap.Entry q = (LinkedHashMap.Entry)p;

LinkedHashMap.Entry t =

new LinkedHashMap.Entry(q.hash, q.key, q.value, next);

transferLinks(q, t);

return t;

}

// newTreeNode和replacementTreeNode和此类似

通过以上对比，可以发现，LinkedHashMap在新增时，调用了linkNodeLast，再替换时调用了transferLinks。以下是这两个方法的实现。

// 就是将元素挂在链尾

private void linkNodeLast(LinkedHashMap.Entry p) {

LinkedHashMap.Entry last = tail;

tail = p;

if (last == null)

head = p;

else {

p.before = last;

last.after = p;

}

}

// 用dst替换src

private void transferLinks(LinkedHashMap.Entry src,

HbVjYuz LinkedHashMap.Entry dst) {

LinkedHashMap.Entry b = dst.before = src.before;

LinkedHashMap.Entry 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 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 eldest) {

return false;

}

2、查询

因为要支持访问顺序，所以获取元素的方法和HashMap也有所不同。下面我们看下其实现：

public V get(Object key) {

Node e;

if ((e = getNode(hash(key), key)) == null)

return null;

if (accessOrder)

// 数据被访问，需要将其移动到末尾

afterNodeAccess(e);

return e.value;

}

getNode方法是在HashMap中实现的，所以这是包装了一下HashMap的方法，并添加了一个afterNodeAccess，其实现如下：

void afterNodeAccess(Node e) { // move node to last

LinkedHashMap.Entry last;

// e元素不在末尾

if (accessOrder && (last = tail) != e) {

// p是e，b是前一个元素，a是后一个元素

LinkedHashMap.Entry p =

(LinkedHashMap.Entry)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;

HbVjYuz last.after = p;

}

tail = p;

++modCount;

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。