黑马程序员技术交流社区

标题: java集合类TreeMap和TreeSet [打印本页]

---

作者: JohnChan    时间: 2016-5-30 23:26
标题: java集合类TreeMap和TreeSet

TreeMap 和 TreeSet 是 Java Collection Framework 的两个重要成员，其中 TreeMap 是 Map 接口的常用实现类，而 TreeSet 是 Set 接口的常用实现类。虽然 TreeMap 和TreeSet 实现的接口规范不同，但 TreeSet 底层是通过 TreeMap 来实现的（如同HashSet底层是是通过HashMap来实现的一样），因此二者的实现方式完全一样。而 TreeMap 的实现就是红黑树算法。

1. TreeSet和TreeMap的关系

-----------------------------------------------------

与HashSet完全类似，TreeSet里面绝大部分方法都市直接调用TreeMap方法来实现的。

相同点：

• TreeMap和TreeSet都是有序的集合，也就是说他们存储的值都是拍好序的。
  

• TreeMap和TreeSet都是非同步集合，因此他们不能在多线程之间共享，不过可以使用方法Collections.synchroinzedMap()来实现同步
• 运行速度都要比Hash集合慢，他们内部对元素的操作时间复杂度为O(logN)，而HashMap/HashSet则为O(1)。
  

不同点：

• 最主要的区别就是TreeSet和TreeMap非别实现Set和Map接口
  

• TreeSet只存储一个对象，而TreeMap存储两个对象Key和Value（仅仅key对象有序）
• TreeSet中不能有重复对象，而TreeMap中可以存在
• TreeMap的底层采用红黑树的实现，完成数据有序的插入，排序。
  

红黑树的特点：

• 性质 1：每个节点要么是红色，要么是黑色。
• 性质 2：根节点永远是黑色的。
• 性质 3：所有的叶节点都是空节点（即 null），并且是黑色的。
• 性质 4：每个红色节点的两个子节点都是黑色。（从每个叶子到根的路径上不会有两个连续的红色节点）
• 性质 5：从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。
  

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2