Java集合詳解--什麼是Set

簡述

Set和List一樣，也繼承于Collection,是集合的一種。和List不同的是，Set内部實作是基于Map的，是以Set取值時不保證資料和存入的時候順序一緻，并且不允許空值，不允許重複值。

然後我們來看下Set的繼承結構

可以看出,Set主要有2個實作方式，一個是TreeSet，另一個是HashSet

這個Set的特點，主要由其内部的Map決定的，可以負責人的說一句，Set就是Map的一個馬甲

HashSet和TreeSet

就如它的名字一樣，HashSet主要由HashMap實作

如果調用HashSet的無參構造函數，那麼就會使用預設的HashMap，初始化Size為16，擴張系數為0.75

//簡單看下HashMap的幾個主要資料執行操作都是間接的調用了内部的HashMap的資料操作
    //比較有意思的是，從add()方法看出，HashSet的值是HashMap的key，
    //HashMap的value是寫死的PRESENT
    //是以周遊HashSet的值，也就是周遊HashMap的KeyEntry
    /**
     * Returns an iterator over the elements in this set.  The elements
     * are returned in no particular order.
     *
     * @return an Iterator over the elements in this set
     * @see ConcurrentModificationException
     */
    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }

    /**
     * Returns the number of elements in this set (its cardinality).
     *
     * @return the number of elements in this set (its cardinality)
     */
    public int size() {
        return map.size();
    }

    /**
     * Returns <tt>true</tt> if this set contains no elements.
     *
     * @return <tt>true</tt> if this set contains no elements
     */
    public boolean isEmpty() {
        return map.isEmpty();
    }

    /**
     * Returns <tt>true</tt> if this set contains the specified element.
     * More formally, returns <tt>true</tt> if and only if this set
     * contains an element <tt>e</tt> such that
     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
     *
     * @param o element whose presence in this set is to be tested
     * @return <tt>true</tt> if this set contains the specified element
     */
    public boolean contains(Object o) {
        return map.containsKey(o);
    }

    /**
     * Adds the specified element to this set if it is not already present.
     * More formally, adds the specified element <tt>e</tt> to this set if
     * this set contains no element <tt>e2</tt> such that
     * <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.
     * If this set already contains the element, the call leaves the set
     * unchanged and returns <tt>false</tt>.
     *
     * @param e element to be added to this set
     * @return <tt>true</tt> if this set did not already contain the specified
     * element
     */
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

    /**
     * Removes the specified element from this set if it is present.
     * More formally, removes an element <tt>e</tt> such that
     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>,
     * if this set contains such an element.  Returns <tt>true</tt> if
     * this set contained the element (or equivalently, if this set
     * changed as a result of the call).  (This set will not contain the
     * element once the call returns.)
     *
     * @param o object to be removed from this set, if present
     * @return <tt>true</tt> if the set contained the specified element
     */
    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }

    /**
     * Removes all of the elements from this set.
     * The set will be empty after this call returns.
     */
    public void clear() {
        map.clear();
    }
           

TreeSet和HashMap的處理方式相似，這裡就不重複展開，差別的地方是，TreeSet内部的是一顆紅黑樹，至于紅黑樹的特點，再下一章會詳細展開

comparator和comparable

由于Set的實作都基于Map，是以操作都十分簡單，是以在這章把Map會提到的comparator和comparable提前分析

直覺的翻譯我們也可以得出，這2個東西都是和排序有關。

comparator和comparable都是接口。

1.comparable

先來看看comparable

Comparable 接口強行對實作它的每個類的對象進行整體排序，Java稱這種排序為自然排序，對比于comparator，又稱為内部排序

Comparable接口隻有一個方法

public int compareTo(T o);
           

對于需要排序的對象，隻要繼承這個接口，實作這個compareTo()方法就可以了，（T o）代表傳入的資料，需要進行比較的對象。如果位于對象 o 之前，傳回負值，如果兩個對象在排序中位置相同，則傳回 0 ，如果位于對象 o 後面，則傳回正值。

在注釋中又說到，希望把comparaTo()和equal(）聯系起來。因為這個2個方法都是對對象進行比較，如果這2個方法對同一個比較對象産生不同的結果，會造成邏輯上的困惑。

舉個例子,

class Test{
    int compareFactor;

    //setCompareFactor...getCompareFactor...

    public int compareTo(T o){
    if(o == null){
    //這裡是注釋上建議這麼做的，如果傳入一個空值，需要抛出一個異常
        throw new RuntimeException ("test");
    }

    //如果相等，表示處于比較的同一個位置
    if(this.compareFactor == ((Test)o).getCompareFactor()){
        return ;
    } else if(this.compareFactor > ((Test)o).getCompareFactor()){
        return ;
    } else {
        return ;
    }

}

//使用的時候隻要調用Collections或者Array的sort（）方法就好了
Collections.sort(list);

           

2.Comparator

相對于Comparable ，comparator又稱為外部排序。對于一些已經封裝好的對象，我們在盡量不修改已有結構的基礎上，通過實作Comparator類來建立一個比較器，然後通過該比較器來對類進行排序。Comparator 接口其實就是一種政策模式的實踐

Comparator内部包含了2個方法

int compare(T o1, T o2);

boolean equals(Object obj);
           

由于所有java對象都繼承于Object，是以equals(Object obj)已經被實作了，我們隻要實作compare(T o1, T o2)方法就好了。實作的思路和comparable一樣，隻不過comparable是和自己比較，Comparator是對于兩個對象進行比較。

3.異同

Comparable是由對象自己實作的，一旦一個對象封裝好了，compare的邏輯也就定了，如果我們需要對同一個對象增加一個字段的排序就比較麻煩，又要修改對象本身。比如淘寶的購買頁面，增加一種受歡迎度的排序，就需要修改對象内部compare方法。好處是對外部不可見，調用者無需知道排序邏輯，隻要調用排序即可，類似于靜态綁定。

而Comparator由外部實作，比較靈活，争對上述問題，隻要新增一個Comparator即可。缺點是所有排序邏輯對外部暴露，需要對象外部實作。不過這裡的外部僅指對象的外部，也可以由API的開發者封裝好所有的Comparator，對調用者隐藏内部邏輯。好處是很靈活，随時可以增加一種排序方法，隻要對象内部字段支援，類似動态綁定。

總結

在這一章節中簡單介紹了Set的結構，實作原理。Set是Map的一個馬甲，主要邏輯都交給Map實作。在下一章中，會詳細介紹Map的實作原理。

還介紹了與排序相關的兩個接口comparator和comparable