| java集合类TreeMap和TreeSet及红黑树 | 您所在的位置：网站首页 › java的树 › java集合类TreeMap和TreeSet及红黑树 |
java集合类TreeMap和TreeSet及红黑树
|
看这篇博客前，我觉得很有必要先看下我之前的几篇博客 Red-Black Trees（红黑树） （TreeMap底层的实现就是用的红黑树数据结构）探索equals()和hashCode()方法 （TreeMap/TreeSet实现使用到的核心方法）java中的HashTable,HashMap和HashSet （同为java集合类，对比下他们的区别）java中Map,List与Set的区别 （TreeMap/TreeSet最主要的区别就是分别实现了Map和Set接口） 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,基本上就弄懂了TreeSet。 2. TreeSet实现原理 ------------------------------------------------------- TreeMap 的实现使用了红黑树数据结构，也就是一棵自平衡的排序二叉树，这样就可以保证快速检索指定节点。对于 TreeMap 而言，它采用一种被称为“红黑树”的排序二叉树来保存 Map 中每个 Entry —— 每个 Entry 都被当成“红黑树”的一个节点对待。举例： [java] view plain copy print ? 
public class TreeMapTest { public static void main(String[] args) { TreeMap map = new TreeMap(); 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 由小到大地排列）： {aaa=80.0, bbb=89.0, ccc=89.0, zzz=80.0} TreeMap的添加节点（put()方法） 对于 TreeMap 而言，由于它底层采用一棵“红黑树”来保存集合中的 Entry，这意味这 TreeMap 添加元素、取出元素的性能都比 HashMap 低（红黑树和Hash数据结构上的区别）：当 TreeMap 添加元素时，需要通过循环找到新增 Entry 的插入位置，因此比较耗性能；当从 TreeMap 中取出元素时，需要通过循环才能找到合适的 Entry，也比较耗性能。但 TreeMap、TreeSet 比 HashMap、HashSet 的优势在于：TreeMap 中的所有 Entry 总是按 key 根据指定排序规则保持有序状态，TreeSet 中所有元素总是根据指定排序规则保持有序状态。 为了很好的理解TreeMap你必须先理解红黑树，然而红黑树又是一种特殊的二叉查找树，所以你必须先看两篇博客 Binary search tree（二叉查找树）Red-Black Trees（红黑树） 因为我这两篇博客已经讲了很多相关知识，所以这里就不列出来了。 掌握红黑树数据结构的理论之后，我们来分析TreeMap添加节点（TreeMap 中使用 Entry 内部类代表节点）的实现，TreeMap 集合的 put(K key, V value) 方法实现了将 Entry 放入排序二叉树中，下面是该方法的源代码： [java] view plain copy print ?
public V put(K key, V value) { // 先以 t 保存链表的 root 节点 Entry t = root; // 如果 t==null，表明是一个空链表，即该 TreeMap 里没有任何 Entry if (t == null) { // 将新的 key-value 创建一个 Entry，并将该 Entry 作为 root root = new Entry(key, value, null); // 设置该 Map 集合的 size 为 1，代表包含一个 Entry size = 1; // 记录修改次数为 1 modCount++; return null; } int cmp; Entry parent; Comparator |
【本文地址】
公司简介
联系我们