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

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

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

Set系列集合介紹

Set集合概述

Set系列集合特點(diǎn):

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

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

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

Set集合實(shí)現(xiàn)類特點(diǎn):

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

public static void main(String[] args) {
  	// 無(wú)序, 不重復(fù), 無(wú)索引
    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ù)、無(wú)索引。

public static void main(String[] args) {
  	// 有序、不重復(fù)、無(wú)索引
    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ù)、無(wú)索引。

public static void main(String[] args) {
    // 排序、不重復(fù)、無(wú)索引
    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集合沒(méi)有擴(kuò)展額外的API。

HashSet無(wú)序原理

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

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

哈希表的組成:

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

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

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

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

哈希值:

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

獲取哈希值: 通過(guò)Object類的API:

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

對(duì)象的哈希值特點(diǎn):

同一個(gè)對(duì)象多次調(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)情況下，不同對(duì)象的哈希值是不同的。

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ì)流程如下:

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

在這里插入圖片描述

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

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

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

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

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

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

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

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

在這里插入圖片描述

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

Set集合對(duì)象去重

HashSet去重注意點(diǎn):

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

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

我們來(lái)看下面這樣一個(gè)案例:

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

分析:

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

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

在學(xué)生類中重寫(xiě)兩個(gè)方法，hashCode()和equals()，自動(dòng)生成即可

步驟一: 定義學(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;
    }
  
    // 重寫(xiě)toString方法
    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                ", id=" + id +
                '}';
    }
}

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

public class Test {
    public static void main(String[] args) {
        // 創(chuàng)建集合存儲(chǔ)學(xué)生對(duì)象
        Set<Student> students = new HashSet<>();
        // 創(chuàng)建學(xué)生對(duì)象
        Student stu1 = new Student("小明", 18, 101);
        Student stu2 = new Student("小明", 18, 101);
        Student stu3 = new Student("小王", 20, 102);
        // 將學(xué)生對(duì)象添加到集合中
        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對(duì)象的內(nèi)容完全一樣, 但是由于對(duì)象的地址不一樣, 會(huì)被當(dāng)成兩個(gè)不同的對(duì)象存入到集合中; 因此我們需要在學(xué)生類中重寫(xiě)兩個(gè)方法，hashCode()和equals()，自動(dòng)生成即可

@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ù)相同, 就會(huì)返回相同的哈希值
    return Objects.hash(name, age, id);
}

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

public class Test {
    public static void main(String[] args) {
        // 創(chuàng)建集合存儲(chǔ)學(xué)生對(duì)象
        Set<Student> students = new HashSet<>();
        // 創(chuàng)建學(xué)生對(duì)象
        Student stu1 = new Student("小明", 18, 101);
        Student stu2 = new Student("小明", 18, 101);
        Student stu3 = new Student("小王", 20, 102);
        // 將學(xué)生對(duì)象添加到集合中
        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集合概述和特點(diǎn):

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

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

原理：

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

在這里插入圖片描述

TreeSet排序規(guī)則

TreeSet集合特點(diǎn):

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

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

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

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

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

對(duì)于數(shù)值類型：Integer , Double，官方默認(rèn)按照大小進(jì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]
}

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

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]
}

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

// 錯(cuò)誤演示
public static void main(String[] args) {
    // 創(chuàng)建學(xué)生對(duì)象
    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集合存儲(chǔ)對(duì)象的的時(shí)候有2種方式可以設(shè)計(jì)自定義比較規(guī)則

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

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

public static void main(String[] args) {
    // 創(chuàng)建學(xué)生對(duì)象
    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)造器自帶比較器對(duì)象，來(lái)進(jìn)行定制比較規(guī)則, 并且該方法如果和方式一同時(shí)出現(xiàn), 會(huì)優(yōu)先使用此方法的比較規(guī)則。

public class SetDemo {
    public static void main(String[] args) {
        // 創(chuàng)建學(xué)生對(duì)象
        Student stu1 = new Student("小明", 18, 101);
        Student stu2 = new Student("小趙", 18, 102);
        Student stu3 = new Student("小王", 18, 103);
        // 創(chuàng)建集合
        // 方式二: 使用構(gòu)造器自帶的比較器對(duì)象
        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表達(dá)式簡(jiǎn)化代碼

public class SetDemo {
    public static void main(String[] args) {
        // 創(chuàng)建學(xué)生對(duì)象
        Student stu1 = new Student("小明", 18, 101);
        Student stu2 = new Student("小趙", 18, 102);
        Student stu3 = new Student("小王", 18, 103);
        // 創(chuàng)建集合
        // 方式二: 使用構(gòu)造器自帶的比較器對(duì)象
        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)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: