0%

Java Map 和 Set(五):剖析 TreeSet

1. 下面代码输出结果为

1
2
3
4
5
6
7
8
9
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. 接上题,如果希望忽略大小写进行比较排序,代码实现为

1
2
3
4
5
6
7
8
9
10
11
12
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 即视为相同
    • mapMap 虽然不同,但比较结果为 0,所以只会保留第一个元素

3. TreeSet 的实现原理

  • TreeSet 内部是基于 TreeMap 实现的

  • TreeSet 内部成员有

    1
    2
    private transient NavigableMap<E, Object> m;
    private static final Object PRESENT = new Object();
  • m 就是背后的那个 TreeMap,这里用的是更为通用的接口类型 NavigableMapPRESENT 就是那个固定的共享值

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

  • TreeSet 的特点与 TreeMap 基本一致

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