Java 容器源码分析之 LinkedHashMap（2）
|
- UID
- 1066743
|
Java 容器源码分析之 LinkedHashMap（2）
双向链表为了简化对双向链表的操作，LinkedHashMap 中提供了 linkNodeLast 和 transferLinks 方法，分别如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| // link at the end of list
// 将新节点 p 链接到双向链表的末尾
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
//为空，则为头节点
head = p;
else {
//修改before 和 after的指向
p.before = last;
last.after = p;
}
}
// apply src's links to dst
// 将src的链接应用到dst中，就是用dst替换src在双向链表中的位置
private void transferLinks(LinkedHashMap.Entry<K,V> src,
LinkedHashMap.Entry<K,V> dst) {
//修改dst的前驱和后继指向
LinkedHashMap.Entry<K,V> b = dst.before = src.before;
LinkedHashMap.Entry<K,V> a = dst.after = src.after;
//将双向链表中原来指向src的链接改为指向dst
if (b == null)
head = dst;
else
b.after = dst;
if (a == null)
tail = dst;
else
a.before = dst;
}
|
LinkedHashMap 重写了父类新建节点的方法，在新建节点之后调用 linkNodeLast 方法将新添加的节点链接到双向链表的末尾：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| //覆盖父类方法
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;
}
//覆盖父类方法
//新建TreeNode
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
//将新建的节点链接到双向链表的末尾
linkNodeLast(p);
return p;
}
|
我们知道，HashMap 中单个桶中的元素可能会在单链表和红黑树之间进行转换，LinkedHashMap 中当然也是一样，不过在转换时还要调用 transferLinks 来改变双向链表中的连接关系：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| //覆盖父类方法
// For conversion from TreeNodes to plain nodes
// 将节点由 TreeNode 转换为 普通节点
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p; //TreeNode
//根据TreeNode的信息创建新的普通节点
LinkedHashMap.Entry<K,V> t =
new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next);
//将双向链表中的TreeNode替换为新的普通节点
transferLinks(q, t);
return t;
}
//覆盖父类方法
// For treeifyBin
// 将节点由普通节点转换为TreeNode
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next);
transferLinks(q, t);
return t;
} |
|
|
|
|
|
|
