Java常用类源码——TreeMap源码解析

Posted on | In | | Visitors

网上介绍HashMap的比较多，但是介绍TreeMap的反而不是那么多，其中的原因我觉得，有两个：1、HashMap的使用场景比较多，2、是相对于HashMap来说，TreeMap所用到的数据结构更为复杂。

TreeMap的签名

1
2
3
public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

从上面的类的签名可以知道，相比HashMap来说，TreeMap多继承了一个接口NavigableMap，也就是这个接口，决定了TreeMap于HashMap的不同：

HashMap的key是无序的，TreeMap的key是有序的

接口NavigableMap

首先看下NavigableMap签名

1
public interface NavigableMap<K,V> extends SortedMap<K, V>

我们从中可以知道NavigableMap继承了SortedMap,再看SortedMap的签名

SortedMap

1
public interface SortedMap<K,V> extends Map<K,V>

SortedMap 顾名思义可以知道，这个Map是有序的，这个顺序一般是值由Comparable接口提供的keys的自然序（natural ordering）,或者也可以在创建SortedMap实例时，指定一个Comparator来决定。当我们在用集合视角（collection views， 与HashMap一样，也是由entrySet、keySet与values方法提供）来迭代（iterate） 一个SortedMap实例时会体现出key的顺序，这里引申下关于Comparable 与Comparator 的区别

  • Comparable一般表示类的自然序，比如定义一个Student类，学号为默认排序。
  • Comparator一般表示类在某种场合下的特殊分类，需要定制化排序，比如现在想按照Student类的age来排序

插入SortedMap中的key的类都必须继承Comparable类(或指定一个Comparator)，这样才能确定如何比较（通过k1.compareTo(k2)或者comparator.compare(k1，k2)）两个key，否则，在插入时，会经常报出ClassCastExecption的异常， 此为，SortedMap中key的顺序性应该与equals方法保持一致。也就是说k1.compareTo(k2)或comparator.compare(k1, k2)为true时，k1.equals(k2)也应该为true。

介绍完了SortedMap，再来回到我们的NavigableMap上面来。 NavigableMap是JDK1.6新增的，在SortedMap的基础上，增加了一些“导航方法”（navigation methods）来返回与搜索目标最近的元素。例如下面这些方法：

  • lowerEntry，返回所有比给定Map.Entry小的元素
  • floorEntry，返回所有比给定Map.Entry小或相等的元素
  • ceilingEntry，返回所有比给定Map.Entry大或相等的元素
  • higherEntry，返回所有比给定Map.Entry大的元素

我在看TreeMap中的源码的时候，我们先看一下TreeSet集合的源码:

TreeSet源码：

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
public class TreeSet<E> extends AbstractSet<E> 
    implements NavigableSet<E>, Cloneable, java.io.Serializable
 { 
    // 使用 NavigableMap 的 key 来保存 Set 集合的元素
    private transient NavigableMap<E,Object> m; 
    // 使用一个 PRESENT 作为 Map 集合的所有 value。
    private static final Object PRESENT = new Object(); 
    // 包访问权限的构造器，以指定的 NavigableMap 对象创建 Set 集合
    TreeSet(NavigableMap<E,Object> m) 
    { 
        this.m = m; 
    } 
    public TreeSet()                                      // ①
    { 
        // 以自然排序方式创建一个新的 TreeMap，
        // 根据该 TreeSet 创建一个 TreeSet，
        // 使用该 TreeMap 的 key 来保存 Set 集合的元素
        this(new TreeMap<E,Object>()); 
    } 
    public TreeSet(Comparator<? super E> comparator)     // ②
    { 
        // 以定制排序方式创建一个新的 TreeMap，
        // 根据该 TreeSet 创建一个 TreeSet，
        // 使用该 TreeMap 的 key 来保存 Set 集合的元素
        this(new TreeMap<E,Object>(comparator)); 
    } 
    public TreeSet(Collection<? extends E> c) 
    { 
        // 调用①号构造器创建一个 TreeSet，底层以 TreeMap 保存集合元素
        this(); 
        // 向 TreeSet 中添加 Collection 集合 c 里的所有元素
        addAll(c); 
    } 
    public TreeSet(SortedSet<E> s) 
    { 
        // 调用②号构造器创建一个 TreeSet，底层以 TreeMap 保存集合元素
        this(s.comparator()); 
        // 向 TreeSet 中添加 SortedSet 集合 s 里的所有元素
        addAll(s); 
    } 
    //TreeSet 的其他方法都只是直接调用 TreeMap 的方法来提供实现
    ... 
    public boolean addAll(Collection<? extends E> c) 
    { 
        if (m.size() == 0 && c.size() > 0 && 
            c instanceof SortedSet && 
            m instanceof TreeMap) 
        { 
            // 把 c 集合强制转换为 SortedSet 集合
            SortedSet<? extends E> set = (SortedSet<? extends E>) c; 
            // 把 m 集合强制转换为 TreeMap 集合
            TreeMap<E,Object> map = (TreeMap<E, Object>) m; 
            Comparator<? super E> cc = (Comparator<? super E>) set.comparator(); 
            Comparator<? super E> mc = map.comparator(); 
            // 如果 cc 和 mc 两个 Comparator 相等
            if (cc == mc || (cc != null && cc.equals(mc))) 
            { 
                // 把 Collection 中所有元素添加成 TreeMap 集合的 key 
                map.addAllForTreeSet(set, PRESENT); 
                return true; 
            } 
        } 
        // 直接调用父类的 addAll() 方法来实现
        return super.addAll(c); 
    } 
    ... 
 }

从上面代码可以看出，TreeSet 的 ① 号、② 号构造器的都是新建一个 TreeMap 作为实际存储 Set 元素的容器，而另外 2 个构造器则分别依赖于 ① 号和 ② 号构造器，由此可见，TreeSet 底层实际使用的存储容器就是 TreeMap。
与HashSet于HashMap完全类似的是， TreeSet里面绝大部分方法都是直接调用TreeMap的方法来实现的，这一点读者可以自行参阅TreeSet的源码，此处就不再给出了。

设计理念

红黑树

TreeMap是用红黑树作为基础实现的，红黑树是一种二叉搜索树，我们想回忆一下二叉搜索树的一些性质。
二叉搜索树

二叉搜索树的关键特点: 左子树的值小于根节点，右子树的值大于根节点

二叉搜索树的优势在于：

  1. 每进行一次判断就能将问题的规模减少一半。
  2. 所以如果二叉搜索树是平衡的话，查找元素的时间复杂度为log(n) ,也就是树的高度。

如果说二叉搜索树将问题规模减少了一半，那么三叉搜索树不就是将问题规模减少了三分之二，这个不是更好吗？以此类推，我们还可以有四叉搜索树，五叉搜索书…..对于更一般的情况:

n个元素，K叉树搜索树的K为多少是效率是最好的？ K=2时吗？

K叉搜索树
如果大家按照我上面的分析，很可能陷入一个误区，就是

三叉搜索树在将问题规模减少三分之二时，所需要比较操作的次数是两次(二叉搜索树再将问题规模减少一半时，只需要一次比较操作)

我们不能把这两次给忽略了，对于更一般的情况

n个元素，K 叉树搜索树需要的平均比较次数为 k*log(n/k).

对于极端的情况 k = n时， K叉树就转化为了线性表了，复杂度也就是O(n)了，如果用数学角度来解决这个问题，相当于：

n为固定值是，k 取何值时， k*log(n/k)的取值最小？

klog(n/k)根据对数的运算规则可以转化为ln(n)k/ln(k)，ln(n)为常数，所以相当于k/ln(k)的极小值。

当k=e 时，k/ln(k)取最小值。

运算上述的式子，在k = 3时 比 k= 2 时得到的结果还要小，那就是说三叉搜索树应该比二叉搜索树更好一些，但是为什么二叉树更流行能？在stackoverflow上找到了答案：

现在的CPU可以针对二重逻辑(binary logic)的代码优化，三重逻辑会被分解为多个二重逻辑

这样也就大概的能理解为什么二叉树这么流行了，就是因为进行一次比较操作，我们最多可以将问题规模减少一半。

红黑树的性质

叶子节点为图中的NIL节点，国内一些教材中没有这个NIL节点，，我们在画图时有时也会省略这些NIL节点，但是我们需要明确，当我们说叶子节点时，指的就是这些NIL节点。

红黑树通过下面5条规则，保证了树是平衡的：
1、树的节点只有红与黑两种颜色
2、根节点为黑色的
3、叶子节点为黑色的
4、红色节点的子节点必定是黑色的
5、从任意一节点出发，到其后继的叶子节点的路径中，黑色节点的数目相同

满足了上面5个条件后，就能保证:根节点到叶子节点的最长路径不会的大于根节点到叶子最短路径的2倍，其实这个很好理解，主要是用了性质4与5这里说明一下:

假设根节点到叶子节点最短的路径中，黑色节点数目为B，那么根据性质5，根节点到叶子节点的最长路径中，黑色节点数目也是B，最长的情况就是每两个黑色节点中将有个红色节点（也就是红黑相间的情况），所以红色节点最多为B-1个，这样就能保证上面的结论了。

在HashMao的每一个节点被称为Entry,从二叉树的知识可以推测出在红黑树中，一个节点应该具备的基本属性，到底是不是呢？那就看下面的源码吧！

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
static final class Entry<K,V> implements Map.Entry<K,V> {
    //节点key
    K key;
    //节点值
    V value;
    //左子树节点
    Entry<K,V> left;
    //右子树节点
    Entry<K,V> right;
    //父节点
    Entry<K,V> parent;
    //节点颜色
    boolean color = BLACK;
    /**
     * Make a new cell with given key, value, and parent, and with
     * {@code null} child links, and BLACK color.
     */
    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }
    /**
     * Returns the key.
     *
     * @return the key
     */
    public K getKey() {
        return key;
    }
    /**
     * Returns the value associated with the key.
     *
     * @return the value associated with the key
     */
    public V getValue() {
        return value;
    }
    /**
     * Replaces the value currently associated with the key with the given
     * value.
     *
     * @return the value associated with the key before this method was
     *         called
     */
    public V setValue(V value) {
        V oldValue = this.value;
        this.value = value;
        return oldValue;
    }
    public boolean equals(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<?,?> e = (Map.Entry<?,?>)o;
        return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
    }
    public int hashCode() {
        int keyHash = (key==null ? 0 : key.hashCode());
        int valueHash = (value==null ? 0 : value.hashCode());
        return keyHash ^ valueHash;
    }
    public String toString() {
        return key + "=" + value;
    }
}

下面我们进行TreeMap的测试：

1
2
3
4
5
6
7
8
9
10
11
12
public class TestDemo {
    private String hello;
    public  static void  main(String[] args){
        TreeMap   tree = new TreeMap<String , Double>();
        tree.put("ccc", 89.0);
        tree.put("aaa", 80.0);
        tree.put("zzz", 80.0);
        tree.put("bbb", 89.0);
        System.out.println(tree);
       // TreeSet  treeser;
    }
}

当程序执行tree.put（”ccc”, 89.0）时，系统将直接把”ccc”-89.0这个Entry放入Map中，这个Entry就是该红黑树”根节点”，接着程序tree.put(“aaa”, 80.0);时，程序将会将”aaa”-80.0 作为新节点添加到已有的红黑树中。以后向TreeMap中放入一个key-value对，系统都需要将该Entry当成一个新节点，添加成已有红黑树中，通过这种方式， 可以保证TreeMap中所有的key 总是由按照红黑树的生成规则排列。

Put()方法

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
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;
		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 {//如果没有定义比较器，那么key必须实现Comparable接口
			if (key == null)//不允许空键
				throw new NullPointerException();
			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);
		}
		//找到插入点之后，创建新结点，插入之。
		Entry<K,V> e = new Entry<>(key, value, parent);
		if (cmp < 0)//判断是挂到左边还是右边
			parent.left = e;
		else
			parent.right = e;
		fixAfterInsertion(e);//进行着色和旋转等操作修复红黑树
		size++;
		modCount++;
		return null;
	}

说明:

  • TreeMap的查询和更新操作都设计比较操作，故而TreeMap的键必须实现Comparable接口或者构造时得传入比较器（既然是实现了Comparable接口又传入了比较器情况下，比较器优先）；
  • put操作不允许null键，但是值（value） 允许null；
  • 键重复的情况下，新值将会覆盖掉旧值。

重要的方法

get()方法

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

调用getEntry方法查询指定键值：

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
final Entry<K,V> getEntry(Object key) {//跟普通二叉排序树的查询操作一致
		// Offload comparator-based version for sake of performance
		if (comparator != null)//存在比较器
			return getEntryUsingComparator(key);//根据比较器定义的比较规则查找
		if (key == null)
			throw new NullPointerException();
		Comparable<? super K> k = (Comparable<? super K>) key;
		Entry<K,V> p = root;
		while (p != null) {//根据Comparable接口定义的比较规则查找
			int cmp = k.compareTo(p.key);
			if (cmp < 0)//待查结点在左子树
				p = p.left;
			else if (cmp > 0)//待查结点在右子树
				p = p.right;
			else
				return p;
		}
		return null;//没找到
	}
 final Entry<K,V> getEntryUsingComparator(Object key) {//根据比较器定义的比较规则查找
		K k = (K) key;
		Comparator<? super K> cpr = comparator;
		if (cpr != null) {
			Entry<K,V> p = root;
			while (p != null) {
				int cmp = cpr.compare(k, p.key);
				if (cmp < 0)
					p = p.left;
				else if (cmp > 0)
					p = p.right;
				else
					return p;
			}
		}
		return null;
	}

从上面的查找方法可以得出，对比HashMap近乎O(1)的查找复杂符，TreeMap显得略有些不足。

remove()方法

1
2
3
4
5
6
7
8
public V remove(Object key) {
		Entry<K,V> p = getEntry(key);//首先找到待删结点
		if (p == null)//判断是否找到
			return null;
		V oldValue = p.value;
		deleteEntry(p);//删除结点
		return oldValue;
	}

虽然看上去寥寥几行的代码，其实逻辑十分复杂，具体体现在删除节点后恢复操作。 我们看下面的deletEntry()方法。

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
private void deleteEntry(Entry<K,V> p) {//删除一个结点
		modCount++;
		size--;
		// If strictly internal, copy successor's element to p and then make p
		// point to successor.
		if (p.left != null && p.right != null) {//p的左右孩子都存在
			Entry<K,V> s = successor(p);//找到p的直接后继(顺着p右子树一直向左)
			p.key = s.key;//用直接后继替代p
			p.value = s.value;
			p = s;
		} // p has 2 children
		//下面操作将释放s结点，并修复红黑树
		// Start fixup at replacement node, if it exists.
		Entry<K,V> replacement = (p.left != null ? p.left : p.right);
		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;
			// Null out links so they are OK to use by fixAfterDeletion.
			p.left = p.right = p.parent = null;
			// Fix replacement
			if (p.color == BLACK)
				fixAfterDeletion(replacement);//修复红黑树
		} else if (p.parent == null) { // return if we are the only node.
			root = 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;
			}
		}
	}

successtor函数用于找一个节点的中序后继：迭代器遍历操作正是基于successtor操作完成的，所以遍历TreeMap得到的键值对是有序的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 {//如果不存在右子树
			Entry<K,V> p = t.parent;//顺着父亲，向上搜索
			Entry<K,V> ch = t;
			while (p != null && ch == p.right) {//如果当前结点是父结点的右孩子，那么继续向上
				ch = p;
				p = p.parent;
			}
			return p;
		}
	}

对称的，还有查找直接前驱的方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
		}
	}

总结

  1. TreeMap的实现基于红黑树；
  2. TreeMap不允许插入null键，但允许null值；
  3. TreeMap线程不安全；
  4. 插入节点时，若键重复，则新值会覆盖旧值；
  5. TreeMap是根据key进行排序的，它的排序和定位需要依赖比较器或覆写Comparable接口，也因此不需要key覆写hashCode方法和equals方法，就可以排除掉重复的key，而HashMap的key则需要通过覆写hashCode方法和equals方法来确保没有重复的key，要求key必须实现Comparable接口，或者初始化传入Comparator版本比较器；
  6. 遍历TreeMap得到的结果集是有序的（中序遍历）；
  7. TreeMap的查询、插入、删除效率均没有HashMap高，一般只有要对key排序时才用TreeMap。TreeMap的各项操作的平均时间复杂为O（log（n））

TreeSet和HashSet的源码不再进行剖析，二者分别是基于TreeMap和HashMap实现的，只是对应的节点中只有key，而没有value，因此对TreeMap 和HashMap比较了解的话，对TreeSet和HashMap的理解就会非常容易。

坚持原创技术分享，您的支持将鼓励我继续创作！