首页 | 新闻 | 新品 | 文库 | 方案 | 视频 | 下载 | 商城 | 开发板 | 数据中心 | 座谈新版 | 培训 | 工具 | 博客 | 论坛 | 百科 | GEC | 活动 | 主题月 | 电子展
返回列表 回复 发帖

Java 容器源码分析之 LinkedHashMap(2)

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;
}
返回列表