Set集合保證元素不重複的原理&Java中的排序接口
- 1. Set體系集合的繼承關系和特點
- 2. HashSet如何保證元素的唯一性
- - 2.1 HashSet集合的簡介和HashSet#add()方法
  - 2.2 重寫hashCode()方法的原則
  - 2.3 重寫equals()方法的原則
- 3. TreeSet與排序
- - 3.1 TreeSet集合的簡介和TreeSet#add()方法
  - 3.2 自然排序
  - 3.3 比較器排序
  - 3.4 小結

Set集合保證元素不重複的原理&Java中的排序接口

閱讀本文您可以了解到以下内容：
- 常用集合的繼承體系&常用Set體系集合的特點；
- Set體系集合保證元素唯一性的原因；
- 重寫hashCode()方法的原因和原則；重寫equals()方法的原因和原則；
- TreeSet集合如何對元素進行排序；
- 自然排序，比較器排序，Comparable接口，Comparator接口；

1. Set體系集合的繼承關系和特點

Set集合保證元素不重複的原理&TreeSet集合與排序Set集合保證元素不重複的原理&Java中的排序接口

Set體系常用集合的特點
- HashSet 的特點：無序、不可重複；
  - LinkedHashSet 的特點：有序、不可重複；
- TreeSet 的特點：能夠使元素按照某種規則排序、不可重複；
Set體系常用集合的資料結構
- HashSet 的底層資料結構：哈希表。增删改都快，哈希表能保證元素的唯一性。
  - LinkedHashSet 的底層資料結構：哈希表+連結清單。哈希表保證元素唯一，連結清單保證元素有序。
- TreeSet 的底層資料結構：紅黑樹。該資料結構能保證元素的唯一和排序。

2. HashSet如何保證元素的唯一性

2.1 HashSet集合的簡介和HashSet#add()方法

HashSet特點
- 元素的存入順序和取出順序不同
- 不能存儲重複元素
  - 多次調用add()方法添加同樣的資料, 除第一次外都會添加失敗。
    
    是以保證元素唯一性的源碼肯定在HashSet#add()方法中。
  - HashSet底層資料結構是哈希表, 哈希表能保證元素的唯一性。
HashSet#add()方法的源碼的簡要分析

//添加相同元素會失敗，展現出儲存元素唯一性，應該看HashSet#add()方法源碼了解為何添加相同元素将失敗
interface Collection {
    //...
}

interface Set extends Collection {
    //...
}

class HashSet implements Set {
    private static final Object PRESENT = new Object();
    private transient HashMap<E, Object> map;

    //由HashSet集合的構造可知，HashSet的底層是HashMap
    public HashSet() {
        map = new HashMap<>();
    }

    public boolean add(E e) {
        //可見HashSet#add()方法底層調用了HashMap#put()方法，參數傳入了一個E和一個Object類型的靜态常量PRESENT
        return map.put(e, PRESENT) == null;
    }
}

class HashMap implements Map {
    public V put(K key, V value) {
        hashCode();
        equals();
    }
}
/*
小結：
HashSet的底層是HashMap，HashSet調用add()方法實際上底層是調用HashMap的put()方法。
put()方法的底層依賴hashCode()方法和equals()方法來保證添加元素的唯一性。

Object#hashCode()：傳回對象的哈希碼值，對象的位址值經過計算得到的值。

Java泛型中的E，就是Element的意思，一般代表放入集合中的元素。
*/

HashSet#add()方法保證添加元素唯一性的細節
1. 用add()方法欲添加一個元素，先用hashCode()方法算出該元素的哈希值，和哈希表中的哈希值進行比較。
2. 如果哈希表中無此哈希值，那麼說明該元素沒被添加過，就添加這個元素。
3. 如果哈希表中有該哈希值，那麼比較欲添加元素和同哈希值元素的位址值并使用equals()方法比較欲添加元素和同哈希值元素的内容是否相同。如果位址值或equals()其中之一不同，就添加這個元素。
小結
- 使用HashSet#add()方法添加元素，先比較哈希值，哈希值不同，添加該元素；哈希值相同，比較位址值或equals()，其中之一不同就添加該元素。
輔助記憶上述内容
- 哈希表就是字典，哈希值就是頁碼，欲添加的元素就是字典上的字。
  
  字的頁碼是根據字和頁碼算法計算出來的（元素的哈希值是根據元素的位址值和雜湊演算法計算出來的）。
- 如果一個字(元素)的頁碼(哈希值)在字典(哈希表)中找不到，說明這個字(元素)沒有被添加過，那麼就添加這個元素。
- 如果一個字(元素)的頁碼(哈希值)能在字典(哈希表)中找到，但是該頁碼(哈希值)下有很多字(元素) (對應不同java對象可能有相同的hashCode)，如果該字(元素)和該頁碼(哈希值)下所有字(元素)的位置(位址值)和筆畫順序(内容)其中之一不同, 說明這個字(元素)沒被添加過, 那麼就添加這個元素。
綜上所屬，如果想讓HashSet#add()保證添加元素的唯一性, 必須重寫集合中元素對應類的hashCode()和equals()。

2.2 重寫hashCode()方法的原則

hashCode()方法是Object類中的方法。

該方法的作用是：傳回對象的哈希碼值。

該方法的源碼是：public native int hashCode();

native 關鍵字代表該方法底層是用c/c++實作的。
重寫該方法的原則：使成員變量值相同的對象的哈希值相同。
重寫該方法的細節
- 将對象的成員變量值相加得出一個值A即可, 如此一來, 值A相同的對象就是成員變量值相同的對象, 就視為相同的對象;
- 如果成員變量是引用類型, 就加哈希值; 如果成員變量是基本類型, 就加變量值;
重寫該方法的示例

// String name;       int age;

@Override
public int hashCode() {
    return this.name.hashCode() + this.age * 任意數字;
}

/*
 * 為什麼要乘以任意數字呢 ? 
 * A對象：name.hashCode()=40, age=30.    40+30=70;
 * B對象：name.hashCode()=50, age=20.    50+20=70;
 * 若出現以上情況，盡管成員變量值都不同，但是最後相加後結果都是相同的，
 * 是以我們将其中一個成員變量值做算數運算，保證了最後相加值的唯一性。
*/

注意
- 如果換一個重寫hashCode()的方式，比如将hashCode()重寫為永遠傳回一個固定的數值的方法(例如将hashCode()的方法體重寫為“return 1;”)也能實作Set體系集合的唯一性。
  
  因為比較完哈希值是否相同，還會再用equals()比較，當equals()傳回false時才添加元素，但是這樣做欲添加的第1000個元素需要和以前添加的999個元素做hashCode()比較和equals()比較才能判斷是否有相同元素, 效率低。是以我們想直接比較哈希值，哈希值不同就添加，相同就不添加，這就需要不同元素哈希值不同, 相同元素哈希值相同, 是以我們選擇成員變量相加的方式重寫hashCode().。
  
  HashSet集合的底層是哈希表結構，哈希表就靠hashCode()和equals()實作元素的唯一性。

2.3 重寫equals()方法的原則

equals()方法是Object類中的方法。

該方法的作用是：判斷兩個變量是否相同。

Object類中的equals()方法是用"=="實作的。
equals()和==的差別
- ==比較基本資料類型變量，比較的是棧中該變量的值是否相同。
- ==比較引用資料類型變量，比較的是棧中該對象的引用變量是否相同，即比較的是兩個對象的位址值是否相同。
- equals()不能比較基本資料類型。因為equals()是Object類中的方法，基本資料類型不能調用方法。
- equals()比較引用資料類型，比較的是對象的内容是否相同。
- 由于equals()是Object類中的方法，該方法底層是用“==”比較的。是以我們一般需要重寫該方法。有些類已經幫我們重寫了該方法，例如String類。
重寫equals()方法的原則：隻要對象的所有屬性值都不同，就視為不同對象。是以重寫equals()隻要寫一個比較兩對象所有屬性值是否相同的方法即可。
我們隻需要知道為什麼要重寫hashCode()方法和equals()方法，不需要手動重寫這兩個方法。

使用IDE工具的快捷鍵能快速重寫這兩個方法，并且重寫的方法的邏輯比我們的缜密。

3. TreeSet與排序

3.1 TreeSet集合的簡介和TreeSet#add()方法

TreeSet集合的特點
- 不能添加重複元素
- 能夠對元素按照某種規則排序
  - 排序方式有兩種，具體用哪一種方式取決于建立TreeSet時使用哪個構造方法。
    1. 自然排序：需要使用TreeSet的無參構造。
    2. 比較器排序(通過建立set時提供的Comparator接口進行排序) ：需要使用TreeSet的有參構造。
TreeSet是如何保證唯一并對元素排序的
- 因為TreeSet資料結構是二叉樹，是以元素能排序并唯一。即底層結構是紅黑樹，此資料結構能保證元素的唯一性和排序。類似分析HashSet，我們也要分析TreeSet的add()方法。
  
  通過觀察TreeSet的add()，我們知道最終要看TreeMap的put()。TreeSet底層是TreeMap()。TreeSet的add()的底層是TressMap的put()。
TreeSet集合的資料結構

Set集合保證元素不重複的原理&TreeSet集合與排序Set集合保證元素不重複的原理&Java中的排序接口

3.2 自然排序

概述
- 用TreeSet無參構造建立對象時才能用此排序方式。
  
  集合中元素對應的類A必須實作Comparable<T>接口(自然排序接口)，在類A中必須重寫int compareTo(T o)方法，方法的内容就寫排序的規則。要充分考慮排序的主要條件和次要條件。
TreeSet集合使用自然排序步驟
1. 使用無參構造建立TreeSet集合的對象
2. 把要傳入集合的元素對應的類實作Comparable<T>接口，泛型填傳入集合的元素類型
3. 在要傳入集合的元素對應的類中實作Comparable<T>接口的int compareTo(T o)方法
4. 方法内容就是比較的規則，要全面考慮主要規則和次要規則。
自然排序示例01

package cn.king.demo01;

import org.junit.Test;
import java.util.TreeSet;

class User implements Comparable<User> {
    private String name;
    private int age;
    
    @Override
    public int compareTo(User o) {
        /*
         * 傳回什麼, 要根據我們的排序規則來決定;
         * 按照年齡排序-->主要條件;
         * 按照年齡排序是主要條件，需分析出次要條件;
         * 年齡相同時，判斷姓名是否相同-->次要條件;
         * 如果年齡和姓名都不相同時，才是同一個元素;
         */

        //比較年齡大小--主要條件
        int num = this.age - o.age;
        //如果年齡相同，就比較姓名，否則還是比較年齡--次要條件
        int num2 = num == 0 ? this.name.compareTo(o.name) : num;
        return num2;
    }
    
    // getter...   setter...  toString...  全參構造...   無參構造...
    
}

/**
 * 排序方式：自然排序--按照年齡從小到大排序
 * 排序規則：
 * 注意：如果類A中的對象要進行自然排序，類必須實作自然排序接口;并在類A中實作compareTo()方法。
 */
public class Demo01 {
    @Test
    public void test01() {
        TreeSet<User> users = new TreeSet<>();
        User user01 = new User("張三", 20);
        User user02 = new User("張三", 30);
        User user03 = new User("王五", 4);
        User user04 = new User("李四", 50);
        User user05 = new User("張三", 20);
        User user06 = new User("趙六", 20);
        users.add(user01);
        users.add(user02);
        users.add(user03);
        users.add(user04);
        users.add(user05);
        users.add(user06);

        users.forEach(System.out::println);

        /*  輸出:
            User{name='王五', age=4}
            User{name='張三', age=20}
            User{name='趙六', age=20}
            User{name='張三', age=30}
            User{name='李四', age=50}
         */
    }
}

自然排序示例02

package cn.king.demo01;

import org.junit.Test;
import java.util.TreeSet;

class User implements Comparable<User> {
    private String name;
    private int age;

    @Override
    public int compareTo(User o) {
        // 比較姓名長度 --> 主要條件
        int num = this.name.length() - o.name.length();
        // 姓名長度相同, 比較姓名内容 --> 次要條件
        int num2 = num == 0 ? this.name.compareTo(o.name) : num;
        // 姓名長度和内容相同, 比較年齡 --> 次要條件
        int num3 = num2 == 0 ? this.age - o.age : num2;
        return num3;
    }

    // getter...   setter...  toString...  全參構造...   無參構造...
}

/**
 * 排序方式：自然排序--按照年齡從小到大排序
 * 排序規則：
 * 注意：如果類A中的對象要進行自然排序，類必須實作自然排序接口;并在類A中實作compareTo()方法。
 */
public class Demo01 {
    @Test
    public void test01() {
        TreeSet<User> users = new TreeSet<>();
        User user01 = new User("張三", 20);
        User user02 = new User("張三", 30);
        User user03 = new User("王五", 4);
        User user04 = new User("李四", 50);
        User user05 = new User("張三", 20);
        User user06 = new User("趙六", 20);
        User user07 = new User("張三豐", 40);
        users.add(user01);
        users.add(user02);
        users.add(user03);
        users.add(user04);
        users.add(user05);
        users.add(user06);
        users.add(user07);

        users.forEach(System.out::println);

        /*
        輸出：
        User{name='張三', age=20}
        User{name='張三', age=30}
        User{name='李四', age=50}
        User{name='王五', age=4}
        User{name='趙六', age=20}
        User{name='張三豐', age=40}
         */
    }
}

3.3 比較器排序

概述：用TreeSet<E>的有參構造建立對象時提供的Comparator進行排序。
TreeSet集合使用比較器排序步驟
1. 用能使用比較器的有參構造建立TreeSet集合對象
2. 構造方法的參數傳入比較器Comparator<T>接口的實作子類A的對象
3. 自定義一個比較器實作子類A，實作比較器接口，泛型填要比較的元素類型
4. 在比較器實作子類中實作接口的compare方法
5. 方法内容寫自定義的比較規則
比較器排序示例01

package cn.king.demo01;

import org.junit.Test;
import java.util.Comparator;
import java.util.TreeSet;

class Student {
    private String name;
    private int age;
    // getter...   setter...  toString...  全參構造...   無參構造...
}

// 自定義的比較器
class MyComparator implements Comparator<Student> {
    @Override
    public int compare(Student s1, Student s2) {
        // 姓名長度
        int num = s1.getName().length() - s2.getName().length();
        // 姓名内容
        int num2 = num == 0 ? s1.getName().compareTo(s2.getName()) : num;
        // 年齡
        int num3 = num2 == 0 ? s1.getAge() - s2.getAge() : num2;
        return num3;
    }
}

// 測試
public class Demo01 {
    @Test
    public void test01() {
        // 建立集合對象用到的構造： public TreeSet(Comparator comparator)
        TreeSet<Student> ts = new TreeSet<>(new MyComparator());
        // 建立元素并 添加元素
        ts.add(new Student("linqingxia", 27));
        ts.add(new Student("zhangguorong", 29));
        ts.add(new Student("wanglihong", 23));
        ts.add(new Student("linqingxia", 27));
        ts.add(new Student("liushishi", 22));
        ts.add(new Student("wuqilong", 40));
        ts.add(new Student("fengqingy", 22));
        ts.add(new Student("linqingxia", 29));
        // 周遊
        ts.forEach(System.out::println);
    }
}

比較器排序示例02 – 使用匿名内部類

package cn.king.demo01;

import org.junit.Test;
import java.util.Comparator;
import java.util.TreeSet;

class Student {
    private String name;
    private int age;
    // getter...   setter...  toString...  全參構造...   無參構造...
}

public class Demo01 {
    @Test
    public void test01() {
        // 建立集合對象用到的構造： public TreeSet(Comparator comparator)
        TreeSet<Student> ts = new TreeSet<>(new Comparator<Student>() {
            @Override
            public int compare(Student s1, Student s2) {
                // 姓名長度
                int num = s1.getName().length() - s2.getName().length();
                // 姓名内容
                int num2 = num == 0 ? s1.getName().compareTo(s2.getName()) : num;
                // 年齡
                return num2 == 0 ? s1.getAge() - s2.getAge() : num2;
            }
        });
        // 建立元素并 添加元素
        ts.add(new Student("linqingxia", 27));
        ts.add(new Student("zhangguorong", 29));
        ts.add(new Student("wanglihong", 23));
        ts.add(new Student("linqingxia", 27));
        ts.add(new Student("liushishi", 22));
        ts.add(new Student("wuqilong", 40));
        ts.add(new Student("fengqingy", 22));
        ts.add(new Student("linqingxia", 29));
        // 周遊
        ts.forEach(System.out::println);
    }
}

比較器排序示例03 – 使用Lambda表達式

package cn.king.demo01;

import org.junit.Test;
import java.util.Comparator;
import java.util.TreeSet;

class Student {
    private String name;
    private int age;
    // getter...   setter...  toString...  全參構造...   無參構造...
}

public class Demo01 {
    @Test
    public void test01() {
        // 建立集合對象用到的構造： public TreeSet(Comparator comparator)
        TreeSet<Student> ts = new TreeSet<>((s1, s2) -> {
            // 姓名長度
            int num = s1.getName().length() - s2.getName().length();
            // 姓名内容
            int num2 = num == 0 ? s1.getName().compareTo(s2.getName()) : num;
            // 年齡
            return num2 == 0 ? s1.getAge() - s2.getAge() : num2;
        });
        // 建立元素并 添加元素
        ts.add(new Student("linqingxia", 27));
        ts.add(new Student("zhangguorong", 29));
        ts.add(new Student("wanglihong", 23));
        ts.add(new Student("linqingxia", 27));
        ts.add(new Student("liushishi", 22));
        ts.add(new Student("wuqilong", 40));
        ts.add(new Student("fengqingy", 22));
        ts.add(new Student("linqingxia", 29));
        // 周遊
        ts.forEach(System.out::println);
    }
}

比較器排序示例04 – 我們可以在條件允許的情況下使用方法引用來簡化Lambda的書寫

public class Demo01 {
    // 原來的匿名内部類
    @Test
    public void fun1() {
        Comparator<Integer> comparator = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return Integer.compare(o1, o2);
            }
        };
        TreeSet<Integer> treeSet = new TreeSet<>(comparator);
    }

    // lambda表達式.
    @Test
    public void fun2() {
        Comparator<Integer> comparator = (o1, o2) -> Integer.compare(o1, o2);
        TreeSet<Integer> treeSet = new TreeSet<>(comparator);
    }

    // 方法引用
    @Test
    public void fun3() {
        Comparator<Integer> comparator = Integer::compare;
        TreeSet<Integer> treeSet = new TreeSet<>(comparator);
    }

    // 上述的fun1 fun2 fun3 功能相同.
}

關于Lambda表達式和方法引用的使用，詳見我得另一篇部落格： Lambda表達式入門

3.4 小結

總結自然排序和比較器排序
- 自然排序(元素具備比較性)：讓元素所屬的類實作自然排序接口 Comparable
- 比較器排序(集合具備比較性)：讓集合的構造方法接收一個比較器接口的子類對象 Comparator
- 自然排序和比較器排序都能達到同樣的目的，若隻使用一次，建議使用比較器器排序，因為比較器排序能用匿名内部類或Lambda，更靈活。

Set集合保證元素不重複的原理&TreeSet集合與排序Set集合保證元素不重複的原理&Java中的排序接口

目錄

Set集合保證元素不重複的原理&Java中的排序接口

1. Set體系集合的繼承關系和特點

2. HashSet如何保證元素的唯一性

2.1 HashSet集合的簡介和HashSet#add()方法

2.2 重寫hashCode()方法的原則

2.3 重寫equals()方法的原則

3. TreeSet與排序

3.1 TreeSet集合的簡介和TreeSet#add()方法

3.2 自然排序

3.3 比較器排序

3.4 小結

繼續閱讀

Java反射具體需求實作案例一

java程式設計思想_006短路現象

九、設計模式以及查找、排序算法

這是我見過最簡單了解NIO的文章了

Map集合中get不存在的key值，傳回值問題

每日一學（14）——（面向對象）抽象類作為方法參數與傳回值

effective java-tagged class to hierarchy class

單點登入-CAS

集合練習題1

java 程式設計思想第四版學習随記

java之單使用者登入

Java反射是什麼，為什麼要用反射

Double類parseDouble和valueOf方法的差別

java調用Windows指令行

java列印任意邊長的菱形

java 8 Lamda 求 List 中 Bigdecimal類型的各種值求最大值求最小值求和求平均值

Set集合保證元素不重複的原理&amp;TreeSet集合與排序Set集合保證元素不重複的原理&amp;Java中的排序接口

目錄

Set集合保證元素不重複的原理&Java中的排序接口

1. Set體系集合的繼承關系和特點

2. HashSet如何保證元素的唯一性

2.1 HashSet集合的簡介和HashSet#add()方法

2.2 重寫hashCode()方法的原則

2.3 重寫equals()方法的原則

3. TreeSet與排序

3.1 TreeSet集合的簡介和TreeSet#add()方法

3.2 自然排序

3.3 比較器排序

3.4 小結

繼續閱讀

Set集合保證元素不重複的原理&TreeSet集合與排序Set集合保證元素不重複的原理&Java中的排序接口