Java中Set集合的使用和底層原理解析

更新時間：2022年12月10日 10:42:42 作者：藍(lán)桉cyq

這篇文章主要介紹了Java中Set集合的使用和底層原理,Set集合的功能上基本上與Collection的API一致, Set集合沒有擴展額外的API，本文通過示例代碼給大家詳細(xì)講解，需要的朋友可以參考下

Set系列集合介紹

Set集合概述

Set系列集合特點:

無序：存取數(shù)據(jù)的順序是不一定的, 當(dāng)數(shù)據(jù)存入后, 集合的順序就固定下來了

不重復(fù)：可以去除重復(fù)

無索引：沒有帶索引的方法，所以不能使用普通for循環(huán)遍歷，也不能通過索引來獲取元素。

Set集合實現(xiàn)類特點:

HashSet : 無序、不重復(fù)、無索引。

public static void main(String[] args) {
  	// 無序, 不重復(fù), 無索引
    Set<String> sets = new HashSet<>();
    sets.add("MySQL");
    sets.add("MySQL");
    sets.add("JAVA");
    sets.add("JAVA");
    sets.add("HTML");
    sets.add("HTML");
    sets.add("Vue");
    sets.add("Vue");
    System.out.println(sets); // [JAVA, MySQL, Vue, HTML]
}

LinkedHashSet：有序、不重復(fù)、無索引。

public static void main(String[] args) {
  	// 有序、不重復(fù)、無索引
    Set<String> sets = new LinkedHashSet<>();
    sets.add("MySQL");
    sets.add("MySQL");
    sets.add("JAVA");
    sets.add("JAVA");
    sets.add("HTML");
    sets.add("HTML");
    sets.add("Vue");
    sets.add("Vue");
    System.out.println(sets); // [MySQL, JAVA, HTML, Vue]
}

TreeSet：排序: 默認(rèn)升序、不重復(fù)、無索引。

public static void main(String[] args) {
    // 排序、不重復(fù)、無索引
    Set<Integer> sets = new TreeSet<>();
    sets.add(10);
    sets.add(10);
    sets.add(20);
    sets.add(20);
    sets.add(30);
    sets.add(30);
    sets.add(40);
    sets.add(40);
    sets.add(50);
    sets.add(50);
    System.out.println(sets); // [10, 20, 30, 40, 50]
}

Set集合的功能上基本上與Collection的API一致, Set集合沒有擴展額外的API。

HashSet無序原理

HashSet集合底層采取哈希表存儲的數(shù)據(jù)。

哈希表是一種對于增刪改查數(shù)據(jù)性能都較好的結(jié)構(gòu)。

哈希表的組成:

JDK8之前的，底層使用數(shù)組+鏈表組成

JDK8開始后，底層采用數(shù)組+鏈表+紅黑樹組成。

哈希表是一種對于增刪改查數(shù)據(jù)性能都較好的結(jié)構(gòu)。

在了解哈希表之前需要先理解哈希值的概念

哈希值:

是JDK根據(jù)對象的地址，按照某種規(guī)則算出來的int類型的數(shù)值。

獲取哈希值: 通過Object類的API:

public int hashCode()：返回對象的哈希值

對象的哈希值特點:

同一個對象多次調(diào)用hashCode()方法返回的哈希值是相同的

public static void main(String[] args) {
    String address = "成都市";
    System.out.println(address.hashCode()); // 25299637
    System.out.println(address.hashCode()); // 25299637
    System.out.println(address.hashCode()); // 25299637
}

默認(rèn)情況下，不同對象的哈希值是不同的。

public static void main(String[] args) {
    String address = "成都市";
    System.out.println(address.hashCode()); // 25299637
    System.out.println(address.hashCode()); // 25299637
    System.out.println(address.hashCode()); // 25299637

    String address2 = "重慶市";
    System.out.println(address2.hashCode()); // 36643529
}

JDK8之前的版本HashSet原理解析：數(shù)組 + 鏈表 +（結(jié)合哈希算法）, 詳細(xì)流程如下:

底層會默認(rèn)創(chuàng)建一個默認(rèn)長度16的數(shù)組，數(shù)組名table

在這里插入圖片描述

根據(jù)元素的哈希值跟數(shù)組的長度求余計算出應(yīng)存入的位置（哈希算法）

例如數(shù)組長度是16, 哈希值與16取余, 得出的結(jié)果一定是0到15之間的數(shù)字

判斷當(dāng)前位置是否為null，如果是null直接存入如果位置不為null，表示有元素，則調(diào)用equals方法比較如果一樣，則不存，如果不一樣，則存入數(shù)組

在JDK 7中, 新元素占老元素位置，并且新元素會指向老元素

在JDK 8中, 新元素掛在老元素下面

JDK8之后的版本HashSet原理解析:

底層結(jié)構(gòu)：哈希表（數(shù)組、鏈表、紅黑樹的結(jié)合體）

當(dāng)掛在元素下面的數(shù)據(jù)過多時，查詢性能降低，從JDK8開始后，當(dāng)鏈表長度超過8的時候，自動轉(zhuǎn)換為紅黑樹。

在這里插入圖片描述

JDK8開始后，哈希表對于紅黑樹的引入進一步提高了操作數(shù)據(jù)的性能。

Set集合對象去重

HashSet去重注意點:

Set集合在比較兩個對象時, 默認(rèn)比較的是兩個對象的地址是否一致, 若地址不同則認(rèn)為是兩個不同的對象;

而如果希望Set集合認(rèn)為2個內(nèi)容一樣的對象是重復(fù)的，則需要自己重寫對象的hashCode()和equals()方法

我們來看下面這樣一個案例:

需求: 創(chuàng)建一個存儲學(xué)生對象的集合，存儲多個學(xué)生對象，使用程序?qū)崿F(xiàn)在控制臺遍歷該集合，要求：學(xué)生對象的成員變量值相同，我們就認(rèn)為是同一個對象

分析:

定義學(xué)生類，創(chuàng)建Set集合對象, 創(chuàng)建學(xué)生對象

把學(xué)生添加到集合

在學(xué)生類中重寫兩個方法，hashCode()和equals()，自動生成即可

步驟一: 定義學(xué)生類

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

    // 構(gòu)造器
    public Student() {};

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

    // getter和setter方法
    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;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }
  
    // 重寫toString方法
    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                ", id=" + id +
                '}';
    }
}

步驟二: 創(chuàng)建學(xué)生對象和HashSet集合, 并將學(xué)生對象存入HashSet集合中, 如下代碼:

public class Test {
    public static void main(String[] args) {
        // 創(chuàng)建集合存儲學(xué)生對象
        Set<Student> students = new HashSet<>();
        // 創(chuàng)建學(xué)生對象
        Student stu1 = new Student("小明", 18, 101);
        Student stu2 = new Student("小明", 18, 101);
        Student stu3 = new Student("小王", 20, 102);
        // 將學(xué)生對象添加到集合中
        students.add(stu1);
        students.add(stu2);
        students.add(stu3);

        System.out.println(students);
        // 打印結(jié)果如下: 
        //  [Student{name='小明', age=18, id=101}, 
        //  Student{name='小明', age=18, id=101}, 
        //  Student{name='小王', age=20, id=102}]
    }
}

步驟三: 我們發(fā)現(xiàn)步驟二代碼中, stu1和stu2對象的內(nèi)容完全一樣, 但是由于對象的地址不一樣, 會被當(dāng)成兩個不同的對象存入到集合中; 因此我們需要在學(xué)生類中重寫兩個方法，hashCode()和equals()，自動生成即可

@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 && id == student.id && Objects.equals(name, student.name);
}

@Override
public int hashCode() {
  	// 該方法傳入的參數(shù)相同, 就會返回相同的哈希值
    return Objects.hash(name, age, id);
}

步驟四: 此時再將stu1和stu2對象存入集合, 由于內(nèi)容一樣就會被去掉重復(fù)的

public class Test {
    public static void main(String[] args) {
        // 創(chuàng)建集合存儲學(xué)生對象
        Set<Student> students = new HashSet<>();
        // 創(chuàng)建學(xué)生對象
        Student stu1 = new Student("小明", 18, 101);
        Student stu2 = new Student("小明", 18, 101);
        Student stu3 = new Student("小王", 20, 102);
        // 將學(xué)生對象添加到集合中
        students.add(stu1);
        students.add(stu2);
        students.add(stu3);

        System.out.println(students);
        //  [Student{name='小王', age=20, id=102}, Student{name='小明', age=18, id=101}]
    }
}

LinkedHashSet

LinkedHashSet集合概述和特點:

有序、不重復(fù)、無索引。

這里的有序指的是保證存儲和取出的元素順序一致

原理：

底層數(shù)據(jù)結(jié)構(gòu)是依然哈希表，只是每個元素又額外的多了一個雙鏈表的機制記錄存儲的順序。

在這里插入圖片描述

TreeSet排序規(guī)則

TreeSet集合特點:

不重復(fù)、無索引、可排序

可排序：按照元素的大小默認(rèn)升序（有小到大）排序。

TreeSet集合底層是基于紅黑樹的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)排序的，增刪改查性能都較好。

注意：TreeSet集合是一定要排序的，可以將元素按照指定的規(guī)則進行排序。

TreeSet默認(rèn)排序規(guī)則:

對于數(shù)值類型：Integer , Double，官方默認(rèn)按照大小進行升序排序。

public static void main(String[] args) {
    Set<Integer> sets1 = new TreeSet<>();
    sets1.add(50);
    sets1.add(10);
    sets1.add(30);
    sets1.add(20);
    System.out.println(sets1); // [10, 20, 30, 50]

    Set<Double> sets2 = new TreeSet<>();
    sets2.add(10.11);
    sets2.add(20.22);
    sets2.add(43.22);
    sets2.add(8.22);
    System.out.println(sets2); // [8.22, 10.11, 20.22, 43.22]
}

對于字符串類型：默認(rèn)按照首字符的編號升序排序。

public static void main(String[] args) {
    Set<String> sets = new TreeSet<>();
    sets.add("bbb");
    sets.add("eee");
    sets.add("aaa");
    sets.add("ccc");
    System.out.println(sets); // [aaa, bbb, ccc, eee]
}

對于自定義類型如Student對象，TreeSet無法直接排序, 需要制定排序規(guī)則; 例如下面代碼中向集合中添加學(xué)生類, TreeSet是無法進行排序的, 會崩潰報錯。

// 錯誤演示
public static void main(String[] args) {
    // 創(chuàng)建學(xué)生對象
    Student stu1 = new Student("小明", 18, 101);
    Student stu2 = new Student("小趙", 18, 102);
    Student stu3 = new Student("小王", 18, 103);
    // 創(chuàng)建集合
    Set<Student> students = new TreeSet<>();
    students.add(stu1);
    students.add(stu2);
    students.add(stu3);
    System.out.println(students);
}

自定義排序規(guī)則: TreeSet集合存儲對象的的時候有2種方式可以設(shè)計自定義比較規(guī)則

方式一: 讓自定義的類（如學(xué)生類）實現(xiàn)Comparable接口, 并重寫compareTo方法來定制比較規(guī)則。

// 實現(xiàn)Comparable接口
public class Student implements Comparable<Student> {
  	// 其他代碼...
  
  	// 重寫compareTo方法
    @Override
    public int compareTo(Student o) {
        // 例如按照id進行排序
        return this.id - o.id;
    }
}

public static void main(String[] args) {
    // 創(chuàng)建學(xué)生對象
    Student stu1 = new Student("小明", 18, 101);
    Student stu2 = new Student("小趙", 18, 102);
    Student stu3 = new Student("小王", 18, 103);
    // 創(chuàng)建集合
    Set<Student> students = new TreeSet<>();
    students.add(stu1);
    students.add(stu2);
    students.add(stu3);
    System.out.println(students);
    // 打印結(jié)果: 按照id升序
    // [Student{name='小明', age=18, id=101}, 
    // Student{name='小趙', age=18, id=102}, 
    // Student{name='小王', age=18, id=103}]
}

方式二: TreeSet集合有參數(shù)構(gòu)造器自帶比較器對象，來進行定制比較規(guī)則, 并且該方法如果和方式一同時出現(xiàn), 會優(yōu)先使用此方法的比較規(guī)則。

public class SetDemo {
    public static void main(String[] args) {
        // 創(chuàng)建學(xué)生對象
        Student stu1 = new Student("小明", 18, 101);
        Student stu2 = new Student("小趙", 18, 102);
        Student stu3 = new Student("小王", 18, 103);
        // 創(chuàng)建集合
        // 方式二: 使用構(gòu)造器自帶的比較器對象
        Set<Student> students = new TreeSet<>(new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                return o2.getId() - o1.getId();
            }
        });
        students.add(stu1);
        students.add(stu2);
        students.add(stu3);
        System.out.println(students);
        // 打印結(jié)果: 按照id降序
        // [Student{name='小王', age=18, id=103},
        // Student{name='小趙', age=18, id=102},
        // Student{name='小明', age=18, id=101}]
    }
}

并且可以使用Lambda表達式簡化代碼

public class SetDemo {
    public static void main(String[] args) {
        // 創(chuàng)建學(xué)生對象
        Student stu1 = new Student("小明", 18, 101);
        Student stu2 = new Student("小趙", 18, 102);
        Student stu3 = new Student("小王", 18, 103);
        // 創(chuàng)建集合
        // 方式二: 使用構(gòu)造器自帶的比較器對象
        Set<Student> students = new TreeSet<>((Student o1, Student o2) -> o2.getId() - o1.getId());
        
        students.add(stu1);
        students.add(stu2);
        students.add(stu3);
        System.out.println(students);
        // 打印結(jié)果: 按照id降序
        // [Student{name='小王', age=18, id=103},
        // Student{name='小趙', age=18, id=102},
        // Student{name='小明', age=18, id=101}]
    }
}

到此這篇關(guān)于Java中Set集合的使用和底層原理的文章就介紹到這了,更多相關(guān)Java中Set集合的使用內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: