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

Java 容器源码分析之 TreeMap(9)

Java 容器源码分析之 TreeMap(9)

因为红黑树自身就是有序的,迭代是只要从第一个节点不断获取后继节点即可。当然,逆序时则是从最后一个节点不断获取前驱节点。通过迭代器访问时基于 modCount 实现对并发修改的检查。
在排序二叉树中获取前驱和后继节点的方法如下:
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//后继节点
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.right != null) {
        //右子树存在,则取右子树的最小节点
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        //右子树不存在
        //若父节点为null,则该节点是最大节点(根节点,且无右子树),无后继,返回null
        //若当前节点是父节点的左子节点,直接返回父节点
        //若当前节点是父节点的右子节点,则当前节点是以父节点为根的子树中最大的节点
        Entry<K,V> p = t.parent; //父节点
        Entry<K,V> ch = t;//当前节点
        while (p != null && ch == p.right) {
            //是右子节点,向上迭代,直到是左子节点
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

//前驱节点,同后继节点处理逻辑一致,左右颠倒
static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.left != null) {
        //左子树存在,则取左子树的最小节点
        Entry<K,V> p = t.left;
        while (p.right != null)
            p = p.right;
        return p;
    } else {
        //左子树不存在
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.left) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}
其它方法TreeMap 中还实现了一些其它的方法,如区间操作: headMap(), tailMap(), subMap() ; 获取逆序的 map: descendingMap() , descendingKeySet() 。只要了解了前面介绍的各种操作的原理,再来看这些方法的实现应该也不难理解。由于篇幅太长,这里就不再介绍了。
小结TreeMap 是基于红黑树实现的一种 Key-Value 结构,最大的特点在于可以按照 Key 的顺序进行访问,要求 Key 实现 Comparable 接口或传入 Comparator 作为比较器。因为基于红黑树实现,TreeMap 内部在实现插入和删除操作时代价较高。
TreeMap 实现了 NavigableMap 接口,可以支持一系列导航方法,有 firstEntry()、 lastEntry()、 lowerEntry()、 higherEntry()、 floorEntry()、 ceilingEntry()、 pollFirstEntry() 、 pollLastEntry() ;还可以支持区间操作获取 map 的一部分,如 subMap(), headMap(), tailMap(K fromKey) 。除此以外, TreeMap 还支持通过 descendingMap() 获取和原来顺序相反的 map。
如果 TreeMap 没有使用自定义的 Comparator,则是不支持键为 null 的,因为调用 compareTo() 可能会发生异常;如果自定义的比较器可以接受 null 作为参数,那么是可以支持将 null 作为键的。
TreeMap 不是线程安全的,多线程情况下要手动进行同步或使用 SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));。
返回列表