Java Map 和 Set（五）：剖析 TreeSet

1. 下面代码输出结果为

Set<String> words = new TreeSet<String> ();

words.addAll(Arrays.asList(new String[] {
    "tree", "map", "hash", "map"
}));

for(String w : words) {
    System.out.print(w + " ");
}

• 结果：hash map tree
• 分析
  • TreeSet 经常也只是当作 Set 使用
  • TreeSet 实现了两点：去重和有序

2. 接上题，如果希望忽略大小写进行比较排序，代码实现为

Set<String> words = new TreeSet<String> (new Comparator<String> () {
    @Override
    public int compare(String o1, String o2) {
        return o1.compareToIgnoreCase(o2);
    }
});

words.addAll(Arrays.asList(new String[] {
    "tree", "map", "hash", "Map"
}));

System.out.println(words);

• 结果：[hash, map, tree]
• 分析
  • Set 是去重的，去重是基于比较的结果，结果为 0 即视为相同
  • map 和 Map 虽然不同，但比较结果为 0，所以只会保留第一个元素

3. TreeSet 的实现原理

• TreeSet 内部是基于 TreeMap 实现的

• TreeSet 内部成员有

  private transient NavigableMap<E, Object> m;
  private static final Object PRESENT = new Object();

• m 就是背后的那个 TreeMap，这里用的是更为通用的接口类型 NavigableMap，PRESENT 就是那个固定的共享值

• TreeSet 的方法实现主要就是调用 m 的方法

• TreeSet 的特点与 TreeMap 基本一致

  • 按键有序，TreeMap 同样实现了 SortedMap 和 NavigableMap 接口，可以方便地根据键的顺序进行查找，如第一个、最后一个、某一范围的键、临近键等
  • 为了按键有序，TreeMap 要求键实现 Comparable 接口或通过构造方法提供一个 Comparator 比较器对象
  • 根据键保存、查找、删除的效率比较高，为 O(h)，h 为树的高度，在树平衡的情况下，h = log2(N)，N 为节点数
  • 不要求排序，优先考虑 HashMap；要求排序，考虑 TreeMap