1.Set

上一篇，我們介紹Java中的List集合。本篇，讓我們繼續(xù)學(xué)習(xí)，來(lái)了解下Set集合；

Set繼承于Collection接口，是一個(gè)不允許出現(xiàn)重復(fù)元素，并且無(wú)序的集合，主要有HashSet和TreeSet兩大實(shí)現(xiàn)類。

在判斷重復(fù)元素的時(shí)候，Set集合會(huì)調(diào)用hashCode()和equal()方法來(lái)實(shí)現(xiàn)。

HashSet是哈希表結(jié)構(gòu)，主要利用HashMap的key來(lái)存儲(chǔ)元素，計(jì)算插入元素的hashCode來(lái)獲取元素在集合中的位置；

TreeSet是紅黑樹結(jié)構(gòu)，每一個(gè)元素都是樹中的一個(gè)節(jié)點(diǎn)，插入的元素都會(huì)進(jìn)行排序；

Set集合框架結(jié)構(gòu)：

image

1.1 Set常用方法

與List接口一樣，Set接口也提供了集合操作的基本方法。

但與List不同的是，Set還提供了equals(Object o)和hashCode()，供其子類重寫，以實(shí)現(xiàn)對(duì)集合中插入重復(fù)元素的處理；

public interface Set<E> extends Collection<E> {

    A:添加功能
    boolean add(E e);
    boolean addAll(Collection<? extends E> c);

    B:刪除功能
    boolean remove(Object o);
    boolean removeAll(Collection<?> c);
    void clear();

    C:長(zhǎng)度功能
    int size();

    D:判斷功能
    boolean isEmpty();
    boolean contains(Object o);
    boolean containsAll(Collection<?> c);
    boolean retainAll(Collection<?> c); 

    E:獲取Set集合的迭代器：
    Iterator<E> iterator();

    F:把集合轉(zhuǎn)換成數(shù)組
    Object[] toArray();
    <T> T[] toArray(T[] a);

    //判斷元素是否重復(fù)，為子類提高重寫方法
    boolean equals(Object o);
    int hashCode();
}

1.2 HashSet

HashSet實(shí)現(xiàn)Set接口，底層由HashMap(后面講解)來(lái)實(shí)現(xiàn)，為哈希表結(jié)構(gòu)，新增元素相當(dāng)于HashMap的key，value默認(rèn)為一個(gè)固定的Object。在我看來(lái)，HashSet相當(dāng)于一個(gè)閹割版的HashMap;

當(dāng)有元素插入的時(shí)候，會(huì)計(jì)算元素的hashCode值，將元素插入到哈希表對(duì)應(yīng)的位置中來(lái)；

它繼承于AbstractSet，實(shí)現(xiàn)了Set, Cloneable, Serializable接口。

(1)HashSet繼承AbstractSet類，獲得了Set接口大部分的實(shí)現(xiàn)，減少了實(shí)現(xiàn)此接口所需的工作，實(shí)際上是又繼承了AbstractCollection類；

(2)HashSet實(shí)現(xiàn)了Set接口，獲取Set接口的方法，可以自定義具體實(shí)現(xiàn)，也可以繼承AbstractSet類中的實(shí)現(xiàn)；

(3)HashSet實(shí)現(xiàn)Cloneable，得到了clone()方法，可以實(shí)現(xiàn)克隆功能；

(4)HashSet實(shí)現(xiàn)Serializable，表示可以被序列化，通過(guò)序列化去傳輸，典型的應(yīng)用就是hessian協(xié)議。

具有如下特點(diǎn)：

• 不允許出現(xiàn)重復(fù)因素；

• 允許插入Null值；

• 元素?zé)o序（添加順序和遍歷順序不一致）；

• 線程不安全，若2個(gè)線程同時(shí)操作HashSet，必須通過(guò)代碼實(shí)現(xiàn)同步；

1.3 HashSet基本操作

HashSet底層由HashMap實(shí)現(xiàn)，插入的元素被當(dāng)做是HashMap的key，根據(jù)hashCode值來(lái)確定集合中的位置，由于Set集合中并沒(méi)有角標(biāo)的概念，所以并沒(méi)有像List一樣提供get（）方法。當(dāng)獲取HashSet中某個(gè)元素時(shí)，只能通過(guò)遍歷集合的方式進(jìn)行equals()比較來(lái)實(shí)現(xiàn)；

public class HashSetTest {
    public static void main(String[] agrs){
        //創(chuàng)建HashSet集合：
        Set<String> hashSet = new HashSet<String>();
        System.out.println("HashSet初始容量大?。?+hashSet.size());

        //元素添加：
        hashSet.add("my");
        hashSet.add("name");
        hashSet.add("is");
        hashSet.add("jiaboyan");
        hashSet.add(",");
        hashSet.add("hello");
        hashSet.add("world");
        hashSet.add("!");
        System.out.println("HashSet容量大?。?+hashSet.size());

        //迭代器遍歷：
        Iterator<String> iterator = hashSet.iterator();
        while (iterator.hasNext()){
            String str = iterator.next();
            System.out.println(str);
        }
        //增強(qiáng)for循環(huán)
        for(String str:hashSet){
            if("jiaboyan".equals(str)){
                System.out.println("你就是我想要的元素:"+str);
            }
            System.out.println(str);
        }

        //元素刪除：
        hashSet.remove("jiaboyan");
        System.out.println("HashSet元素大?。? + hashSet.size());
        hashSet.clear();
        System.out.println("HashSet元素大小：" + hashSet.size());

        //集合判斷：
        boolean isEmpty = hashSet.isEmpty();
        System.out.println("HashSet是否為空：" + isEmpty);
        boolean isContains = hashSet.contains("hello");
        System.out.println("HashSet是否為空：" + isContains);
    }
}

1.4 HashSet元素添加分析

Set集合不允許添加重復(fù)元素，那么到底是個(gè)怎么情況呢？

來(lái)看一個(gè)簡(jiǎn)單的例子：

public class HashSetTest {

    public static void main(String[] agrs){
        //hashCode() 和 equals()測(cè)試：
        hashCodeAndEquals();
    }
    public static void hashCodeAndEquals(){
        //第一個(gè) Set集合：
        Set<String> set1 = new HashSet<String>();
        String str1 = new String("jiaboyan");
        String str2 = new String("jiaboyan");
        set1.add(str1);
        set1.add(str2);
        System.out.println("長(zhǎng)度："+set1.size()+",內(nèi)容為："+set1);

        //第二個(gè) Set集合：
        Set<App> set2 = new HashSet<App>();
        App app1 = new App();
        app1.setName("jiaboyan");

        App app2 = new App();
        app2.setName("jiaboyan");

        set2.add(app1);
        set2.add(app2);
        System.out.println("長(zhǎng)度："+set2.size()+",內(nèi)容為："+set2);

        //第三個(gè) Set集合：
        Set<App> set3 = new HashSet<App>();
        App app3 = new App();
        app3.setName("jiaboyan");
        set3.add(app3);
        set3.add(app3);
        System.out.println("長(zhǎng)度："+set3.size()+",內(nèi)容為："+set3);
    }
}

測(cè)試結(jié)果：

長(zhǎng)度：1,內(nèi)容為：[jiaboyan]
長(zhǎng)度：2,內(nèi)容為：[com.jiaboyan.collection.App@efb78af, com.jiaboyan.collection.App@5f3306ad]
長(zhǎng)度：1,內(nèi)容為：[com.jiaboyan.collection.App@1fb030d8]

可以看到，第一個(gè)Set集合中最終只有一個(gè)元素；第二個(gè)Set集合保留了2個(gè)元素；第三個(gè)集合也只有1個(gè)元素；

究竟是什么原因呢？

讓我們來(lái)看看HashSet的add(E e)方法：

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

在底層HashSet調(diào)用了HashMap的put(K key, V value)方法:

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

通過(guò)查看以上的源碼，我們可以了解到：實(shí)際的邏輯都是在HashMap的put()方法中。

int hash = hash(key) 對(duì)傳入的key計(jì)算hash值；

int i = indexFor(hash, table.length) 對(duì)hash值進(jìn)行轉(zhuǎn)換，轉(zhuǎn)換成數(shù)組的index(HashMap中底層存儲(chǔ)使用了Entry<K,V>[]數(shù)組)；

for (Entry<K,V> e = table[i]; e != null; e = e.next) 判斷對(duì)應(yīng)index下是否存在元素；

如果存在，則if(e.hash == hash && ((k = e.key) == key || key.equals(k)))判斷；

如果不存在，則addEntry(hash, key, value, i)直接添加；

簡(jiǎn)單概括如下：

在向HashMap中添加元素時(shí)，先判斷key的hashCode值是否相同，如果相同，則調(diào)用equals()、==進(jìn)行判斷，若相同則覆蓋原有元素；如果不同，則直接向Map中添加元素；

反過(guò)來(lái)，我們?cè)诳聪律厦娴睦樱?/p>

在第一個(gè)Set集合中，我們new了兩個(gè)String對(duì)象，賦了相同的值。當(dāng)傳入到HashMap中時(shí)，key均為“jiaboyan”，所以hash和i的值都相同。進(jìn)行if (e.hash == hash && ((k = e.key) == key || key.equals(k)))判斷，由于String對(duì)象重寫了equals()方法，所以在((k = e.key) == key || key.equals(k))判斷時(shí)，返回了true，所以第二次的插入并不會(huì)增加Set集合的長(zhǎng)度；

第二個(gè)Set集合中，也是new了兩個(gè)對(duì)象，但沒(méi)有重寫equals()方法（底層調(diào)用的Object的equals()，也就是==判斷），所以會(huì)增加2個(gè)元素；

第三個(gè)Set集合中，只new了一個(gè)對(duì)象，調(diào)用的兩次add方法都添加的這個(gè)新new的對(duì)象，所以也只是保留了1個(gè)元素；

1.5 TreeSet

從名字上可以看出，此集合的實(shí)現(xiàn)和樹結(jié)構(gòu)有關(guān)。與HashSet集合類似，TreeSet也是基于Map來(lái)實(shí)現(xiàn)，具體實(shí)現(xiàn)TreeMap(后面講解)，其底層結(jié)構(gòu)為紅黑樹（特殊的二叉查找樹）；

與HashSet不同的是，TreeSet具有排序功能，分為自然排序(123456)和自定義排序兩類，默認(rèn)是自然排序；在程序中，我們可以按照任意順序?qū)⒃夭迦氲郊现?，等到遍歷時(shí)TreeSet會(huì)按照一定順序輸出--倒序或者升序；

它繼承AbstractSet，實(shí)現(xiàn)NavigableSet, Cloneable, Serializable接口。

（1）與HashSet同理，TreeSet繼承AbstractSet類，獲得了Set集合基礎(chǔ)實(shí)現(xiàn)操作；

（2）TreeSet實(shí)現(xiàn)NavigableSet接口，而NavigableSet又?jǐn)U展了SortedSet接口。這兩個(gè)接口主要定義了搜索元素的能力，例如給定某個(gè)元素，查找該集合中比給定元素大于、小于、等于的元素集合，或者比給定元素大于、小于、等于的元素個(gè)數(shù)；簡(jiǎn)單地說(shuō)，實(shí)現(xiàn)NavigableSet接口使得TreeSet具備了元素搜索功能；

（3）TreeSet實(shí)現(xiàn)Cloneable接口，意味著它也可以被克??；

（4）TreeSet實(shí)現(xiàn)了Serializable接口，可以被序列化，可以使用hessian協(xié)議來(lái)傳輸；

具有如下特點(diǎn)：

• 對(duì)插入的元素進(jìn)行排序，是一個(gè)有序的集合（主要與HashSet的區(qū)別）;

• 底層使用紅黑樹結(jié)構(gòu)，而不是哈希表結(jié)構(gòu)；

• 允許插入Null值；

• 不允許插入重復(fù)元素；

• 線程不安全；

1.6 TreeSet基本操作

public class TreeSetTest {
    public static void main(String[] agrs){
        TreeSet<String> treeSet = new TreeSet<String>();
        System.out.println("TreeSet初始化容量大小："+treeSet.size());

        //元素添加：
        treeSet.add("my");
        treeSet.add("name");
        treeSet.add("jiaboyan");
        treeSet.add("hello");
        treeSet.add("world");
        treeSet.add("1");
        treeSet.add("2");
        treeSet.add("3");
        System.out.println("TreeSet容量大?。? + treeSet.size());
        System.out.println("TreeSet元素順序?yàn)椋? + treeSet.toString());

        //增加for循環(huán)遍歷：
        for(String str:treeSet){
            System.out.println("遍歷元素："+str);
        }

        //迭代器遍歷：升序
        Iterator<String> iteratorAesc = treeSet.iterator();
        while(iteratorAesc.hasNext()){
            String str = iteratorAesc.next();
            System.out.println("遍歷元素升序："+str);
        }

        //迭代器遍歷：降序
        Iterator<String> iteratorDesc = treeSet.descendingIterator();
        while(iteratorDesc.hasNext()){
            String str = iteratorDesc.next();
            System.out.println("遍歷元素降序："+str);
        }

        //元素獲取:實(shí)現(xiàn)NavigableSet接口
        String firstEle = treeSet.first();//獲取TreeSet頭節(jié)點(diǎn)：
        System.out.println("TreeSet頭節(jié)點(diǎn)為：" + firstEle);

        // 獲取指定元素之前的所有元素集合：(不包含指定元素)
        SortedSet<String> headSet = treeSet.headSet("jiaboyan");
        System.out.println("jiaboyan節(jié)點(diǎn)之前的元素為："+headSet.toString());

        //獲取給定元素之間的集合：（包含頭，不包含尾）
        SortedSet subSet = treeSet.subSet("1","world");
        System.out.println("1--jiaboan之間節(jié)點(diǎn)元素為："+subSet.toString());

        //集合判斷：
        boolean isEmpty = treeSet.isEmpty();
        System.out.println("TreeSet是否為空："+isEmpty);
        boolean isContain = treeSet.contains("who");
        System.out.println("TreeSet是否包含who元素："+isContain);

        //元素刪除：
        boolean jiaboyanRemove = treeSet.remove("jiaboyan");
        System.out.println("jiaboyan元素是否被刪除"+jiaboyanRemove);

        //集合中不存在的元素，刪除返回false
        boolean whoRemove = treeSet.remove("who");
        System.out.println("who元素是否被刪除"+whoRemove);

       //刪除并返回第一個(gè)元素：如果set集合不存在元素，則返回null
        String pollFirst = treeSet.pollFirst();
        System.out.println("刪除的第一個(gè)元素："+pollFirst);

        //刪除并返回最后一個(gè)元素：如果set集合不存在元素，則返回null
        String pollLast = treeSet.pollLast();
        System.out.println("刪除的最后一個(gè)元素："+pollLast);

        treeSet.clear();//清空集合:
    }
}

1.7 TreeSet元素排序

在前面的章節(jié)，我們講到了TreeSet是一個(gè)有序集合，可以對(duì)集合元素排序，其中分為自然排序和自定義排序，那么這兩種方式如何實(shí)現(xiàn)呢？

首先，我們通過(guò)JDK提供的對(duì)象來(lái)展示，我們使用String、Integer：

public class TreeSetTest {
    public static void main(String[] agrs){
        naturalSort();
    }

    //自然排序順序：升序
    public static void naturalSort(){
        TreeSet<String> treeSetString = new TreeSet<String>();
        treeSetString.add("a");
        treeSetString.add("z");
        treeSetString.add("d");
        treeSetString.add("b");
        System.out.println("字母順序：" + treeSetString.toString());

        TreeSet<Integer> treeSetInteger = new TreeSet<Integer>();
        treeSetInteger.add(1);
        treeSetInteger.add(24);
        treeSetInteger.add(23);
        treeSetInteger.add(6);
        System.out.println(treeSetInteger.toString());
        System.out.println("數(shù)字順序：" + treeSetString.toString());
    }
}

測(cè)試結(jié)果：

字母順序：[a, b, d, z]
數(shù)字順序：[1, 6, 23, 24]

接下來(lái)，我們自定義對(duì)象，看能否實(shí)現(xiàn)：

public class App{

    private String name;

    private Integer age;

    public App(){}

    public App(String name,Integer age){
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Integer getAge() {
        return age;
    }

    public void setAge(Integer age) {
        this.age = age;
    }

    public static void main(String[] args ){
        System.out.println( "Hello World!" );
    }
}

public class TreeSetTest {
    public static void main(String[] agrs){
        customSort();
    }

     //自定義排序順序：升序
    public static void customSort(){
        TreeSet<App> treeSet = new TreeSet<App>();

        //排序?qū)ο螅?        App app1 = new App("hello",10);
        App app2 = new App("world",20);
        App app3 = new App("my",15);
        App app4 = new App("name",25);

        //添加到集合：
        treeSet.add(app1);
        treeSet.add(app2);
        treeSet.add(app3);
        treeSet.add(app4);
        System.out.println("TreeSet集合順序?yàn)椋?+treeSet);
    }
}

測(cè)試結(jié)果：

拋出異常：提示App不能轉(zhuǎn)換為Comparable對(duì)象：
Exception in thread "main" java.lang.ClassCastException: com.jiaboyan.collection.App cannot be cast to java.lang.Comparable

為什么會(huì)報(bào)錯(cuò)呢？

compare(key, key); // type (and possibly null) check

final int compare(Object k1, Object k2) {
    return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
        : comparator.compare((K)k1, (K)k2);
}

通過(guò)查看源碼發(fā)現(xiàn)，在TreeSet調(diào)用add方法時(shí)，會(huì)調(diào)用到底層TreeMap的put方法，在put方法中會(huì)調(diào)用到compare(key, key)方法，進(jìn)行key大小的比較；

在比較的時(shí)候，會(huì)將傳入的key進(jìn)行類型強(qiáng)轉(zhuǎn)，所以當(dāng)我們自定義的App類進(jìn)行比較的時(shí)候，自然就會(huì)拋出異常，因?yàn)锳pp類并沒(méi)有實(shí)現(xiàn)Comparable接口；

將App實(shí)現(xiàn)Comparable接口，在做比較:

public class App implements Comparable<App>{
    private String name;
    private Integer age;
    public App(){}
    public App(String name,Integer age){
        this.name = name;
        this.age = age;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public Integer getAge() {
        return age;
    }
    public void setAge(Integer age) {
        this.age = age;
    }
    //自定義比較：先比較name的長(zhǎng)度，在比較age的大?。?    public int compareTo(App app) {
        //比較name的長(zhǎng)度：
        int num = this.name.length() - app.name.length();
        //如果name長(zhǎng)度一樣，則比較年齡的大小：
        return num == 0 ? this.age - app.age : num;
    }
    @Override
    public String toString() {
        return "App{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

測(cè)試結(jié)果如下：

TreeSet集合順序?yàn)椋篬App{name='my', age=15}, App{name='name', age=25}, App{name='hello', age=10}, App{name='world', age=20}]

此外，還有另一種方式，那就是實(shí)現(xiàn)Comparetor<t>接口，并重寫compare方法；

//自定義App類的比較器：
public class AppComparator implements Comparator<App> {

    //比較方法：先比較年齡，年齡若相同在比較名字長(zhǎng)度；
    public int compare(App app1, App app2) {
        int num = app1.getAge() - app2.getAge();
        return num == 0 ? app1.getName().length() - app2.getName().length() : num;
    }
}

此時(shí)，App不用在實(shí)現(xiàn)Comparerable接口了，單純的定義一個(gè)類即可；

public class App{

    private String name;

    private Integer age;

    public App(){}

    public App(String name,Integer age){
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Integer getAge() {
        return age;
    }

    public void setAge(Integer age) {
        this.age = age;
    }

    public static void main(String[] args ){
        System.out.println( "Hello World!" );
    }
}

public class TreeSetTest {
    public static void main(String[] agrs){
        customSort();
    }

    //自定義比較器：升序
    public static void customComparatorSort(){
        TreeSet<App> treeSet = new TreeSet<App>(new AppComparator());

        //排序?qū)ο螅?        App app1 = new App("hello",10);
        App app2 = new App("world",20);
        App app3 = new App("my",15);
        App app4 = new App("name",25);

        //添加到集合：
        treeSet.add(app1);
        treeSet.add(app2);
        treeSet.add(app3);
        treeSet.add(app4);

        System.out.println("TreeSet集合順序?yàn)椋?+treeSet);
    }
}

測(cè)試結(jié)果：

TreeSet集合順序?yàn)椋篬App{name='hello', age=10}, App{name='my', age=15}, App{name='world', age=20}, App{name='name', age=25}]

最后，在說(shuō)下關(guān)于compareTo()、compare()方法：

結(jié)果返回大于0時(shí)，方法前面的值大于方法中的值；

結(jié)果返回等于0時(shí)，方法前面的值等于方法中的值；

結(jié)果返回小于0時(shí)，方法前面的值小于方法中的值；

集合排序方法

   @Test
    public void testFor() {
        String orderId1 = "2321837281372913";
        String userId1 = "20180701001";
        String orderId2 = "2321837281372914";
        String userId2 = "20180701002";
        String orderId3 = "2321837281372912";
        String userId3 = "20180701003";
        String orderId4 = "2321837281372918";
        String userId4 = "20180701005";
        String orderId5 = "2321837281372918";
        String userId5 = "20180701004";

        Order order = new Order();
        order.setUserId(userId1);
        order.setOrderId(orderId1);
        Order order1 = new Order();
        order1.setOrderId(orderId2);
        order1.setUserId(userId2);

        Order order2 = new Order();
        order2.setOrderId(orderId3);
        order2.setUserId(userId3);
        Order order3 = new Order();
        order3.setOrderId(orderId4);
        order3.setUserId(userId4);
        Order order4 = new Order();
        order4.setOrderId(orderId5);
        order4.setUserId(userId5);
        List<Order> orderList = new ArrayList<Order>();
        orderList.add(order);
        orderList.add(order1);
        orderList.add(order2);
        orderList.add(order3);
        orderList.add(order4);

//1.jdk8 lambda排序，帶參數(shù)類型
//        orderList.sort(( Order ord1, Order ord2) -> ord2.getOrderId().compareTo(ord1.getOrderId()));

//2.jdk8 lambda排序，不帶參數(shù)類型
//        orderList.sort(( ord1, ord2) -> ord2.getOrderId().compareTo(ord1.getOrderId()));

//3.jdk8 升序排序，Comparator提供的靜態(tài)方法
        Collections.sort(orderList, Comparator.comparing(Order::getOrderId));

//4.jdk8 降序排序，Comparator提供的靜態(tài)方法
//        Collections.sort(orderList, Comparator.comparing(Order::getOrderId).reversed());

//5.jdk8 組合排序，Comparator提供的靜態(tài)方法，先按orderId排序，orderId相同的按userId排序
//        Collections.sort(orderList, Comparator.comparing(Order::getOrderId).reversed().thenComparing(Order::getUserId));

        orderList.stream().forEach(str -> System.out.println(str.getOrderId()+"/" + str.getUserId()));
    }

作者：賈博巖
鏈接：http://www.itdecent.cn/p/b48c47a42916
來(lái)源：簡(jiǎn)書