程式師世界 >> 編程語言 >> JAVA編程 >> JAVA綜合教程 >> 計算機程序的思維邏輯 (44)，思維44

計算機程序的思維邏輯 (44)，思維44

編輯：JAVA綜合教程

計算機程序的思維邏輯 (44)，思維44

41節介紹了HashSet，我們提到，HashSet有一個重要局限，元素之間沒有特定的順序，我們還提到，Set接口還有另一個重要的實現類TreeSet，它是有序的，與HashSet和HashMap的關系一樣，TreeSet是基於TreeMap的，上節我們介紹了TreeMap，本節我們來詳細討論TreeSet。

下面，我們先來看TreeSet的用法，然後看實現原理，最後總結分析TreeSet的特點。

基本用法

構造方法

TreeSet的基本構造方法有兩個：

public TreeSet()
public TreeSet(Comparator<? super E> comparator)

默認構造方法假定元素實現了Comparable接口，第二個使用傳入的比較器，不要求元素實現Comparable。

基本例子

TreeSet經常也只是當做Set使用，只是希望迭代輸出有序，如下面代碼所示：

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實現了兩點：排重和有序。

如果希望不同的排序，可以傳遞一個Comparator，如下所示：

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，所以只會保留第一個元素。

以上就是TreeSet的基本用法，簡單易用。不過，因為有序，TreeSet還實現了NavigableSet和SortedSet接口，NavigableSet擴展了SortedSet，此外，TreeSet還有幾個構造方法，我們來看下。

高級用法

SortedSet接口

SortedSet接口與SortedMap接口類似，具體定義為：

public interface SortedSet<E> extends Set<E> {
    Comparator<? super E> comparator();
    SortedSet<E> subSet(E fromElement, E toElement);
    SortedSet<E> headSet(E toElement);
    SortedSet<E> tailSet(E fromElement);
    E first();
    E last();
}

first()返回第一個元素，last()返回最後一個，headSet/tailSet/subSet都返回一個視圖，包括原Set中的一定取值范圍的元素，區別在於范圍：

headSet：嚴格小於toElement的所有元素
tailSet: 大於等於fromElement的所有元素
subSet: 大於等於fromElement，且小於toElement的所有元素

與之前介紹的視圖概念一樣，對返回視圖的操作會直接影響原Set。

comparator()返回使用的比較器，如果沒有自定義的比較器，返回值為null。

我們來看一段簡單的示例代碼，以增強直觀感受，輸出用注釋說明：

SortedSet<String> set = new TreeSet<String>();
set.addAll(Arrays.asList(new String[]{
    "c", "a", "b", "d","f"    
}));

System.out.println(set.first()); //a
System.out.println(set.last()); //f
System.out.println(set.headSet("b"));//[a]
System.out.println(set.tailSet("d"));//[d, f]
System.out.println(set.subSet("b", "e")); //[b, c, d]
set.subSet("b", "e").clear(); //會從原set中刪除
System.out.println(set); //[a, f]

NavigableSet接口

與NavigableMap類似，NavigableSet接口擴展了SortedSet，主要增加了一些查找鄰近元素的方法，比如：

E floor(E e); //返回小於等於e的最大元素
E lower(E e); // 返回小於e的最大元素
E ceiling(E e); //返回大於等於e的最小元素
E higher(E e); //返回大於e的最小元素

相比SortedSet中的視圖方法，NavigableSet增加了一些方法，以更為明確的方式指定返回值中是否包含邊界值，如：

NavigableSet<E> headSet(E toElement, boolean inclusive);
NavigableSet<E> tailSet(E fromElement, boolean inclusive);
NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                           E toElement,   boolean toInclusive);

NavigableSet也增加了兩個對頭尾的操作：

E pollFirst(); //返回並刪除第一個元素
E pollLast(); //返回並刪除最後一個元素

此外，NavigableSet還有如下方法，以方便逆序訪問：

NavigableSet<E> descendingSet();
Iterator<E> descendingIterator();

我們來看一段簡單的示例代碼，以增強直觀感受，輸出用注釋說明：

NavigableSet<String> set = new TreeSet<String>();
set.addAll(Arrays.asList(new String[]{
    "c", "a", "b", "d","f"    
}));
System.out.println(set.floor("a")); //a
System.out.println(set.lower("b")); //a
System.out.println(set.ceiling("d"));//d
System.out.println(set.higher("c"));//d
System.out.println(set.subSet("b", true, "d", true)); //[b, c, d]
System.out.println(set.pollFirst()); //a
System.out.println(set.pollLast()); //f
System.out.println(set.descendingSet()); //[d, c, b]

其他構造方法

TreeSet的其他構造方法為：

public TreeSet(Collection<? extends E> c)
public TreeSet(SortedSet<E> s)
TreeSet(NavigableMap<E,Object> m)

前兩個都是以一個已有的集合為參數，將其中的所有元素添加到當前TreeSet，區別在於，在第一個中，比較器為null，假定元素實現了Comparable接口，而第二個中，比較器設為和參數SortedSet中的一樣。

第三個不是public的，是內部用的。

基本實現原理

41節介紹過，HashSet是基於HashMap實現的，元素就是HashMap中的鍵，值是一個固定的值，TreeSet是類似的，它是基於TreeMap實現的，我們具體來看一下代碼，先看其內部組成。

內部組成

TreeSet的內部有如下成員：

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

m就是背後的那個TreeMap，這裡用的是更為通用的接口類型NavigableMap，PRESENT就是那個固定的共享值。

TreeSet的方法實現主要就是調用m的方法，我們具體來看下。

構造方法

幾個構造方法的代碼為：

TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}

public TreeSet() {
    this(new TreeMap<E,Object>());
}

public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}

public TreeSet(Collection<? extends E> c) {
    this();
    addAll(c);
}

public TreeSet(SortedSet<E> s) {
    this(s.comparator());
    addAll(s);
}

代碼都比較簡單，就不解釋了。

添加元素

add方法的代碼為：

public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}

就是調用map的put方法，元素e用作鍵，值就是固定值PRESENT，put返回null表示原來沒有對應的鍵，添加成功了。

檢查是否包含元素

代碼為：

public boolean contains(Object o) {
    return m.containsKey(o);
}

就是檢查map中是否包含對應的鍵。

刪除元素

代碼為：

public boolean remove(Object o) {
    return m.remove(o)==PRESENT;
}

就是調用map的remove方法，返回值為PRESENT表示原來有對應的鍵且刪除成功了。

子集視圖

subSet方法的代碼：

public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                              E toElement,   boolean toInclusive) {
    return new TreeSet<>(m.subMap(fromElement, fromInclusive,
                                   toElement,   toInclusive));
}

先調用subMap方法獲取NavigatebleMap的子集，然後調用內部的TreeSet構造方法。

頭尾操作

代碼為：

public E first() {
    return m.firstKey();
}

public E last() {
    return m.lastKey();
}

 

public E pollFirst() {
    Map.Entry<E,?> e = m.pollFirstEntry();
    return (e == null) ? null : e.getKey();
}

public E pollLast() {
    Map.Entry<E,?> e = m.pollLastEntry();
    return (e == null) ? null : e.getKey();
}

代碼都比較簡單，就不解釋了。

逆序遍歷

代碼為：

public Iterator<E> descendingIterator() {
    return m.descendingKeySet().iterator();
}

public NavigableSet<E> descendingSet() {
    return new TreeSet<>(m.descendingMap());
}

也很簡單。

實現原理小結

TreeSet的實現代碼都比較簡單，主要就是調用內部NavigatableMap的方法。

TreeSet特點分析

與HashSet相比，TreeSet同樣實現了Set接口，但內部基於TreeMap實現，而TreeMap基於大致平衡的排序二叉樹 - 紅黑樹，這決定了它有如下特點：

沒有重復元素
添加、刪除元素、判斷元素是否存在，效率比較高，為O(log2(N))，N為元素個數。
有序，TreeSet同樣實現了SortedSet和NavigatableSet接口，可以方便的根據順序進行查找和操作，如第一個、最後一個、某一取值范圍、某一值的鄰近元素等。
為了有序，TreeSet要求元素實現Comparable接口或通過構造方法提供一個Comparator對象。

小結

本節介紹了TreeSet的用法和實現原理，在用法方面，它實現了Set接口，但有序，同樣實現了SortedSet和NavigatableSet接口，在內部實現上，它使用了TreeMap，代碼比較簡單。

至此，我們已經介紹完了Java中主要常見的容器接口和實現類，接口主要有隊列(Queue)，雙端隊列(Deque)，列表(List)，Map和Set，實現類有ArrayList, LinkedList, HashMap, TreeMap, HashSet和TreeSet。

關於接口Queue, Deque, Map和Set，Java容器類中還有其他一些實現類，它們各有特點，讓我們在接下來的幾節中繼續探索。

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

未完待續，查看最新文章，敬請關注微信公眾號“老馬說編程”(掃描下方二維碼)，從入門到高級，深入淺出，老馬和你一起探索Java編程及計算機技術的本質。用心原創，保留所有版權。