Ronaldo

• 于 Read

管中窥豹：TreeMap源码学习

一、学习自

红黑树：http://www.cnblogs.com/skywang12345/p/3245399.html
http://www.cnblogs.com/skywang12345/p/3310928.html

二、注意点

TreeMap 是一个有序的key-value集合,它是通过红黑树实现的。(key,value都不能为null)
TreeMap 实现了NavigableMap接口,意味着它支持一系列的导航方法。比如返回有序的key集合。
TreeMap基于红黑树(Red-Black tree)实现。该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator 进行排序,具体取决于使用的构造方法。
TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。
TreeMap是非同步的。它的iterator 方法返回的迭代器是fail-fastl的。
TreeMap本质上是一颗红黑树。要彻底理解TreeMap,建议读者先理解红黑树。

三、自己以一个小示例开始学习思考的过程

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("one", 1);
treeMap.put("two", 2);
treeMap.put("three", 3);
System.out.println(treeMap);                     // {one=1, three=3, two=2}
System.out.println(treeMap.lastKey());           // two
treeMap.remove("two", 2);
System.out.println(treeMap);                     // {one=1, three=3}
System.out.println(treeMap.firstEntry());        // one=1
System.out.println(treeMap.floorEntry("one"));   // one=1
System.out.println(treeMap.lowerKey("one"));     // null
System.out.println(treeMap.ceilingEntry("one")); // one=1
System.out.println(treeMap);                     // {one=1, three=3}
System.out.println(treeMap.headMap("one"));      // {}

我的思考过程很简单,以上面的示例代码为例,去源码里一步一步对着来:
      比如,一开始就实例化了一个TreeMap的对象,那么肯定用到构造函数了,TreeMap里有4个构造函数,我只需要找到相对应那个即可,由于我没有传参,那么很显然就是无参构造函数了,当然,实例化同时也会将TreeMap定义的一些属性初始化,一并打出来：

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
private final Comparator<? super K> comparator; // 注释里面说用来保持顺序的或者使用 键的自然顺序。用来给TreeMap排序
private transient Entry<K,V> root;  // 红黑书的根节点,这里用到了Entry,需要找到它
private transient int size = 0;     // 红黑树的节点总数
private transient int modCount = 0; // 修改次数
/*
 * Constructs a new, empty tree map, using the natural ordering of its keys
 * 只做了一件事,把 comparator 赋值为null
 */
public TreeMap() {
    comparator = null;
}
/**
  * Node in the Tree.  Doubles as a means to pass key-value pairs back to
  * user (see Map.Entry).
  * Entry 是TreeMap基本数据节点
  */
static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;
    // 省略一部分代码
    ...
}
/*
 * TreeMap 有自己重写的 put 方法,代码有点多。。。
 * 理解TreeMap的前提是掌握“红黑树”。
 * 若理解“红黑树中添加节点”的算法,则很容易理解put。
 */
public V put(K key, V value) {
    Entry<K,V> t = root;
    // 若红黑树为空,则插入根节点
    if (t == null) {
        compare(key, key); // type (and possibly null) check
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    // 在二叉树(红黑树是特殊的二叉树)中,找到(key, value)的插入位置。
    // 红黑树是以key来进行排序的,所以这里以key来进行查找。
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    else {
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    // 新建红黑树的节点(e)
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    // 红黑树插入节点后,不再是一颗红黑树；
    // 这里通过fixAfterInsertion的处理,来恢复红黑树的特性。
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}
/*
 * 接下来看看lastKey()
 */
public K lastKey() {
    return key(getLastEntry());
}
static <K> K key(Entry<K,?> e) {
    if (e==null)
        throw new NoSuchElementException();
    // 返回了Entry类型的e.key属性
    return e.key;
}
/**
  * Returns the last Entry in the TreeMap (according to the TreeMap's
  * key-sort function).  Returns null if the TreeMap is empty.
  */
final Entry<K,V> getLastEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.right != null)
            p = p.right;
    return p;
}
/*
 * 再看看floorEntry,返回不大于key的最大的键值对,没有的话返回null
 */
public Map.Entry<K,V> floorEntry(K key) {
    return exportEntry(getFloorEntry(key));
}
/*
 * 获取TreeMap中不大于key的最大的节点；
 * 若不存在(即TreeMap中所有节点的键都比key小),就返回null
 * getFloorEntry的原理和getCeilingEntry类似
 */
final Entry<K,V> getFloorEntry(K key) {
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp > 0) {
            if (p.right != null)
                p = p.right;
            else
                return p;
        } else if (cmp < 0) {
            if (p.left != null) {
                p = p.left;
            } else {
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                while (parent != null && ch == parent.left) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        } else
            return p;
    }
    return null;
}
/*
 * 返回一个拷贝值
 */
static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
    return (e == null) ? null :
        new AbstractMap.SimpleImmutableEntry<>(e);
}
/*
 * 接下来是lowerKey()
 */
public K lowerKey(K key) {
    return keyOrNull(getLowerEntry(key));
}
/*
 * 这里的getLowerEntry()和getFloorEntry()很像
 * 获取TreeMap中小于key的最大的节点。若不存在,就返回null。
 * 与getFloorEntry()区别在于排除了等于key的节点
 * 最后,看看headMap(),有两个不同类型的,我示例中用到了SortedMap类型的
 */
public SortedMap<K,V> headMap(K toKey) {
    return headMap(toKey, false); // 这里其实还是调用了NavigableMap类型的headMap()
}
public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
    return new AscendingSubMap<>(this,
                                     true,  null,  true,
                                     false, toKey, inclusive);
}

总结

      TreeMap比之前几个集合理解起来有点难度,因为我不懂红黑树,红黑树看起来也不是很懂,所以着重看文章开头的链接吧,前辈讲的很好。

Newer Post

管中窥豹：java队列(Queue)学习一--ArrayDeque

一、学习自https://www.cnblogs.com/CarpenterLee/p/5468803.htmlhttps://blog.csdn.net/u011240877/article/details/52860924https://www.cnblogs.com/Dylansuns/arc …

• 于 继续阅读
Older Post

管中窥豹：LinkedHashMap源码学习

一、学习自https://blog.csdn.net/justloveyou_/article/details/71713781http://www.cnblogs.com/xrq730/p/5052323.htmlhttp://www.importnew.com/18706.html 二、注意点 …

• 于 继续阅读