Java Review (二十六、集合----- Set 集合）HashSet 類LinkedHashSet 類TreeSet 類EnumSet 類各 Set 實作類的性能分析

文章目錄

Set 集合，它類似于一個罐子，程式可以依次把多個對象"丢進" Set 集合，而 Set集合通常不能記住元素的添加順序。 Set 集合與 Collection 基本相同，沒有提供任何額外的方法。實際上 Set 就是 Collection ，隻是行為略有不同( Set不允許包含重複元素) 。

散清單（hashtable )是一種可以快速地査找所需要的對象的資料結構，散清單為每個對象計算一個整數，稱為散列碼（hashcode)。散列碼是由對象的執行個體域産生的一個整數。更準确地說，具有不同資料域的對象将産生不同的散列碼。

HashSet是 Set 接口的典型實作，大多數時候使用 Set 集合時就是使用這個實作類。 HashSet 按 Hash算法來存儲集合中的元素，是以具有很好的存取和查找性能。

HashSet 具有以下特點：

不能保證元素的排列順序，順序可能與添加順序不同，順序也有可能發生變化。
HashSet 不是同步的，如果多個線程同時通路一個 HashSet，假設有兩個或者兩個以上線程同時修改了 HashSet 集合時，則必須通過代碼來保證其同步。
集合元素值可以是 null 。

當向 HashSet 集合中存入一個元素時， HashSet 會調用該對象的 hashCode()方法來得到該對象的hashCode 值，然後根據該 hashCode 值決定該對象在 HashSet 中的存儲位置。如果有兩個元素通過 equals()方法比較傳回 true，但它們的 hashCode()方法傳回值不相等， HashSet 将會把它們存儲在不同的位置，

依然可以添加成功。

HashSet 集合判斷兩個元素相等的标準是兩個對象通過 equals()方法比較相等，并且兩個對象的 hashCode()方法傳回值也相等。

下面程式分别提供了三個類 A 、 B 和 C ，它們分别重寫了 equals()、 hashCode()兩個方法的一個或全部，通過此程式可以了解HashSet 判斷集合元素相同的标準：

HashSetTest.java

// 類A的equals方法總是傳回true，但沒有重寫其hashCode()方法
class A
{
    public boolean equals(Object obj)
    {
        return true;
    }
}
// 類B的hashCode()方法總是傳回1，但沒有重寫其equals()方法
class B
{
    public int hashCode()
    {
        return 1;
    }
}
// 類C的hashCode()方法總是傳回2，且重寫其equals()方法總是傳回true
class C
{
    public int hashCode()
    {
        return 2;
    }
    public boolean equals(Object obj)
    {
        return true;
    }
}
public class HashSetTest
{
    public static void main(String[] args)
    {
        HashSet books = new HashSet();
        // 分别向books集合中添加兩個A對象，兩個B對象，兩個C對象
        books.add(new A());
        books.add(new A());
        books.add(new B());
        books.add(new B());
        books.add(new C());
        books.add(new C());
        System.out.println(books);
    }
}

運作結果：

Java Review (二十六、集合----- Set 集合）HashSet 類LinkedHashSet 類TreeSet 類EnumSet 類各 Set 實作類的性能分析

即使兩個 A 對象通過 equals()方法比較傳回 true ，但 HashSet 依然把它們當成兩個對象:即使兩個 B 對象的 hashCode()傳回相同值〈都是1)，但 HashSet 依然把它們當成兩個對象。

當把一個對象放入 HashSet 中時，如果需要重寫該對象對應類的 equalsO方法，則也應該重寫其 hashCode()方法。規則是 :如果兩個對象通過 equals()方法比較傳回 true ，這兩個對象的 hashCode 值也應該相同。

散清單用連結清單數組實作。每個清單被稱為桶（ bucket) (參看圖二) 要想査找表中對象的位置，就要先計算它的散列碼，然後與桶的總數取餘，所得到的結果就是儲存這個元素的桶的索引。

例如，如果某個對象的散列碼為 76268, 并且有 128 個桶，對象應該儲存在第 108 号桶中（76268除以 128餘 108 )。或許會很幸運，在這個桶中沒有

其他元素，此時将元素直接插人到桶中就可以了。

圖二、散清單

有時候會遇到桶被占滿的情況，這也是不可避免的。這種現象被稱為散列沖突（ hash collision) 。這時，需要用新對象與桶中的所有對象進行比較，査看這個對象是否已經存在。如果散列碼是合理且随機分布的，桶的數目也足夠大，需要比較的次數就會很少。

當向 HashSet 中添加可變對象時，必須十分小心。如果修改 HashSet 集合中的對象，有可能導緻該對象與集合中的其他對象相等，進而導緻 HashSet 無法準确通路該對象。

API: java.util.HashSet

HashSet還有一個子類 LinkedHashSet ， LinkedHashSet 集合也是根據元素的 hashCode 值來決定元素的存儲位置，但它同時使用連結清單維護元素的次序，這樣使得元素看起來是以插入的順序儲存的。也就是說，當周遊 LinkedHashSet 集合裡的元素時， LinkedHashSet 将會按元素的添加順序來通路集合裡的元素。

LinkedHashSet 需要維護元素的插入順序，是以性能略低于 HashSet 的性能，但在疊代通路 Set 裡的全部元素時将有很好的性能，因為它以連結清單來維護内部順序。

LinkedHashSetTest.java

public class LinkedHashSetTest
{
    public static void main(String[] args)
    {
        LinkedHashSet books = new LinkedHashSet();
        books.add("瘋狂Java講義");
        books.add("輕量級Java EE企業應用實戰");
        System.out.println(books);
        // 删除 瘋狂Java講義
        books.remove("瘋狂Java講義");
        // 重新添加 瘋狂Java講義
        books.add("瘋狂Java講義");
        System.out.println(books);
    }
}

雖然 LinkedHashSet 使用了連結清單記錄集合元素的添加順序，但 LinkedHashSet 依然是HashSet ，是以它依然不九許集合元素重複。

java.util.LinkedHashSet

TreeSet 是 SortedSet 接口的實作類，正如 SortedSet 名字所暗示的， TreeSet 可以確定集合元素處于排序狀态。與 HashSet 集合相比， TreeSet 還提供了如下幾個額外的方法 :

Comparator comparator(): 如果 TreeSet 采用了定制排序，則該方法傳回定制排序所使用的Comparator; 如果 TreeSet 采用了自然排序，則傳回 null 。
Object ftrst(): 傳回集合中的第一個元素。
Object last(): 傳回集合中的最後一個元素。
Object lower(Object e): 傳回集合中位于指定元素之前的元素( 即小于指定元素的最大元素，參考元素不需要是 TreeSet 集合裡的元素)。
Object higher (Object e): 傳回集合中位于指定元素之後的元素(即大于指定元素的最小元素，參考元素不需要是 TreeSet 集合裡的元素) 。
SortedSet subSet(Object fromElement, Object toElement): 傳回此 Set 的子集合，範圍從 fromElement(包含〉到 toElement (不包含)。
SortedSet headSet(Object toElement): 傳回此 Set 的子集，由小于toElement 的元素組成。
SortedSet tailSet(Object 仕omElement): 傳回此Set 的子集，由大于或等于企omElement 的元素組成。

下面程式測試了 TreeSet 的通用用法:

TreeSetTest.java

public class TreeSetTest
{
    public static void main(String[] args)
    {
        TreeSet nums = new TreeSet();
        // 向TreeSet中添加四個Integer對象
        nums.add(5);
        nums.add(2);
        nums.add(10);
        nums.add(-9);
        // 輸出集合元素，看到集合元素已經處于排序狀态
        System.out.println(nums);
        // 輸出集合裡的第一個元素
        System.out.println(nums.first()); // 輸出-9
        // 輸出集合裡的最後一個元素
        System.out.println(nums.last());  // 輸出10
        // 傳回小于4的子集，不包含4
        System.out.println(nums.headSet(4)); // 輸出[-9, 2]
        // 傳回大于5的子集，如果Set中包含5，子集中還包含5
        System.out.println(nums.tailSet(5)); // 輸出 [5, 10]
        // 傳回大于等于-3，小于4的子集。
        System.out.println(nums.subSet(-3 , 4)); // 輸出[2]
    }
}

與 HashSet 集合采用 hash 算法來決定元素的存儲位置不同， TreeSet 采用紅黑樹的資料結構來存儲集合元素。TreeSet 支援兩種排序方法 : 自然排序和定制排序。在預設情況下， TreeSet 采用自然排序。

要使用樹集，必須能夠比較元素。這些元素必須實作 Comparable 接口，或者構造集時必須提供一個 Comparator 。

TreeSet 會調用集合元素的 compareTo(Object obj)方法來比較元素之間的大小關系，然後将集合元素按升序排列，這種方式就是自然排序。

Java 提供了一個 Comparable 接口，該接口裡定義了一個 compareTo(Object obj )方法，該方法傳回一個整數值，實作該接口的類必須實作該方法，實作了該接口的類的對象就可以比較大小。當一個對象調用該方法與另一個對象進行比較時，例如 obj 1.compareTo(obj2) ，如果該方法傳回 0 ，則表明這兩個對象

相等 :如果該方法傳回一個正整數，則表明 objl 大于 obj2; 如果該方法傳回一個負整數，則表明 objl小于 obj2 。

Java 的一些常用類已經實作了 Comparable 接口，并提供了比較大小的标準。

下面是實作了Comparable 接口的常用類：

BigDecimal 、 BigInteger 以及所有的數值型對應的包裝類 : 按它們對應的數值大小進行比較。
Character: 按字元的 UNICODE 值進行比較。
Boolean: true 對應的包裝類執行個體大于 false 對應的包裝類執行個體。
String: 按字元串中字元的UNICODE 值進行比較。
Date 、 Time: 後面的時間、日期比前面的時間、日期大。

如果試圖把一個對象添加到 TreeSet 時，則該對象的類必須實作 Comparable 接口，否則程式将會抛出異常。如下程式示範了這個錯誤:

TreeSetTestError.java

class Err{}
public class TreeSetErrorTest
{
    public static void main(String[] args)
    {
        TreeSet ts = new TreeSet();
        // 向TreeSet集合中添加Err對象
        // 自然排序時，Err沒實作Comparable接口将會引發錯誤
        ts.add(new Err());
    }
}

向 TreeSet 中添加的應該是同一個類的對象，否則也會引發ClassCastException 異常，因為大部分類在實作 compareTo(Object obj)方法時，都需要将被比較對象 obj 強制類型轉換成相同類型。

如下程式示範了這個錯誤：

TreeSetErrorTest2.java

public class TreeSetErrorTest2
{
    public static void main(String[] args)
    {
        TreeSet ts = new TreeSet();
        // 向TreeSet集合中添加兩個對象
        ts.add(new String("瘋狂Java講義"));
        ts.add(new Date());   // ①
    }
}

當把一個對象加入 TreeSet 集合中時， TreeSet 調用該對象的compareTo(Object obj)方法與容器中的其他對象比較大小，然後根據紅黑樹結構找到它的存儲位置。如果兩個對象通過 compareTo(Object obj)方法比較相等，新對象将無法添加到 TreeSet 集合中。

TreeSetTest2.java

class Z implements Comparable
{
    int age;
    public Z(int age)
    {
        this.age = age;
    }
    // 重寫equals()方法，總是傳回true
    public boolean equals(Object obj)
    {
        return true;
    }
    // 重寫了compareTo(Object obj)方法，總是傳回1
    public int compareTo(Object obj)
    {
        return 1;
    }
}
public class TreeSetTest2
{
    public static void main(String[] args)
    {
        TreeSet set = new TreeSet();
        Z z1 = new Z(6);
        set.add(z1);
        // 第二次添加同一個對象，輸出true，表明添加成功
        System.out.println(set.add(z1));    //①
        // 下面輸出set集合，将看到有兩個元素
        System.out.println(set);
        // 修改set集合的第一個元素的age變量
         ((Z)(set.first())).age = 9;
        // 輸出set集合的最後一個元素的age變量，将看到也變成了9
        System.out.println(((Z)(set.last())).age);
    }
}

程式中①代碼行把同一個對象再次添加到 TreeSet 集合中，因為 zl 對象的

ompareTo(Object obj)方法總是傳回 1，雖然它的 equalsO方法總是傳回 true ，但 TreeSet會認為 z1對象和它自己也不相等，是以TreeSet 可以添加兩個 z1 對象。

TreeSet 及 Z 對象在記憶體中的存儲示意圖

由此應該注意一個問題 : 當需要把一個對象放入 TreeSet中，重寫該對象對應類的 equals()方法時，應保證該方法與 compareTo(Object obj)方法有一緻的結果，其規則是 : 如果兩個對象通過 equals()方法比較傳回 true 時，這兩個對象通過 compareTo(Object obj)方法比較應傳回 0 。

TreeSet 的自然排序是根據集合元素的大小， TreeSet 将它們以升序排列。如果需要實作定制排序，例如以降序排列，則可以通過 Comparator 接口的幫助。該接口裡包含一個 int compare(T 01 , T 02)方法，該方法用于比較 01 和 02 的大小:如果該方法返回正整數，則表明 01 大于 02; 如果該方法傳回 0 ，則表明 01 等于 02; 如果該方法傳回負整數，則表明 01 小于 02 。

如果需要實作定制排序，則需要在建立 TreeSet 集合對象時，提供一個Comparator 對象與該TreeSet集合關聯，由該 Comparator 對象負責集合元素的排序邏輯。由于 Comparator 是一個函數式接口，是以可使用 Lambda 表達式來代替 Comparator 對象。

TreeSetTest4.java

class M
{
    int age;
    public M(int age)
    {
        this.age = age;
    }
    public String toString()
    {
        return "M [age:" + age + "]";
    }
}
public class TreeSetTest4
{
    public static void main(String[] args)
    {
        // 此處Lambda表達式的目标類型是Comparator
        TreeSet ts = new TreeSet((o1 , o2) ->
        {
            M m1 = (M)o1;
            M m2 = (M)o2;
            // 根據M對象的age屬性來決定大小，age越大，M對象反而越小
            return m1.age > m2.age ? -1
                : m1.age < m2.age ? 1 : 0;
        });
        ts.add(new M(5));
        ts.add(new M(-3));
        ts.add(new M(9));
        System.out.println(ts);
    }
}

java.util.TreeSet

EnumSet 是一個專為枚舉類設計的集合類， EnumSet 中的所有元素都必須是指定枚舉類型的枚舉值，該枚舉類型在建立 EnumSet 時顯式或隐式地指定。

EnumSet 的集合元素也是有序的， EnumSet 以枚舉值在 Enum 類内的定義順序來決定集合元素的順序。

EnumSet 在内部以位向量的形式存儲，這種存儲形式非常緊湊、高效，是以 EnumSet 對象占用記憶體很小，而且運作效率很好。尤其是進行批量操作(如調用 containsAll() 和 retainAll()方法〉時，如果其參數也是 EnumSet 集合，則該批量操作的執行速度也非常快。

EnumSet 集合不允許加入 null 元素，如果試圖插入 null 元素， EnumSet 将抛出 NullPointerException異常。如果隻是想判斷 EnumSet 是否包含 null 元素或試圖删除 null 元素都不會抛出異常，隻是删除操作将傳回 false，因為沒有任何 null 元素被删除。

EnumSet 類沒有暴露任何構造器來建立該類的執行個體，程式應該通過它提供的類方法來建立 EnumSet對象。 EnumSet 類它提供了如下常用的類方法來建立 EnumSet 對象 :

EnumSet allOf(Class elementType): 建立一個包含指定枚舉類裡所有枚舉值的 EnumSet 集合。
EnumSet complementOf(EnumSet s): 建立一個其元素類型與指定 EnumSet 裡元素類型相同的

*EnumSet 集合，新 EnumSet 集合包含原 EnumSet 集合所不包含的、此枚舉類剩下的枚舉值(即新EnumSet 集合和原 EnumSet 集合的集合元素加起來就是該枚舉類的所有枚舉值)。
EnumSet copyOf(Collection c): 使用一個普通集合來建立 EnumSet 集合。
EnumSet copyOf(EnumSet s): 建立一個與指定 EnumSet 具有相同元素類型、相同集合元素的EnumSet 集合。
EnumSet noneOf(Class elementType): 建立一個元素類型為指定枚舉類型的空 EnumSet 。
EnumSet of(E first, E… rest): 建立一個包含一個或多個枚舉值的 EnumSet 集合，傳入的多個枚舉值必須屬于同一個枚舉類。
EnumSet range(E from, E to): 建立一個包含從 from 枚舉值到 to 枚舉值範圍内所有枚舉值的EnumSet集合。

下面程式示範了如何使用 EnumSet來儲存枚舉類的多個枚舉值 :

EnumSetTest.java

enum Season
{
    SPRING,SUMMER,FALL,WINTER
}
public class EnumSetTest
{
    public static void main(String[] args)
    {
        // 建立一個EnumSet集合，集合元素就是Season枚舉類的全部枚舉值
        EnumSet es1 = EnumSet.allOf(Season.class);
        System.out.println(es1); // 輸出[SPRING,SUMMER,FALL,WINTER]
        // 建立一個EnumSet空集合，指定其集合元素是Season類的枚舉值。
        EnumSet es2 = EnumSet.noneOf(Season.class);
        System.out.println(es2); // 輸出[]
        // 手動添加兩個元素
        es2.add(Season.WINTER);
        es2.add(Season.SPRING);
        System.out.println(es2); // 輸出[SPRING,WINTER]
        // 以指定枚舉值建立EnumSet集合
        EnumSet es3 = EnumSet.of(Season.SUMMER , Season.WINTER);
        System.out.println(es3); // 輸出[SUMMER,WINTER]
        EnumSet es4 = EnumSet.range(Season.SUMMER , Season.WINTER);
        System.out.println(es4); // 輸出[SUMMER,FALL,WINTER]
        // 新建立的EnumSet集合的元素和es4集合的元素有相同類型，
        // es5的集合元素 + es4集合元素 = Season枚舉類的全部枚舉值
        EnumSet es5 = EnumSet.complementOf(es4);
        System.out.println(es5); // 輸出[SPRING]
    }
}

java.util.EnumSet

HashSet 和 TreeSet 是 Set 的兩個典型實作，到底如何選擇 HashSet 和 TreeSet 呢?

HashSet 的性能總是比 TreeSet 好(特别是最常用的添加、查詢元素等操作) ，因為 TreeSet 需要額外的紅黑樹算法來維護集合元素的次序。隻有當需要一個保持排序的 Set 時，才應該使用 TreeSet，否則都應該使用 HashSet 。

HashSet 還有一個子類 : LinkedHashSet ，對于普通的插入、删除操作， LinkedHashSet 比 HashSet要略微慢一點，這是由維護連結清單所帶來的額外開銷造成的，但由于有了連結清單，周遊 LinkedHashSet 會更快。

EnumSet 是所有 Set 實作類中性能最好的，但它隻能儲存同一個枚舉類的枚舉值作為集合元素。

必須指出的是， Set 的三個實作類 HashSet 、 TreeSet 和 EnumSet 都是線程不安全的。如果有多個線程同時通路一個 Set 集合，并且有超過一個線程修改了該 Set 集合，則必須手動保證該Set 集合的同步性。通常可以通過 Collections 工具類的 syncbronizedSortedSet 方法來 "包裝"該 Set 集合。此操作最

好在建立時進行，以防止對 Set 集合的意外非同步通路。

SortedSet s = Collections.synchronizedSortedSet(new TreeSet(.. .));

Java Review系列目錄 ⇐⇐Java Review (二十五、集合----- Iterator接口） Java Review (二十七、集合----- List 集合）⇒⇒

參考：

【1】：《瘋狂Java講義》

【2】：《Java核心技術卷一》

【3】：

廖雪峰的官方網站：使用Set

Java Review (二十六、集合----- Set 集合）HashSet 類LinkedHashSet 類TreeSet 類EnumSet 類各 Set 實作類的性能分析

文章目錄

繼續閱讀

資料結構與算法（27）——排序（二）

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method

hdu7108哈希