java集合框架源码解析之TreeMap源码解析_java getceilingentry

• 摘要**
  包含三个部分：
  TreeMap介绍
  TreeMap数据结构
  TreeMap源码分析

创作不易，转载请说明出处：https://blog.csdn.net/qq_37520037/article/details/82962487

• TreeMap介绍
  TreeMap是一个基于红黑树实现的一个有序的Key-Value集合。
  TreeMap继承自AbstractMap，实现了NavigableMap，Cloneable，Serializable接口，是一个可以导航，克隆，序列化的Map。
  TreeMap基于红黑树实现，是有序的，在不提供comparator的情况下根据自然顺序排序，在提供comparator时利用指定的comparator进行排序。
• TreeMap数据结构
  TreeMap基于红黑树来实现，如果你不了解红黑树的结构，建议你先去了解下红黑树，下面给出红黑树的简要定义：
  根节点为黑色，红连接总为左连接。
  没有任何一个节点同时和两个红连接相连。
  该树是完美的黑色平衡树，即任意空连接到根节点的黑连接数量是相同的。

TreeMap以Entry为存储结构，Entry中的属性包括有：key–存储键，value–存储与之对应的值，left–为指向左节点的连接，right–为指向右节点的连接，color–节点的颜色，parent–指向父节点的连接。

• TreeMap源码解析
  ThreeMap包含四个属性，分别是:
  private final Comparator<? super K> comparator; //在构造器中指定，如果没有指定则按自然顺序排序
  private transient Entry<K,V> root; //存储红黑树的根节点
  private transient int size = 0; //红黑树中的节点个数
  private transient int modCount = 0; //记录修改的次数

TreeMap有四个构造器，分别为：

//默认构造函数
public TreeMap() {
        comparator = null;
    }
//指定比较器的构造器
public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }
//传入一个map来把它构造成TreeMap
public TreeMap(Map<? extends K, ? extends V> m) {
        comparator = null;
        putAll(m);
    }
//传入一个SortedMap类型的参数，通过它来设置TreeMap的比较器并把它转化成TreeMap
public TreeMap(SortedMap<K, ? extends V> m) {
        comparator = m.comparator();
        try {
            buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
        } catch (java.io.IOException cannotHappen) {
        } catch (ClassNotFoundException cannotHappen) {
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

下面我们来看一下containsKey方法:
源码：
我们可以看到containsKey()方法中调用了getEntry(key)来判断是否存在指定的Key

public boolean containsKey(Object key) {
        return getEntry(key) != null;
    }
1
2
3

getEntry(Object key) 方法源码：
我们可以看到TreeMap是通过红黑树来实现的，在源码中还可以看出他的查找顺序，先获取分界点，利用自然顺序的比较器来比较指定key与根节点key的关系，比根节点key大的话，查找根节点的右子节点，比根节点小的话，查找根节点的左子节点，直到找到或者查找到null节点结束。
而当comparator不等于null是调用的方法去查找key与这个方法查找key的原理是一样的，只不过是在指定key与红黑树中的key比较时使用指定的比较器而已。

final Entry<K,V> getEntry(Object key) {
        // 如果指定了比较器，调用getEntryUsingComparator方法来获取Entry
        if (comparator != null)
            return getEntryUsingComparator(key);
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
            //根据二分查找来查找key，找到返回Entry,找不到返回null.
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = k.compareTo(p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
        return null;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

getCeilingEntry方法（K key），此方法用于查找一个比指定key大于或等于的最小节点。
理解这个方法主要看他的查找过程，对于红黑树来说，右边的节点>根节点>左边的节点。我们可以看到这也是一个查找，分三种情况。
第一种情况：指定key小于根节点的key，此时，我们只需找到根节点左节点的最小值即可。
第二种情况：指定key大于根节点的key,此时我们通过源码可以看到，因为一个节点的右子节点大于它，所以当这个根节点存在右子节点时，我们遍历右子节点，而当这个根节点没有右子节点时，返回结果有两种情况，一种为空，一种为大于key的最小的节点，因为当遍历到这一步时，之前遍历的节点都满足大于指定key这个条件，所以查找它的父节点来找出最小的那个大于它的节点，这个有点难理解。
第三种情况：指定key等于root的key,直接返回root.
对于第二种情况可以画图来理解:
首先我们遍历根节点，根节点key大于指定key，之后我们遍历根节点的左节点，直到其效益key为止，此时我们遍历小于key节点的右节点，遍历到最后一个时仍然小于key，此时我们要找的节点就是左节点中倒数第二个节点，我们不断获取最后一个节点的父节点，直到他为空，或它到左节点中倒数第二个节点.

 final Entry<K,V> getCeilingEntry(K key) {
 	//获取根节点
        Entry<K,V> p = root;
        while (p != null) {
            //比较指定key与根节点key
            int cmp = compare(key, p.key);
            //如果指定key小于根节点
            if (cmp < 0) {
                if (p.left != null)
                    p = p.left;
                else
                    return p;
            }//指定key大于根节点 
            else if (cmp > 0) {
                if (p.right != null) {
                    p = p.right;
                } else {
                    //当执行到这一步时，要弄清楚一点就是之前遍历的节点的key全部大于指定key。
                    Entry<K,V> parent = p.parent;
                    Entry<K,V> ch = p;
                    while (parent != null && ch == parent.right) {
                        ch = parent;
                        parent = parent.parent;
                    }
                    return parent;
                }
            }//指定key等于根节点的key 
            else
                return p;
        }
        return null;
    }
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

接下来是getFloorEntry（K key）获取比指定key小于或等于的最大节点。
通过源码我们发现这个实现和getCeilingEntry（k key）差不多，读者可参照上面的讲解理解。

final Entry<K,V> getFloorEntry(K key) {
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = compare(key, p.key);
            //指定key大于p的key
            if (cmp > 0) {
               //p存在右节点，p  = p.right;不存在返回p
                if (p.right != null)
                    p = p.right;
                else
                    return p;
            } else if (cmp < 0) {
            //指定key小于p节点时，找到小于key的最大的节点，参考上面讲解和图片对比理解即可
                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;
    }

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

final Entry<K,V> getHigherEntry(K key)方法用来获取大于指定key的最小节点。
final Entry<K,V> getLowerEntry(K key)方法用来获取小于指定key的最大节点。
由于实现和上面两个方法差不多，所有参照理解即可。

下面来看TreeMap的put方法：
可以看到这个put操作也是通过红黑树的二分查找实现的。

public V put(K key, V value) {
        Entry<K,V> t = root;
        //根节点为空，直接把要put的数据存入根节点
        if (t == null) {
            compare(key, key); // type (and possibly null) check
·	   //new  Entry()三个参数分别为key,value,parent.
            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;
        if (cpr != null) {
           //根节点存在，comparator比较器存在，查找key,找到后覆盖key的原来的值。
            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);
        }
        //没找到key的话说明新插入的key是一个新的key,增加节点。
        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;
    }

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

接下来看fixAfterInsertion()方法，他保证了红黑树添加节点之后的结构仍符合红黑树
解析参考注释，理解时最好画图。

 private void fixAfterInsertion(Entry<K,V> x) {
        //新加入的节点为红节点。
        x.color = RED;
	//恢复红黑树，新插入的节点的父节点为红色
        while (x != null && x != root && x.parent.color == RED) {
            //如果新插入节点的父节点是新插入节点的祖父节点的左节点
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                //判断x的祖父节点的右节点是否为红色，如果为红色的话需要变色操作，也就是把祖父节点变红色，x的父节点，和x的父节点的兄弟节点变黑色，因为红黑树不允许出现一个节点的两个子节点都为红色。
                Entry<K,V> y = rightOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    //这种情况是x节点为父节点的右子节点，而且x节点和其父节点都为红色，由于红黑树不允许出现右节点为红色，所有需要进行左旋操作（rotateLeft）。左旋后存在两个连续节点为红色，x为左子节点，父节点也为红色。
                    if (x == rightOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateLeft(x);
                    }
                    //此时红黑树结构为连续两个节点为红色，而且子节点为左子节点，需要进行右旋操作.
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateRight(parentOf(parentOf(x)));
                }
            } else {
               //这种情况说明x节点的父节点为x节点的祖父节点的右节点
                Entry<K,V> y = leftOf(parentOf(parentOf(x)));
                //同样，如果x节点的祖父节点的左节点为红色，需要颜色变换成根节点红色，子节点黑色
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    //如果x为左子节点，则需要先让x的父节点右旋
                    if (x == leftOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateRight(x);
                    }
                    之后x的祖父节点设为红色，左旋。
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateLeft(parentOf(parentOf(x)));
                }
            }
        }
        //保证根节点为黑色
        root.color = BLACK;
    }
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

接下来我们来看下remove方法，remove方法同样会改变红黑树的结构，因此，它同样需要维持红黑树结构。
remove方法会删除一个节点并返回这个节点原来的值，如果这个节点不存在则返回null.
remove方法调用deleteEntry()来删除节点。
源码如下：

public V remove(Object key) {
        Entry<K,V> p = getEntry(key);
        if (p == null)
            return null;

        V oldValue = p.value;
        deleteEntry(p);
        return oldValue;
    }
1
2
3
4
5
6
7
8
9

deleteEntry()方法实现节点的删除
仔细研究后其实这个代码写的挺好的，它把有两个子节点和有一个子节点的两种情况用一种代码实现了，真好。

private void deleteEntry(Entry<K,V> p) {
        //记录修改次数，修改次数加1
        modCount++;
        //节点数减1
        size--;

        // If strictly internal, copy successor's element to p and then make p
        // point to successor.
        //如果p节点存在左节点和右节点。使用successor(p) 来找出p的下一个节点，即比p大的最小的节点，然后把p的值设为p的下一个节点的值，最后把p的引用指向p的下一个节点的引用。
        if (p.left != null && p.right != null) {
            Entry<K,V> s = successor(p);
            p.key = s.key;
            p.value = s.value;
            p = s;
        } // p has 2 children
	
        // Start fixup at replacement node, if it exists.
        //replacement的值有两种情况，第一种的p的子节点，第二种是p的下一个节点的子节点，因为当p存在两个子节点时p的引用变成了p的下一个节点的引用。
        Entry<K,V> replacement = (p.left != null ? p.left : p.right);
	//当p的子节点存在或p的下一个子节点存在，修改p的子节点的连接或p的下一个子节点的连接。
        if (replacement != null) {
            // Link replacement to parent
            replacement.parent = p.parent;
            if (p.parent == null)
                root = replacement;
            else if (p == p.parent.left)
                p.parent.left  = replacement;
            else
                p.parent.right = replacement;
	    //删除p节点或p的下一个节点，因为当删除p的下一个节点后，p的值已经替换为p的下一个节点的值。这代码真的精致。
            // Null out links so they are OK to use by fixAfterDeletion.
            p.left = p.right = p.parent = null;
	    //因为红黑树不允许存在两个连续的红节点，所有当p为黑色时，删除后可能导致两个连续的红节点的情况出现，所有需要调用fixAfterDeletion()来维护红黑树。
            // Fix replacement
            if (p.color == BLACK)
                fixAfterDeletion(replacement);
                //当p的父节点为空时说明只存在一个节点p所以root节点变为空。
        } else if (p.parent == null) { // return if we are the only node.
            root = null;
            //下面是p不存在子节点的情况，需要把p的父节点指向p的连接置为null.因为红黑树的黑节点为完全平衡的，所以维护红黑树的准确性
        } else { //  No children. Use self as phantom replacement and unlink.
            if (p.color == BLACK)
                fixAfterDeletion(p);

            if (p.parent != null) {
                if (p == p.parent.left)
                    p.parent.left = null;
                else if (p == p.parent.right)
                    p.parent.right = null;
                p.parent = null;
            }
        }
    }
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

get()方法实现比较简单，调用getEntry来获取与key对应的value值

public V get(Object key) {
        Entry<K,V> p = getEntry(key);
        return (p==null ? null : p.value);
    }
1
2
3
4

首先，恭喜你看到这里，我很佩服你的耐心和对知识的渴望，这是TreeMap中一些常用方法，涉及到红黑树的维护，插入，删除，查询。相信你现在已经对红黑树有了更清晰的认识。祝你好运。