java集合（10）——HashSet、LinkedHashSet和TreeSet辨析

Set接口

是Collection的子接口，Set要點：

不允許包含相同的元素
使用equals方法判斷對象是否相同
一個不包含重複元素的 collection。更确切地講，set 不包含滿足 e1.equals(e2) 的元素對 e1 和 e2，并且最多包含一個 null 元素

HashSet類

該類實作的接口：Serializable, Cloneable, Iterable, Collection, Set

HashSet原理

HashSet是基于HashMap來實作的，操作很簡單，更像是對HashMap做了一次“封裝”，而且隻使用了HashMap的key來實作各種特性
HashSet是通過HashMap實作，整個HashSet的核心就是HashMap。HashMap中的鍵作為HashSet中的值，HashMap中的值通過建立一個假的value來實作。
下面是HashSet的部分源碼

private transient HashMap<E,Object> map;

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

/**
 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
 * default initial capacity (16) and load factor (0.75).
 * 首先有一個HashMap成員變量，我們在HashSet的構造函數中将其初始化，預設情況下用的是Initial capacity為16，load factory加載因子為0.75
 */
public HashSet() {
    map = new HashMap<>();
}


public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}
public boolean contains(Object o) {
    return map.containsKey(o);
}
public int size() {
    return map.size();
}

HashSet中的一些基本操作都是調用HashMap來實作的。

HashSet注意事項

HashSet不同步，如果需要使用多線程通路，可以使用 Collections.synchronizedSet() 方法包裝 Set s = Collections.synchronizedSet(new HashSet());
HashSet類判斷兩個元素是否相等，需要兩個條件，第一個條件： equals() 的結果為true，第二個條件： hashCode（） 的值相等，即對應的元素的hashCode碼要相同。
HashSet類：向該類中添加元素，排列的順序不确定，是以隻有不關心集合中元素的順序時才應該是會用HashSet類來存儲元素。
集合HashSet類中元素的值可以是null

下面的例子來自：https://www.bysocket.com/?p=195

package set;

import java.util.HashSet;
import java.util.Set;

public class HashSetTest {

    public static void main(String[] agrs){
        Set s = new HashSet();
        s.add(new EqualsObj());
        s.add(new EqualsObj());
        s.add(new HashCodeObj());
        s.add(new HashCodeObj());
        s.add(new HashSetObj());
        s.add(new HashSetObj());

        System.out.println("HashSet Elements:");
        System.out.print("\t" + s + "\n");
    }
}

class EqualsObj {

    public boolean equals(Object obj) {
        return true;
    }
}

class HashCodeObj {
    public int hashCode() {
        return ;
    }
}

class HashSetObj {
    public boolean equals(Object obj) {
        return true;
    }

    public int hashCode() {
        return ;
    }
}

在控制台輸出的結果如下：

HashSet Elements:
    [set.EqualsObj@7852e922, set.HashCodeObj@1, set.HashCodeObj@1, set.HashSetObj@2, set.EqualsObj@6d06d69c]

從輸出結果可以看出，1.HashSet類存儲資料的順序是不确定的，2. 該類隻認為hashCode和equals方法的值都不同的對象為不同的對象

當我們使用HashSet集合時，需要注意：将對象存儲在HashSet之前，要確定對象重寫了 equals() 和 hashCode() 方法，即如果要把一個對象放在HashSet中，如果重寫了該對象的 equals（） 方法，也要重寫該對象的 hashCode() 方法，修改的規則是：如果兩個對象通過equals方法比較傳回true時，這兩個對象的hashCode一定也要相同

HashSet集合的優點：

它可以通過一個對象快速查找到集合中的對象。hash算法的價值在于查找速度很快：它是通過将對象轉變為對應的hashCode值，然後按照hashCode值在桶中對應位置取出該元素。

下面的程式來自：http://blog.csdn.net/shb_derek1/article/details/8729605

package set;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class HashSetTest2 {
    public static void main(String[] args) {
        Set sets = new HashSet();
        sets.add(new HashSet2());
        sets.add(new HashSet2(-));
        sets.add(new HashSet2());
        sets.add(new HashSet2());
        sets.add(new HashSet2(-));

        //HashSet是無序集合，是以列印的結果是無序的
        System.out.println(sets);

        Iterator i = sets.iterator();
        //取出集合中第一個元素元素
        HashSet2 hs = (HashSet2) i.next();
        //将取出的元素賦新值，賦的值與集合中原有的元素之相同

        hs.count = ;
        //集合中有兩個元素一樣
        System.out.println(sets);

        //從集合中移出值
        sets.remove(new HashSet2());

        System.out.println(sets);
        //集合中不包含21，因為按照hashCode值找到的槽内沒有該值。
        System.out.println("sets.contains(new HashSets(21)："+sets.contains(new HashSet2()));
    }
}

class HashSet2 {
    int count;

    public HashSet2(int count) {
        super();
        this.count = count;
    }

    public String toString() {
        return "HashSet2 [count=" + count + "]" ;
    }

    public boolean equals(Object obj) {
        if(obj instanceof HashSet2){
            HashSet2 hs = (HashSet2) obj;
            if(this.count == hs.count)
                return true;
            return false;
        }
        return false;
    }

    public int hashCode() {
        return this.count;
    }
}

運作結果：

[HashSet2 [count=-], HashSet2 [count=], HashSet2 [count=], HashSet2 [count=-], HashSet2 [count=]]
[HashSet2 [count=], HashSet2 [count=], HashSet2 [count=], HashSet2 [count=-], HashSet2 [count=]]
[HashSet2 [count=], HashSet2 [count=], HashSet2 [count=-], HashSet2 [count=]]
sets.contains(new HashSets()：false

LinkedHashSet類

該類實作的接口：Serializable, Cloneable, Iterable, Collection, Set

該類是一種可以記住元素插入次序的類，即輸出順序與插入順序一緻
它是HashSet類的子類，是以也是通過HashCode的值來決定元素的位置

package set;

import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Set;

public class LinkedHashSet1 {
    public static void main(String[] args) {
        Set s = new LinkedHashSet();
        s.add(new String("e"));
        s.add(new String("b"));
        s.add(new String("a"));
        s.add(new String("c"));

        System.out.println(s);
    }
}

上述程式運作結果：

[e, b, a, c]

TreeSet類

該類實作的接口：Serializable, Cloneable, Iterable, Collection, NavigableSet, Set, SortedSet

TreeSe使用紅黑樹的結構實作，集合中的元素進行排序，添加、删除等算法的複雜度為O(log(n))
使用該集合的類必須實作Comparable接口中的 compare To() 方法，因為該類是有序的
該類是通過元素的值進行排序的，而不是通過插入元素的順序進行排序的

如下面代碼：

package set;

import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

public class TreeSetTest {
    public static void main(String[] args) {
        TreeSet nums = new TreeSet(); 
        nums.add(new Bird());
        nums.add(new Bird());
        nums.add(new Bird());
        nums.add(new Bird());

        System.out.println(nums);
    }
}

class Bird {
    int size;

    public Bird(int size) {
        super();
        this.size = size;
    }

    public String toString() {
        return "Bird [size=" + size + "]";
    }

}

運作後，編譯器報錯：

Exception in thread "main" java.lang.ClassCastException: set.Bird cannot be cast to java.lang.Comparable
    at java.util.TreeMap.put(TreeMap.java:)
    at java.util.TreeSet.add(TreeSet.java:)
    at set.TreeSetTest.main(TreeSetTest.java:)

因為TreeSet是實作SortedSet接口的類，是以他有排序功能，對應的傳遞進來的對象也要有需要可比較。先修改上述代碼如下：

package set;

import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

public class TreeSetTest {
    public static void main(String[] args) {
        TreeSet nums = new TreeSet(); 
        nums.add(new Bird());
        nums.add(new Bird());
        nums.add(new Bird());
        nums.add(new Bird());

        System.out.println(nums);
    }
}

class Bird implements Comparable<Bird>{
    int size;

    public Bird(int size) {
        super();
        this.size = size;
    }

    public String toString() {
        return "Bird [size=" + size + "]";
    }

    public int compareTo(Bird o) {
        // TODO Auto-generated method stub
        return this.size - o.size;
    }
}

程式運作結果：

[Bird [size=], Bird [size=], Bird [size=], Bird [size=]]

java集合（10）——HashSet、LinkedHashSet和TreeSet辨析

Set接口

HashSet類

HashSet原理

HashSet注意事項

LinkedHashSet類

TreeSet類

繼續閱讀

【Java】集合系列07（Stack詳細介紹源碼解析和使用示例）

java集合系列——Map介紹（七）

【Java】集合系列12(TreeMap詳細介紹源碼解析和使用示例)

java中集合和泛型（基礎）

java集合報錯：java.lang.UnsupportedOperationException

Collection接口和疊代器

ArrayList 集合中怎麼插入元素的

Java基礎——CopyOnWriteArrayList源碼分析

Java集合 | CopyOnWriteArrayList源碼分析(JDK 1.7)

java集合之CopyOnWriteArrayList

黑馬程式員_日記43_初學TreeSet

《黑馬程式員》 TreeSet集合練習之按照字元串長度排序

HashSet中的元素比較詳解

Java集合在JDK1.7和JDK1.8中的不同——JDK1.7和JDK1.8中集合的對比研究——java集合深入了解1、ArrayList

HashSet集合解讀

基于jdk1.8的Vector源碼分析