2020.5.17

Set接口

特點：相對于list接口，set接口不能包含重複元素，并且可以有null元素
常用的set子集合

HashSet集合

特點：底層用的是哈希表存放元素，在1.7之前哈希表是用連結清單和數組存放，1.8之後優化成連結清單，數組和二叉樹。
哈希表原理：

Set接口以及子集合（HashSet/LinkedHashSet/TreeSet）的用法和資料結構2020.5.17

一個資料儲存過程，先根據元素通過hash函數，計算出元素的哈希值，由于哈希值比較大，然後用該數字對數組長度取餘，得到的資料就是數組對應的下标，由于數組長度是有限的，是以在存儲過程中可能會出現碰撞，多個元素計算的結果對應一個數組下标，連結清單就解決了這個情況，如果計算出的數組下标相同，就判斷是否是同一個元素，如果是同一個元素，就不存儲。不是就使用連結清單存放。
是以我們在存放對象時，對象就要重寫Hash()方法那和equals()方法，重寫Hash()方法是為了減少碰撞，重寫equals()是避免元素重複。
- 元素特征轉變為數組下标的方法就是散列法。散列法當然不止一種，下面列出三種比較常用的：
1，除法散列法

最直覺的一種，上圖使用的就是這種散列法，公式：

index = value % 16

學過彙編的都知道，求模數其實是通過一個除法運算得到的，是以叫“除法散列法”。

2，平方散列法

求index是非常頻繁的操作，而乘法的運算要比除法來得省時（對現在的CPU來說，估計我們感覺不出來），是以我們考慮把除法換成乘法和一個位移操作。公式：

index = (value * value) >> 28 （右移，除以2^28。記法：左移變大，是乘。右移變小，是除。）

如果數值配置設定比較均勻的話這種方法能得到不錯的結果，但我上面畫的那個圖的各個元素的值算出來的index都是0——非常失敗。也許你還有個問題，value如果很大，value * value不會溢出嗎？答案是會的，但我們這個乘法不關心溢出，因為我們根本不是為了擷取相乘結果，而是為了擷取index。

3，斐波那契（Fibonacci）散列法

平方散列法的缺點是顯而易見的，是以我們能不能找出一個理想的乘數，而不是拿value本身當作乘數呢？答案是肯定的。

1，對于16位整數而言，這個乘數是40503

2，對于32位整數而言，這個乘數是2654435769

3，對于64位整數而言，這個乘數是11400714819323198485
```
這幾個“理想乘數”是如何得出來的呢？這跟一個法則有關，叫黃金分割法則，而描述黃金分割法則的最經典表達式無疑就是著名的斐波那契數列，即如此形式的序列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377, 610， 987, 1597, 2584, 4181, 6765, 10946，…。另外，斐波那契數列的值和太陽系八大行星的軌道半徑的比例出奇吻合。
  
  對我們常見的32位整數而言，公式： 
          index = (value * 2654435769) >> 28
           
```
原文連結：https://blog.csdn.net/duan19920101/article/details/51579136
影響Hash碰撞（沖突）發生的除了Hash函數本身意外，底層數組容量也是一個重要原因。很明顯，極端情況下如果數組容量為1，哪必然發生碰撞，如果數組容量無限大，哪碰撞的機率非常之低。是以，哈希碰撞還取決于負載因子。負載因子是存儲的鍵值對數目與數組容量的比值，比如數組容量100，目前存貯了90個鍵值對，負載因子為0.9。負載因子決定了哈希表什麼時候擴容，如果負載因子的值太大，說明存儲的鍵值對接近容量，增加碰撞的風險，如果值太小，則浪費空間。
優點：因為它集合了數組和連結清單的特點，是以它查詢塊，增删也快。
缺點：它是基于數組的，數組建立後難于擴充，某些哈希表被基本填滿時，性能下降得非常嚴重，是以必須要清楚表中将要存儲多少資料。

構造方法及方法

Set接口以及子集合（HashSet/LinkedHashSet/TreeSet）的用法和資料結構2020.5.17
代碼示例：

1.package org.westos.demo0518; 
 
/*Author:LH
CreatTime:2020.05.18.15:04*/

import java.util.HashSet;
import java.util.Iterator;
import java.util.function.Consumer;

public class MyTest {
    public static void main(String[] args) {
        HashSet<Integer> hashset = new HashSet<>();
        hashset.add(100);
        hashset.add(200);
        hashset.add(200);
        hashset.add(300);
        System.out.println(hashset);
        System.out.println("========");
//        疊代器周遊方法
        Iterator<Integer> iterator = hashset.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
        System.out.println("++++++++");
//        增強for循環周遊方法
        for (Integer integer : hashset) {
            System.out.println(integer);
        }
        System.out.println("++++++++");
//        foreach周遊方法
        hashset.forEach(new Consumer<Integer>() {
            @Override
            public void accept(Integer integer) {
                System.out.println(integer);
            }
        });
        /*集合中存放的是Integer和String類型時，不用手動重寫hash方法和equals方法
        * 因為這兩個類型已經預設重寫了此方法，是以資料才會存進去并去重。
        * */
    }
}
2.package org.westos.demo0518; 
 
/*Author:LH
CreatTime:2020.05.18.15:15*/
import java.util.HashSet;
//要将Student對象存入set集合，對象就要重寫Hash方法和equals方法,來保證元素唯一性
public class MyTest2 {
    public static void main(String[] args) {
        HashSet<Student> hashset = new HashSet<>();
        hashset.add(new Student("小王",23));
        hashset.add(new Student("李輝",23));
        hashset.add(new Student("王培紅",24));
        hashset.add(new Student("紮西格勒",25));
        hashset.add(new Student("東方日出2",26));
//        System.out.println(hashset);
        for (Student student : hashset) {
            System.out.println(student.toString());
        }
    }
}
package org.westos.demo0518; 
 
/*Author:LH
CreatTime:2020.05.18.15:16*/

import java.util.Objects;

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

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public Student() {
    }

    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);
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}
3.package org.westos.demo0518; 
 
/*Author:LH
CreatTime:2020.05.18.15:51*/

import java.util.ArrayList;
import java.util.LinkedHashSet;

//将list集合中重複元素去除。
//可以自己寫方法去掉，也可以根據set集合的特點，轉換
public class MyTest3 {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(100);
        list.add(100);
        list.add(300);
        list.add(200);
        list.add(300);
        list.add(500);
        list.add(600);
        list.add(700);
        for (Integer integer : list) {
            System.out.println(integer);
        }
        System.out.println("==========");
//        使用有參構造,将list集合傳入，建立新的set集合，将自動去除重複元素
        LinkedHashSet<Object> linkedHashSet = new LinkedHashSet<>(list);
        for (Object o : linkedHashSet) {
            System.out.println(o);
        }
    }
}

LinkedHashSet集合

它的底層資料結構是連結清單和哈希表，連結清單保證有序（存取順序一緻），哈希表保證元素唯一。是以此集合的特點是元素有序，且唯一。但是線程不安全。
構造方法及方法

Set接口以及子集合（HashSet/LinkedHashSet/TreeSet）的用法和資料結構2020.5.17

案例示範：

1.package org.westos.demo0518.LinkedHashSet; 
 
/*Author:LH
CreatTime:2020.05.18.16:08*/

import java.util.LinkedHashSet;
//LinkedHashSet集合存取元素順序一緻，保證元素唯一性。
public class Test {
    public static void main(String[] args) {
        LinkedHashSet<Integer> integers = new LinkedHashSet<>();
        integers.add(100);
        integers.add(200);
        integers.add(200);
        integers.add(300);
        integers.add(300);
        integers.add(400);
        for (Integer integer : integers) {
            System.out.println(integer);
        }
    }
}

2.package org.westos.demo0518.LinkedHashSet; 
 
/*Author:LH
CreatTime:2020.05.18.16:35*/

import java.util.LinkedHashSet;
//LinkedHashSet存自定義對象，也要重寫Hash方法和equals方法，來保證元素的唯一性
public class Test2 {
    public static void main(String[] args) {
        LinkedHashSet<Student> linkedHashSet = new LinkedHashSet<>();
        linkedHashSet.add(new Student("李瑤",23));
        linkedHashSet.add(new Student("李其",23));
        linkedHashSet.add(new Student("李其",23));
        linkedHashSet.add(new Student("章子路",23));
        linkedHashSet.add(new Student("章子路",23));
        linkedHashSet.add(new Student("上官風雨",23));
        for (Student student : linkedHashSet) {
            System.out.println(student.toString());
        }
    }
}
package org.westos.demo0518.LinkedHashSet;
 
/*Author:LH
CreatTime:2020.05.18.15:16*/

import java.util.Objects;

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

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public Student() {
    }

    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);
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

TreeSet集合

底層資料結構是二叉樹，可以對元素排序，并且保證元素唯一性。
二叉樹原理圖

Set接口以及子集合（HashSet/LinkedHashSet/TreeSet）的用法和資料結構2020.5.17

二叉樹存放資料，将進來的資料和根資料對比，根據排序方法，将資料放在其左右，相同元素不能被存放。

方法和構造方法

Set接口以及子集合（HashSet/LinkedHashSet/TreeSet）的用法和資料結構2020.5.17

代碼示範：

1.package org.westos.demo0518.TreeSet; 
 
/*Author:LH
CreatTime:2020.05.19.16:26*/
//TreeSet集合使用自然排序存Integer類型資料
import java.util.Iterator;
import java.util.TreeSet;
import java.util.function.Consumer;

public class Test {
    public static void main(String[] args) {
        TreeSet<Integer> treeSet = new TreeSet<>();
        treeSet.add(23);
        treeSet.add(14);
        treeSet.add(15);
        treeSet.add(28);
        treeSet.add(8);
        Iterator<Integer> iterator = treeSet.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
        for (Integer integer : treeSet) {
            System.out.println(integer);
        }
        treeSet.forEach(new Consumer<Integer>() {
            @Override
            public void accept(Integer integer) {
                System.out.println(integer);
            }
        });
    }
}
2.package org.westos.demo0518.TreeSet; 
 
/*Author:LH
CreatTime:2020.05.19.16:31*/

import java.util.Comparator;
import java.util.TreeSet;
//使用比較器排序
public class Test2 {
    public static void main(String[] args) {
//        重寫Comparator接口的compare方法。
        TreeSet<Integer> treeSet = new TreeSet<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });
        treeSet.add(12);
        treeSet.add(34);
        treeSet.add(14);
        treeSet.add(67);
        treeSet.add(2);
        for (Integer integer : treeSet) {
            System.out.println(integer);
        }
    }
}
3.package org.westos.demo0518.TreeSet; 
 
/*Author:LH
CreatTime:2020.05.19.16:35*/

import java.util.TreeSet;
//TreeSet集合使用自然排序存自定義對象
public class TestStudent {
    public static void main(String[] args) {
        TreeSet<Student> treeSet = new TreeSet<>();
        treeSet.add(new Student("張三",23));
        treeSet.add(new Student("李四",23));
        treeSet.add(new Student("張三",25));
        treeSet.add(new Student("王五",28));
        treeSet.add(new Student("趙六",23));
        for (Student student : treeSet) {
            System.out.println(student.toString());
        }
    }
}
package org.westos.demo0518.TreeSet;
 
/*Author:LH
CreatTime:2020.05.18.15:16*/
// 自定義對象實作 Comparable<Student>，如果能明确泛型，一定要準确的把泛型寫出來，此處不寫也不會報錯，
//隻是重寫compareTo(Student o)方法時，括号給的是Object資料類型，需要轉型。
public class Student implements Comparable<Student> {
    private String name;
    private int age;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public Student() {
    }

    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 String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    @Override
//    根據年齡大小排序，如果年齡相同，再判斷姓名是否相同，相同就是同一個元素，不同則存進來
    public int compareTo(Student o) {
        int num=this.age-o.age;
        int num2=num==0?this.name.compareTo(o.name):num;
        return num2;
    }
}
4.package org.westos.demo0518.TreeSet; 
 
/*Author:LH
CreatTime:2020.05.19.17:09*/

import java.util.Comparator;
import java.util.TreeSet;
//使用比較器對自定義對象排序
public class TestStudent2 {
    public static void main(String[] args) {
        TreeSet<Student2> treeSet = new TreeSet<>(new Comparator<Student2>() {
            @Override
            //    根據年齡大小排序，如果年齡相同，再判斷姓名是否相同，相同就是同一個元素，不同則存進來
            public int compare(Student2 o1, Student2 o2) {
                int num=o1.getAge()-o2.getAge();
                int num2=num==0?o1.getName().compareTo(o2.getName()):num;
                return num2;
            }
        });
        treeSet.add(new Student2("張三",18));
        treeSet.add(new Student2("李四",18));
        treeSet.add(new Student2("王五",27));
        treeSet.add(new Student2("李輝",18));
        treeSet.add(new Student2("張三",18));
        for (Student2 student2 : treeSet) {
            System.out.println(student2.toString());
        }
    }
}
package org.westos.demo0518.TreeSet;
 
/*Author:LH
CreatTime:2020.05.18.15:16*/

public class Student2 {
    private String name;
    private int age;

    public Student2(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public Student2() {
    }

    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 String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}
5.package org.westos.demo0518.TreeSet;

import java.util.LinkedHashSet;
import java.util.Random;

/*Author:LH
CreatTime:2020.05.19.17:17*/
/*編寫一個程式，擷取10個1至20的随機數，要求随機數不能重複。
        并把最終的随機數輸出到控制台。*/
public class Test3 {
    public static void main(String[] args) {
        Random random = new Random();
        LinkedHashSet<Integer> integers = new LinkedHashSet<>();
        while (integers.size()<=10) {
            int i = random.nextInt(20)+1;
            integers.add(i);
        }
        for (Integer integer : integers) {
            System.out.println(integer);
        }
    }
}
6.package org.westos.demo0518.TreeSet; 
 
/*Author:LH
CreatTime:2020.05.19.17:51*/

//案例示範:	需求：鍵盤錄入3個學生資訊(姓名,國文成績,數學成績,英語成績),按照總分從高到低輸出到控制台。

import java.util.Comparator;
import java.util.TreeSet;

/**
 * 步驟:
 * 		a: 自定義一個學生類
 * 		b: 建立一個TreeSet集合對象(使用比較器進行排序)
 * 		c: 鍵盤錄入學生的資料,然後把學生的資料封裝成一個學生對象,把學生對象添加到集合中
 * 		d: 周遊集合
 */
public class Test4 {
    public static void main(String[] args) {
        TreeSet<Student3> treeSet = new TreeSet<>(new Comparator<Student3>() {
            @Override
            public int compare(Student3 o1, Student3 o2) {
                int num=o1.getSum()-o2.getSum();
                int num2=num==0?o1.getName().compareTo(o2.getName()):num;
                return num2;
            }
        });
        treeSet.add(new Student3("張三",60,20,40));
        treeSet.add(new Student3("張三",67,20,47));
        treeSet.add(new Student3("李四",60,20,40));
        treeSet.add(new Student3("王五",69,90,41));
        treeSet.add(new Student3("張三",67,20,47));
        treeSet.add(new Student3("趙六",27,20,47));
        for (Student3 student3 : treeSet) {
            System.out.println(student3.toString());
        }
    }
}
package org.westos.demo0518.TreeSet; 
 
/*Author:LH
CreatTime:2020.05.19.17:53*/

public class Student3 {
    private String name;
    private  int chineseScore;
    private  int englishScore;
    private  int mathScore;

    public Student3(String name, int chineseScore, int englishScore, int mathScore) {
        this.name = name;
        this.chineseScore = chineseScore;
        this.englishScore = englishScore;
        this.mathScore = mathScore;
    }

    public Student3() {
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getChineseScore() {
        return chineseScore;
    }

    public void setChineseScore(int chineseScore) {
        this.chineseScore = chineseScore;
    }

    public int getEnglishScore() {
        return englishScore;
    }

    public void setEnglishScore(int englishScore) {
        this.englishScore = englishScore;
    }

    public int getMathScore() {
        return mathScore;
    }

    public void setMathScore(int mathScore) {
        this.mathScore = mathScore;
    }
    public int getSum(){
        return chineseScore+englishScore+mathScore;
    }

    @Override
    public String toString() {
        return
                "name='" + name + '\''+
                 '\t'+"chineseScore=" + chineseScore +
                '\t'+ "englishScore=" + englishScore +
                '\t'+"mathScore=" + mathScore +'\t'+
                "總分"+getSum();
    }
}

  public void setEnglishScore(int englishScore) {
        this.englishScore = englishScore;
    }

    public int getMathScore() {
        return mathScore;
    }

    public void setMathScore(int mathScore) {
        this.mathScore = mathScore;
    }
    public int getSum(){
        return chineseScore+englishScore+mathScore;
    }

    @Override
    public String toString() {
        return
                "name='" + name + '\''+
                 '\t'+"chineseScore=" + chineseScore +
                '\t'+ "englishScore=" + englishScore +
                '\t'+"mathScore=" + mathScore +'\t'+
                "總分"+getSum();
    }
}

Set接口以及子集合（HashSet/LinkedHashSet/TreeSet）的用法和資料結構2020.5.17

2020.5.17

Set接口

HashSet集合

LinkedHashSet集合

TreeSet集合

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

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

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

Linux裝置模型（中）之上層容器