文章目錄

Set接口及其實作類
- 1. Set接口介紹
- 2. Set接口的主要實作類
- - 2.1 HashSet集合☆
  - - - 哈希值和哈希表
      - HashSet中添加元素的過程
      - 重寫 hashCode() 方法的基本原則
      - 重寫 equals() 方法的基本原則
      - HashSet存儲自定義類型元素☆
      - LinkedHashSet集合☆
  - 2.2 TreeSet集合
  - - - 排序—自然排序
      - 排序—定制排序
☆

Set接口及其實作類

1. Set接口介紹

java.util.Set 接口和 java.util.List 接口一樣，同樣繼承自 Collection 接口，它與 Collection 接口中的方法基本一緻，并沒有對 Collection 接口進行功能上的擴充，隻是比 Collection 接口更加嚴格了。

與 List 接口不同的是， Set 接口中元素無序，并且都會以某種規則保證存入的元素不出現重複。

Set 判斷兩個對象是否相同不是使用 == 運算符，而是根據 equals() 方法。

Set集合取出元素的方式可以采用：疊代器、增強for。

Set 集合有多個子類，這裡我們介紹其中的 java.util.HashSet 、 java.util.LinkedHashSet 、 java.util.TreeSet 這三個集合。

6. Set接口及其實作類Set接口及其實作類☆

2. Set接口的主要實作類

2.1 HashSet集合☆

java.util.HashSet 是 Set 接口的一個典型實作類，它所存儲的 元素是不可重複 的， 集合元素可以為null ， 線程不安全 ，并且元素都是 無序的 (即存取順序不能保證不一緻)。

HashSet 是根據對象的哈希值來确定元素在集合中的存儲位置，是以具有良好的存儲和查找性能。保證元素唯一性的方式依賴于： hashCode 與 equals 方法。即兩個對象通過 hashCode() 方法比較相等，并且兩個對象的 equals() 方法傳回值也相等。

對于存放在Set容器中的對象， 對應的類一定要重寫equals() 和hashCode(Object obj) 方法 ，以實作對象相等規則。即： “相等的對象必須具有相等的散列碼” 。

java.util.HashSet 底層的實作其實是一個 java.util.HashMap 支援。

哈希值和哈希表

哈希值簡介：是JDK根據 對象的位址 或者 字元串 或者 數字 算出來的 int類型的數值 。

如何擷取哈希值： Object類中的public int hashCode()；傳回對象的哈希碼值。

哈希值的特點：

同一個對象多次調用hashCode()方法傳回的哈希值是相同的。

預設情況下，不同對象的哈希值是不同的。而重寫hashCode()方法，可以實作讓不同對象的哈希值相同。

什麼是哈希表呢？哈希表是HashSet集合存儲資料的結構

在 JDK1.8 之前，哈希表底層采用 數組+連結清單 實作，即使用連結清單處理沖突，同一 hash 值的連結清單都存儲在一個連結清單裡。但是當位于一個桶中的元素較多，即 hash 值相等的元素較多時，通過 key 值依次查找的效率較低。

6. Set接口及其實作類Set接口及其實作類☆

而 JDK1.8 中，哈希表存儲 采用數組+連結清單+紅黑樹 實作，當連結清單長度超過門檻值（8）時，将連結清單轉換為紅黑樹，這樣大大減少了查找時間。

6. Set接口及其實作類Set接口及其實作類☆

底層也是數組，初始容量為16，當如果使用率超過0.75，（16*0.75=12）就會擴大容量為原來的2倍。 （16擴容為32，依次為64,128…等）。

簡單的來說，哈希表是由數組+連結清單+紅黑樹（ JDK1.8 增加了紅黑樹部分）實作的，如下圖所示：

6. Set接口及其實作類Set接口及其實作類☆

HashSet中添加元素的過程

當向 HashSet 集合中存入一個元素時，HashSet 會調用該對象的 hashCode() 方法來得到該對象hashCode 值，然後根據 hashCode 值，通過某種散列函數決定該對象在 HashSet 底層數組中的存儲位置。（ 這個散列函數會與底層數組的長度相計算得到在數組中的下标，并且這種散列函數計算還盡可能保證能均勻存儲元素，越是散列分布，該散列函數設計的越好 ）

如果兩個元素的hashCode()值相等，會再繼續調用equals方法，如果equals方法結果為true，添加失敗；如果為false，那麼會儲存該元素，但是該數組的位置已經有元素了，那麼會通過 連結清單的方式 繼續連結。

重寫 hashCode() 方法的基本原則

在程式運作時，同一個對象多次調用 hashCode() 方法應該傳回相同的值。

當兩個對象的 equals() 方法比較傳回 true 時，這兩個對象的 hashCode()方法的傳回值也應相等。

對象中用作 equals() 方法比較的 Field，都應該用來計算 hashCode 值。

重寫 equals() 方法的基本原則

以自定義的Student類為例，何時需要重寫equals()？

當一個類有自己特有的“邏輯相等”概念, 當改寫equals()的時候，總是要改寫hashCode()，根據一個類的equals方法（改寫後），兩個截然不同的執行個體有可能在邏輯上是相等的，但是，根據Object.hashCode()方法，它們僅僅是兩個對象。

是以，違反了 “相等的對象必須具有相等的散列碼” 。

結論：複寫equals方法的時候一般都需要同時複寫hashCode方法。 通常參與計算hashCode 的對象的屬性也應該參與到equals()。

HashSet存儲自定義類型元素☆

給 HashSet 中存放自定義類型元素時，需要重寫對象中的 hashCode 和 equals 方法，建立自己的比較方式，才能保證HashSet集合中的對象唯一。

/**
*建立自定義Student類
*/
public class Student {
    private String name;
    private int age;
    public Student() {
    }
    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o)
            return true;
        if (o == null || getClass() != o.getClass())
            return false;
        Student student = (Student) o;
        return age == student.age &&
            Objects.equals(name, student.name);
    }
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

public class HashSetDemo {
    public static void main(String[] args) {
        
        //建立集合對象 該集合中存儲 Student類型對象
        HashSet<Student> stuSet = new HashSet<Student>();
        //存儲
        Student stu = new Student("于謙", 43);
        stuSet.add(stu);
        stuSet.add(new Student("郭德綱", 44));
        stuSet.add(new Student("于謙", 43));
        stuSet.add(new Student("郭麒麟", 23));
        stuSet.add(stu);
        for (Student stu2 : stuSet) {
            System.out.println(stu2);
        }
    }
}

執行結果：

Student [name=郭德綱, age=44]

Student [name=于謙, age=43]

Student [name=郭麒麟, age=23]

Objects.hash(name, age);執行細節如下：

public static int hash(Object... values) {
        return Arrays.hashCode(values);
    }
        
    public static int hashCode(Object a[]) {
        if (a == null)
            return 0;

        int result = 1;

        for (Object element : a)
            result = 31 * result + (element == null ? 0 : element.hashCode());

        return result;
    }

LinkedHashSet集合☆

我們知道 HashSet 保證元素唯一，可是元素存放進去是沒有順序的，那麼我們要保證有序，怎麼辦呢？在 HashSet 下面有一個子類 java.util.LinkedHashSet ，它是連結清單和哈希表組合的一個資料存儲結構。

LinkedHashSet 是 HashSet 的子類。

LinkedHashSet 根據元素的 hashCode 值來決定元素的存儲位置，但它同時使用雙向連結清單維護元素的次序，這使得元素看起來是 以插入順序儲存的 。

LinkedHashSet插入性能略低于 HashSet，但在疊代通路 Set 裡的全部元素時有很好的性能。

LinkedHashSet 不允許集合元素重複。

2.2 TreeSet集合

TreeSet 是 SortedSet 接口的實作類 ，TreeSet 可以確定集合元素處于排序狀态。

TreeSet底層使用紅黑樹結構存儲資料。

可以将元素按照規則進行排序。

TreeSet()：根據其元素的 自然排序進行排序。

TreeSet(Comparator comparator) ：根據指定的 比較器進行排序。

特點：

有序，查詢速度比List快。

排序—自然排序

自然排序：TreeSet 會調用集合元素的 compareTo(Object obj) 方法來比較元素之間的大小關系，然後将集合元素 按升序(預設情況)排列 。

如果試圖把一個對象添加到 TreeSet 時，則該對象的類必須實作 Comparable接口。

實作 Comparable 的類必須實作 compareTo(Object obj) 方法，兩個對象即通過compareTo(Object obj) 方法的傳回值來比較大小。

Comparable 的典型實作：

BigDecimal、BigInteger 以及所有的數值型對應的包裝類：按它們對應的數值大小進行比較。

Character： 按字元的 unicode值來進行比較。

Boolean：true 對應的包裝類執行個體大于 false 對應的包裝類執行個體。

String： 按字元串中字元的 unicode 值進行比較。

Date、Time： 後邊的時間、日期比前面的時間、日期大。

向 TreeSet 中添加元素時，隻有第一個元素無須比較compareTo()方法，後面添加的所有元素都會調用compareTo()方法進行比較。

因為隻有相同類的兩個執行個體才會比較大小，是以向 TreeSet 中添加的應該是同一個類的對象。

對于 TreeSet 集合而言，它判斷兩個對象是否相等的唯一标準是：兩個對象通過 compareTo(Object obj) 方法比較傳回值。

當需要把一個對象放入 TreeSet 中，重寫該對象對應的 equals() 方法時，應保證該方法與 compareTo(Object obj) 方法有一緻的結果：如果兩個對象通過equals() 方法比較傳回 true，則通過 compareTo(Object obj) 方法比較應傳回 0。否則，讓人難以了解。

排序—定制排序

TreeSet的自然排序要求元素所屬的類實作Comparable接口，如果元素所屬的類沒有實作Comparable接口，或不希望按照升序(預設情況)的方式排列元素或希望按照其它屬性大小進行排序，則考慮使用定制排序。

定制排序，通過Comparator接口來實作。需要重寫compare(T o1,T o2)方法。

利用 int compare(T o1,T o2) 方法，比較 o1 和 o2 的大小：

如果方法傳回正整數，則表示o1大于o2；

如果傳回0，表示相等；

傳回負整數，表示o1小于o2。

要實作定制排序，需要将實作Comparator接口的執行個體作為形參傳遞給TreeSet的構造器。

此時，仍然隻能向TreeSet中添加類型相同的對象，否則發生ClassCastException異常。

使用定制排序判斷兩個元素相等的标準是：通過Comparator比較 兩個元素傳回了0。

6. Set接口及其實作類Set接口及其實作類☆

文章目錄

Set接口及其實作類

1. Set接口介紹

2. Set接口的主要實作類

2.1 HashSet集合☆

哈希值和哈希表

HashSet中添加元素的過程

重寫 hashCode() 方法的基本原則

重寫 equals() 方法的基本原則

HashSet存儲自定義類型元素☆

LinkedHashSet集合☆

2.2 TreeSet集合

排序—自然排序

排序—定制排序

☆

繼續閱讀

LinkedHashSet集合LinkedHashSet集合

[Java基礎]LinkedHashSet集合概述和特點

Java中HashSet、LinkedHashSet和TreeSet的使用

後端---Java中的HashSet和TreeSet和LinkedHashSet的差別Java中的HashSet和TreeSet和LinkedHashSet差別

LinkedHashSet源碼閱讀回顧

C# HashSet類常用函數 C# HashSet類常用函數

集合架構（三） Set&HashSet

淺析Java集合類源碼（二）--- HashSet, HashMap, Hashtable

Java中的HashSet

java--HashSet詳解

Java HashSet（基礎詳解）一、什麼是HashSet二、HashSet的架構圖三、代碼案例示範：

Java集合 HashSet 和 TreeSet的了解

HashSet 詳解

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

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

HashSet中的元素比較詳解