通过分析 JDK 源代码研究 TreeMap 红黑树算法实现

核心提示： 从上面代码可以看出，TreeSet 的 ① 号、② 号构造器的都是新建一个 TreeMap 作为实际存储 Set 元素的容器，通过分析 JDK 源代码研究 TreeMap 红黑树算法实现(2)，而另外 2 个构造器则分别依赖于 ① 号和 ② 号构造器，由此可见，添加成已有红黑树中，通过这种方式就

从上面代码可以看出，TreeSet 的 ① 号、② 号构造器的都是新建一个 TreeMap 作为实际存储 Set 元素的容器，而另外 2 个构造器则分别依赖于 ① 号和 ② 号构造器，由此可见，TreeSet 底层实际使用的存储容器就是 TreeMap。

与 HashSet 完全类似的是，TreeSet 里绝大部分方法都是直接调用 TreeMap 的方法来实现的，这一点读者可以自行参阅 TreeSet 的源代码，此处就不再给出了。

对于 TreeMap 而言，它采用一种被称为“红黑树”的排序二叉树来保存 Map 中每个 Entry —— 每个 Entry 都被当成“红黑树”的一个节点对待。例如对于如下程序而言：

　public　class　TreeMapTest　
　{　
　　public　static　void　main(String[]　args)　
　　{　
　　　　TreeMap<String　,　Double>　map　=　
　　　　　　new　TreeMap<String　,　Double>();　
　　　　map.put("ccc"　,　89.0);　
　　　　map.put("aaa"　,　80.0);　
　　　　map.put("zzz"　,　80.0);　
　　　　map.put("bbb"　,　89.0);　
　　　　System.out.println(map);　
　　}　
　}　

当程序执行 map.put("ccc" , 89.0); 时，系统将直接把 "ccc"-89.0 这个 Entry 放入 Map 中，这个 Entry 就是该“红黑树”的根节点。接着程序执行 map.put("aaa" , 80.0); 时，程序会将 "aaa"-80.0 作为新节点添加到已有的红黑树中。

以后每向 TreeMap 中放入一个 key-value 对，系统都需要将该 Entry 当成一个新节点，添加成已有红黑树中，通过这种方式就可保证 TreeMap 中所有 key 总是由小到大地排列。例如我们输出上面程序，将看到如下结果（所有 key 由小到大地排列）：