09-集合2-Set、TreeSet(BST,AVL,RBT底層複習)、HashSet(哈希表，拉鍊法，RBT優化 底層複習)

文章目錄

• • 1.Set集合
  • • 1.1Set集合概述和特點【應用】
    • 1.2Set集合的使用【應用】
  • 2.TreeSet集合 (自動排序)(底層紅黑樹)
  • • 2.1TreeSet集合概述和特點【應用】
    • 2.2TreeSet集合基本使用【應用】（元素自然排序）
    • 2.3自然排序Comparable的使用【應用】 (元素規則排序)
    • 2.3自然排序Comparable的使用【應用】
    • 2.4比較器排序Comparator的使用【應用】 (使用TreeSet集合的構造方法傳遞比較規則)
    • 2.4兩種比較方式總結【了解】
  • 3.TreeSet底層就是紅黑樹
  • 3.資料結構 (簡單基礎知識 可略)
  • • 3.1二叉樹【了解】
    • 3.2二叉查找樹【了解】
    • 3.3平衡二叉樹【了解】
    • 3.4紅黑樹【了解】
    • 3.5成績排序案例【應用】
    • • ==人家幫你把資料結構寫好後，你自己用起來，那是相當友善(一點算法細節都不涉及)(但是自己要知道)==
  • 4.HashSet集合 (底層查找那章的Hash表) (不會自動排序，僅僅用Hash表去重了下)（Hash查找非常快，引入RBT後去重也非常快）(==檢視源碼底層用到了HashMap(就是一種Hash表呀)==)
  • • 4.1HashSet集合概述和特點【應用】（根據hashCode直接計算出索引值 查找很快）
    • 4.2HashSet集合的基本應用【應用】
    • 4.3哈希值【了解】
    • 4.4哈希表結構【了解】 （★真正了解了hashcode和equals方法的作用★)
    • 4.5HashSet集合存儲學生對象并周遊【應用】（用現成的資料結構太簡單享受了）
    • • 注意: ==HashSet存儲自定義對象 必須重寫equals、hashCode (否則身為一個set,去重都去不了)==
• 小知識

1.Set集合

1.1Set集合概述和特點【應用】

• 不可以存儲重複元素
• 沒有索引,不能使用普通for循環周遊 也不能通過索引來擷取删除元素(無序自然無索引)

Set一大學領：去重

Set集合一大特點：存取順序不一緻

1.2Set集合的使用【應用】

存儲字元串并周遊

public static void main(String[] args) {
        Set<String> set = new TreeSet<>();
        set.add("ccc");set.add("aaa");set.add("aaa");set.add("bbb");

        /*for (int i = 0; i < set.size(); i++) {
            //Set集合沒有索引，是以不能通過普通索引擷取元素方法周遊
        }*/

        //所有單列集合 均可用疊代器通路、周遊
        Iterator<String> it = set.iterator();
        while (it.hasNext()){
            String s = it.next();
            System.out.print(s+" ");//"aaa bbb ccc "    重複的aaa隻留下了一個 天然去重
        }

        System.out.println("\n------------");
        //Collection層面就實作了Iterable接口  是以單列集合都可以使用增強for
        for (String s : set) {
            System.out.print(s+" ");//"aaa bbb ccc "    存取的順序也變了
        }
    }
           

2.TreeSet集合 (自動排序)(底層紅黑樹)

2.1TreeSet集合概述和特點【應用】

• 不可以存儲重複元素
• 沒有索引
• 可以将元素按照規則進行排序
  • TreeSet()：根據其元素的自然排序進行排序 （預設自然排序）
  • TreeSet(Comparator comparator) ：根據指定的比較器進行排序 （指定比較規則排序）

2.2TreeSet集合基本使用【應用】（元素自然排序）

存儲Integer類型的整數并周遊

public static void main(String[] args) {
        TreeSet<Integer> ts=new TreeSet<>();
        ts.add(5);ts.add(3);ts.add(4);ts.add(1);ts.add(2);
        
        System.out.println(ts);//"[1, 2, 3, 4, 5]"  預設自然序排好了
    }
           

2.3自然排序Comparable的使用【應用】 (元素規則排序)

• 案例需求
  • 存儲學生對象并周遊，建立TreeSet集合使用無參構造方法
  • 要求：按照年齡從小到大排序
• 實作步驟
  1. 使用空參構造建立TreeSet集合
     • 用TreeSet集合存儲自定義對象，無參構造方法使用的是自然排序對元素進行排序的
  2. 自定義的Student類實作Comparable接口
     • 自然排序，就是讓元素所屬的類實作Comparable接口，重寫compareTo(T o)方法
  3. 重寫接口中的compareTo方法
     • 重寫方法時，一定要注意排序規則必須按照要求的主要條件和次要條件來寫

• 代碼實作

  學生類

  此例不指定比較規則(實作Comparable接口，重寫compareTo方法)直接add，運作時會報錯: ClassCastException

代碼：

//實作接口
public class Student implements Comparable<Student>{//泛型也要寫Student 臃腫了
    private String name;
    private Integer age;

    //此處空參構造

    //此處全參構造

    //此處所有get/set

    //此處toString
	
	//實作接口方法
    @Override
    public int compareTo(Student o) {
        //根據年齡升序排序
        int result = this.age - o.age;
        return result;
    }
	
	//不實作接口，重寫方法，add時就會報錯  TreeSet就是BST的一種，插入即開始排序，必須有比較依據
}
           

public static void main(String[] args) {
        TreeSet<Student> tss=new TreeSet<>();
        Student s1 = new Student("小米", 18);
        Student s2 = new Student("小米蜜", 17);
        Student s3 = new Student("小米米", 19);
        Student s4 = new Student("小黑", 18);//排序規則下年齡相同傳回0，即認為重複，不存入(得增強規則才行)
        tss.add(s1);tss.add(s2);tss.add(s3);tss.add(s4);
        System.out.println(tss);//年齡升序排序
    }
           

2.3自然排序Comparable的使用【應用】

• 案例需求
  • 存儲學生對象并周遊，建立TreeSet集合使用無參構造方法
  • 要求：按照年齡從小到大排序，年齡相同時，按照姓名的字母順序排序
• 實作步驟
  1. 使用空參構造建立TreeSet集合
     • 用TreeSet集合存儲自定義對象，無參構造方法使用的是自然排序對元素進行排序的
  2. 自定義的Student類實作Comparable接口
     • 自然排序，就是讓元素所屬的類實作Comparable接口，重寫compareTo(T o)方法
  3. 重寫接口中的compareTo方法
     • 重寫方法時，一定要注意排序規則必須按照要求的主要條件和次要條件來寫
     • 姓名和年齡都一樣(compareTo傳回0)，才認為是同一個學生對象，（重複元素）不存入

• 代碼實作

  學生類

public class Student implements Comparable<Student>{//泛型也要寫Student 臃腫了
    private String name;
    private Integer age;

    //此處空參構造

    //此處全參構造

    //此處所有get/set

    //此處toString

    @Override
    public int compareTo(Student o) {
        //首要條件年齡：根據年齡升序排序
        int result = this.age - o.age;
        //次要判斷條件姓名：年齡相同時根據姓名字母序排序
        if(result==0) result=this.name.compareTo(o.getName());//遇到不熟悉api，查chm文檔啊
        return result;
    }
           

測試類

public static void main(String[] args) {
        TreeSet<Student> tss=new TreeSet<>();
        Student s1 = new Student("zhangsan", 18);
        Student s2 = new Student("lisi", 17);
        Student s3 = new Student("wangwu", 19);
        Student s4 = new Student("zhaoliu", 18);
        Student s5 = new Student("qianqi", 20);
        Student s6 = new Student("zhaoliu", 18);//與s4重複不存
        tss.add(s1);tss.add(s2);tss.add(s3);tss.add(s4);tss.add(s5);tss.add(s6);

        for (Student student : tss) {
            System.out.println(student);
        }
    }
           

查下API，TreeSet的構造方法，肯定有所發現

2.4比較器排序Comparator的使用【應用】 (使用TreeSet集合的構造方法傳遞比較規則)

• 案例需求
  • 存儲老師對象并周遊，建立TreeSet集合使用帶參構造方法
  • 要求：按照年齡從小到大排序，年齡相同時，按照姓名的字母順序排序
• 實作步驟
  • 用TreeSet集合存儲自定義對象，帶參構造方法使用的是比較器排序對元素進行排序的
  • 比較器排序，就是讓集合構造方法接收Comparator的實作類對象，重寫compare(T o1,T o2)方法
  • 重寫方法時，一定要注意排序規則必須按照要求的主要條件和次要條件來寫

• 代碼實作

  老師類

public class Teacher {
    private String name;
    private Integer age;

    //此處空參構造

    //此處全參構造

    //此處所有get/set

    //此處toString
}
           

測試類1：匿名内部類

public static void main(String[] args) {
        //說明TreeSet有對應的構造器
       TreeSet<Teacher> ts = new TreeSet<>(new Comparator<Teacher>() {//new接口  也就是匿名内部類實作一下
            @Override
            public int compare(Teacher o1, Teacher o2) {
                int result = o1.getAge()-o2.getAge();
                if(result==0) result = o1.getName().compareTo(o2.getName());
                return result;
            }
        });


        Teacher t1 = new Teacher("zhangsan",23);
        Teacher t2 = new Teacher("lisi",22);
        Teacher t3 = new Teacher("wangwu",24);
        Teacher t4 = new Teacher("zhaoliu",24);
        Teacher t5 = new Teacher("wangwu",24);//重複的不存

        ts.add(t1); ts.add(t2); ts.add(t3); ts.add(t4); ts.add(t5);

        for (Teacher t : ts) {
            System.out.println(t);
        }
    }
           

測試類2：lambda表達式

public static void main(String[] args) {
        //說明TreeSet有對應的構造器
        TreeSet<Teacher> ts = new TreeSet<>((Teacher o1,Teacher o2)->{
            int result = o1.getAge()-o2.getAge();
            if(result==0) result=o1.getName().compareTo(o2.getName());
            return result;
        });

        Teacher t1 = new Teacher("zhangsan",23);
        Teacher t2 = new Teacher("lisi",22);
        Teacher t3 = new Teacher("wangwu",24);
        Teacher t4 = new Teacher("zhaoliu",24);
        Teacher t5 = new Teacher("wangwu",24);//重複的不存

        ts.add(t1); ts.add(t2); ts.add(t3); ts.add(t4); ts.add(t5);

        for (Teacher t : ts) {
            System.out.println(t);
        }
    }
           

運作結果同上

2.4兩種比較方式總結【了解】

• 兩種比較方式小結
  • 自然排序: 自定義類實作Comparable接口,重寫compareTo方法,根據傳回值進行排序
  • 比較器排序: 建立TreeSet對象的時候傳遞Comparator的實作類對象,重寫compare方法,根據傳回值進行排序
  • 在使用的時候,預設使用自然排序,當自然排序不滿足現在的需求時,必須使用比較器排序
• 兩種方式中關于傳回值的規則
  • 如果傳回值為負數，表示目前存入的元素是較小值，存左邊
  • 如果傳回值為0，表示目前存入的元素跟集合中元素重複了，不存
  • 如果傳回值為正數，表示目前存入的元素是較大值，存右邊

    

TreeSet比較器排序： “c” , “ab” , “df” , “qwer”

無法改String源碼的compareTo()方法,隻能用TreeSet<>(Comparator比較器)

public static void main(String[] args) {
        TreeSet<String> ts = new TreeSet<>((String s1,String s2)->{
            if(s1.length()!=s2.length()) return s1.length()-s2.length();
            return s1.compareTo(s2);
        });
        ts.add("c"); ts.add("qwer"); ts.add("df");  ts.add("ab");
        for (String t : ts) {
            System.out.print(t+" ");// "c ab df qwer "
        }
    }
           

3.TreeSet底層就是紅黑樹

3.資料結構 (簡單基礎知識 可略)

樹的基礎：參考 樹專題

3.1二叉樹【了解】

• 二叉樹的特點
  • 二叉樹中,任意一個節點的度要小于等于2
    • 節點: 在樹結構中,每一個元素稱之為節點
    • 度: 每一個節點的子節點數量稱之為度
• 二叉樹結構圖

  

3.2二叉查找樹【了解】

• 二叉查找樹的特點
  • 二叉查找樹,又稱二叉排序樹或者二叉搜尋樹
  • 每一個節點上最多有兩個子節點
  • 左子樹上所有節點的值都小于根節點的值
  • 右子樹上所有節點的值都大于根節點的值
• 二叉查找樹結構圖

  

• 二叉查找樹和二叉樹對比結構圖

• 二叉查找樹添加節點規則
  • 小的存左邊
  • 大的存右邊
  • 一樣的不存(修改規則也可以存儲，隻是可能不能算是嚴格意義上的BST了)

3.3平衡二叉樹【了解】

參考： 算法筆記9.5 平衡二叉樹(AVL樹)

• 平衡二叉樹的特點
  • 二叉樹左右兩個子樹的高度差不超過1
  • 任意節點的左右兩個子樹都是一顆平衡二叉樹
• 平衡二叉樹旋轉
  • 旋轉觸發時機
    • 當添加一個節點之後,該樹不再是一顆平衡二叉樹
  • 左旋
    • 就是将根節點的右側往左拉,原先的右子節點變成新的父節點,并把多餘的左子節點出讓,給已經降級的根節點當右子節點

• 右旋
  • 就是将根節點的左側往右拉,左子節點變成了新的父節點,并把多餘的右子節點出讓,給已經降級根節點當左子節點

• 平衡二叉樹和二叉查找樹對比結構圖

• 平衡二叉樹旋轉的四種情況
  • 左左
    • 左左: 當根節點左子樹的左子樹有節點插入,導緻二叉樹不平衡
    • 如何旋轉: 直接對整體進行右旋即可

• 左右
  • 左右: 當根節點左子樹的右子樹有節點插入,導緻二叉樹不平衡
  • 如何旋轉: 先在左子樹對應的節點位置進行左旋,在對整體進行右旋

• 右右
  • 右右: 當根節點右子樹的右子樹有節點插入,導緻二叉樹不平衡
  • 如何旋轉: 直接對整體進行左旋即可

• 右左
  • 右左:當根節點右子樹的左子樹有節點插入,導緻二叉樹不平衡
  • 如何旋轉: 先在右子樹對應的節點位置進行右旋,在對整體進行左旋

3.4紅黑樹【了解】

每個結點有紅或者黑兩種顔色

avl的改進，不必每次失衡都要左右旋調整，偶爾調整，(不嚴格平衡) 相對也是平衡的，效率還進一步提高了(減少調整次數)

• 紅黑樹的特點
  • 平衡二叉B樹(最初的名字)
  • 每一個節點可以是紅或者黑
  • 紅黑樹不是高度平衡的,它的平衡是通過"自己的紅黑規則"進行實作的
• 紅黑樹的紅黑規則有哪些

1. 每一個節點或是紅色的,或者是黑色的
2. 根節點必須是黑色
3. 如果一個節點沒有子節點或者父節點,則該節點相應的指針屬性值為Nil,這些Nil視為葉節點,每個葉節點(Nil)是黑色的
4. 如果某一個節點是紅色,那麼它的子節點必須是黑色(不能出現兩個紅色節點相連 的情況)
5. 對每一個節點,從該節點到其所有後代葉節點的簡單路徑上,均包含相同數目的黑色節點

根葉黑

不紅紅

黑路同

（左根右）

• 紅黑樹添加節點的預設顔色
  • 添加節點時,預設為紅色,效率高

• 紅黑樹添加節點後如何保持紅黑規則
  • 根節點位置
    • 直接變為黑色
  • 非根節點位置
    • 父節點為黑色
      • 不需要任何操作,預設紅色即可
    • 父節點為紅色
      • 叔叔節點為紅色
        1. 将"父節點"設為黑色,将"叔叔節點"設為黑色
        2. 将"祖父節點"設為紅色
        3. 如果"祖父節點"為根節點,則将根節點再次變成黑色
      • 叔叔節點為黑色
        1. 将"父節點"設為黑色
        2. 将"祖父節點"設為紅色
        3. 以"祖父節點"為支點進行旋轉

3.5成績排序案例【應用】

TreeSet底層就是紅黑樹

• 案例需求
  • 用TreeSet集合存儲多個學生資訊(姓名,國文成績,數學成績,英語成績),并周遊該集合
  • 要求: 按照總分從高到低出現

• 代碼實作

  學生類

public class Student implements Comparable<Student>{
    private String name;
    private Integer chinese;//國文成績
    private Integer math;//數學成績
    private Integer english;//英語成績

    //空參構造

    //全參構造

    //所有get/set

    public Integer getSum(){
        return chinese+math+english;
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", chinese=" + chinese +
                ", math=" + math +
                ", english=" + english +
                ", 總分=" + getSum() +
                '}';
    }

    @Override
    public int compareTo(Student o) {
        int result=this.getSum()-o.getSum();
        //總分一樣依次比較數學，英語
        if(result==0) result=this.getMath()-o.getMath();
        if(result==0) result=this.getEnglish()-o.getEnglish();
        //分數完全一樣  姓名序排序
        if(result==0) result=this.getName().compareTo(o.getName());
        return -result;//result是升序    -result是降序
    }
}
           

測試類：

public static void main(String[] args) {
        TreeSet<Student> ts=new TreeSet<>();
        Student s1 = new Student("daHei",80,80,80);
        Student s2 = new Student("erHei",90,90,90);
        Student s3 = new Student("xiaoHei",100,100,100);

        ts.add(s1);ts.add(s2);ts.add(s3);
        //根據提供的比較規則，按照紅黑樹的性質依次插入到RBT中
        //周遊時底層自動幫你中序周遊

        for (Student t : ts) {
            System.out.println(t);//ClassCastException  不添加比較條件 直接add後輸出 有問題報錯
        }
    }
           

人家幫你把資料結構寫好後，你自己用起來，那是相當友善(一點算法細節都不涉及)(但是自己要知道)

4.HashSet集合 (底層查找那章的Hash表) (不會自動排序，僅僅用Hash表去重了下)（Hash查找非常快，引入RBT後去重也非常快）(檢視源碼底層用到了HashMap(就是一種Hash表呀))

4.1HashSet集合概述和特點【應用】（根據hashCode直接計算出索引值 查找很快）

• 底層資料結構是哈希表
• 存取無序
• 不可以存儲重複元素
• 沒有索引,不能使用普通for循環周遊

4.2HashSet集合的基本應用【應用】

存儲int并周遊

public static void main(String[] args) {
        HashSet<Integer> hs=new HashSet<>();

        hs.add(10); hs.add(20); hs.add(15); hs.add(5); hs.add(8); hs.add(20);

        Iterator<Integer> it = hs.iterator();
        while (it.hasNext()){
            Integer next = it.next();
            System.out.print(next+" ");//20 5 8 10 15 無序(隻去重)
        }
        System.out.println("\n===============================");
        for (Integer h : hs) {
            System.out.print(h+" ");//20 5 8 10 15   無序(隻去重)
        }
    }
           

4.3哈希值【了解】

• 哈希值簡介

  ​ 是JDK根據對象的位址或者字元串或者數字算出來的int類型的數值

• 如何擷取哈希值

  ​ Object類中的public int hashCode()：傳回對象的哈希碼值

• 哈希值的特點
  • 同一個對象多次調用hashCode()方法傳回的哈希值是相同的
  • 預設情況下，不同對象的哈希值是不同的。而重寫hashCode()方法，可以實作讓不同對象的哈希值相同
  • 重寫hashCode一般都是通過對象屬性值計算哈希值，此時不同對象屬性值相同，哈希值也相同

4.4哈希表結構【了解】 （★真正了解了hashcode和equals方法的作用★)

hashcode就是key，根據key直接計算出位址值

沖突(兩個元素計算到同一個位址值)，equals出馬看是否是同一個元素(重複丢棄，不同則探測法或者拉鍊法)

• JDK1.8以前

  ​ 數組 + 連結清單 ★

• JDK1.8以後

  • 拉鍊節點個數少于等于8個

    ​ 數組 + 連結清單

  • 拉鍊節點個數多于8個

    ​ 數組 + 紅黑樹

    (拉鍊過長，每次比較周遊很長的一個連結清單，時間代價過大，這時将拉鍊變成紅黑樹，存儲結構沒變，時間複雜度卻降下來了)

4.5HashSet集合存儲學生對象并周遊【應用】（用現成的資料結構太簡單享受了）

• 案例需求
  • 建立一個存儲學生對象的集合，存儲多個學生對象，使用程式實作在控制台周遊該集合
  • 要求：學生對象的成員變量值相同，我們就認為是同一個對象

• 代碼實作

  學生類

public class Student {
    private String name;
    private Integer age;

    //空參構造

    //全參構造

    //所有get/set

   //tostring
	
	//HashSet存儲自定義對象 必須重寫equals、hashCode
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return Objects.equals(name, student.name) &&
                Objects.equals(age, student.age);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}
           

查找：

public static void main(String[] args) {
        HashSet<Student> hs= new HashSet<>();

        Student s1 = new Student("xiaohei", 23);
        Student s2 = new Student("xiaohei", 23);
        Student s3 = new Student("xiaomei", 22);

        hs.add(s1);hs.add(s2);hs.add(s3);

        for (Student h : hs) {
            System.out.println(h);//去重 但 無序
        }
    }
           

• 總結

  ​ HashSet集合存儲自定義類型元素,要想實作元素的唯一,要求必須重寫hashCode方法和equals方法

注意: HashSet存儲自定義對象 必須重寫equals、hashCode (否則身為一個set,去重都去不了)

小知識

遇到不熟悉api，查chm文檔啊

• TreeSet：

  1、首先是Set 元素不重複

  2、其實底層是紅黑樹(前提也是BST),天然有序(中序周遊)，查找效率O(2log2n)

  紅黑樹插入時既可以有序，有可以去重(相等不插入就是了)

• HashSet:

  1、首先是Set 元素不重複

  2、底層是Hash表，equals方法，Hash[n]表記錄是否出現過，來去重了下。

  3、元素打亂，無序(不會自動給你排序，沒有那個機制)

  Hash表，隻能去重，無法排序，是以隻能排序