TreeSet是非同步的,線程不安全的,需要的朋友可以參考下" />

欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java中的TreeSet集合解析

 更新時(shí)間:2023年09月15日 10:51:31   作者:姚舜禹_12140  
這篇文章主要介紹了Java中的TreeSet集合解析,  TreeSet是一個(gè)有序的集合,基于TreeMap實(shí)現(xiàn),支持兩種排序方式:自然排序和定制排序,
TreeSet是非同步的,線程不安全的,需要的朋友可以參考下

一、TreeSet介紹

TreeSet是一個(gè)有序的集合,基于TreeMap實(shí)現(xiàn),支持兩種排序方式:自然排序和定制排序。 TreeSet是非同步的,線程不安全的。

二、源碼分析

1、TreeSet實(shí)現(xiàn)的接口

如下圖:

觀察上圖:

  • AbstractSet類:該類提供了Set接口的骨架實(shí)現(xiàn),通過擴(kuò)展此類來實(shí)現(xiàn)集合的過程與通過擴(kuò)展AbstractCollection實(shí)現(xiàn)集合的過程相同,除了此類的子類中的所有方法和構(gòu)造函數(shù)都必須遵守由Set接口施加的附加約束(例如,添加方法不能允許將一個(gè)對(duì)象的多個(gè)實(shí)例添加到集合中)。
  • Navigable接口:支持一系列的導(dǎo)航方法。比如查找與指定目標(biāo)最匹配項(xiàng)。
  • Serializable接口:主要用于序列化,即:能夠?qū)?duì)象寫入磁盤。與之對(duì)應(yīng)的還有反序列化操作,就是將對(duì)象從磁盤中讀取出來。因此如果要進(jìn)行序列化和反序列化,ArrayList的實(shí)例對(duì)象就必須實(shí)現(xiàn)這個(gè)接口,否則在實(shí)例化的時(shí)候程序會(huì)報(bào)錯(cuò)(java.io.NotSerializableException)。
  • Cloneable接口:實(shí)現(xiàn)Cloneable接口的類能夠調(diào)用clone方法,如果沒有實(shí)現(xiàn)Cloneable接口就調(diào)用方法,就會(huì)拋出異常(java.lang.CloneNotSupportedException)。

2、TreeSet中的變量

  • private transient NavigableMap<E,Object> m:存放元素的集合
  • private static final Object PRESENT = new Object():常量,構(gòu)造一個(gè)虛擬的對(duì)象PRESENT,默認(rèn)為map的value值(HashSet中只需要用到鍵,而HashMap是key-value鍵值對(duì),使用PRESENT作為value的默認(rèn)填充值,解決差異問題)

3、TreeSet的構(gòu)造方法

(1)同包下的構(gòu)造方法

    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }

(2)無參構(gòu)造方法

    public TreeSet() {
        this(new TreeMap<E,Object>());
    }

(3)帶比較器的構(gòu)造方法

    public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));
    }

(4)帶集合參數(shù)的構(gòu)造方法

    public TreeSet(Collection<? extends E> c) {
        this();
        addAll(c);
    }

(5)帶SortMap的構(gòu)造方法

    public TreeSet(SortedSet<E> s) {
        this(s.comparator());
        addAll(s);
    }

通過上面的構(gòu)造方法,可以看出TreeSet的底層是用TreeMap實(shí)現(xiàn)的。在構(gòu)造方法中會(huì)創(chuàng)建一個(gè)TreeMap實(shí)例,用于存放元素,另外TreeSet是有序的,也提供了制定比較器的構(gòu)造函數(shù),如果沒有提供比較器,則采用key的自然順序進(jìn)行比較大小,如果指定的比較器,則采用指定的比較器,進(jìn)行key值大小的比較。

4、常用方法

//遍歷方法,返回m.keyset集合
    public Iterator<E> iterator() {
        return m.navigableKeySet().iterator();
    }
    //逆序排序的迭代器
    public Iterator<E> descendingIterator() {
        return m.descendingKeySet().iterator();
    }
    /**
     * @since 1.6
     */
    public NavigableSet<E> descendingSet() {
        return new TreeSet<>(m.descendingMap());
    }
    //返回 m 包含的鍵值對(duì)的數(shù)量
    public int size() {
        return m.size();
    }
    //是否為空
    public boolean isEmpty() {
        return m.isEmpty();
    }
    //是否包含指定的key
    public boolean contains(Object o) {
        return m.containsKey(o);
    }
    //添加元素,調(diào)用m.put方法實(shí)現(xiàn)
    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }
    //刪除方法,調(diào)用m.remove()方法實(shí)現(xiàn)
    public boolean remove(Object o) {
        return m.remove(o)==PRESENT;
    }
    //清除集合
    public void clear() {
        m.clear();
    }
    //將一個(gè)集合中的所有元素添加到TreeSet中
    public  boolean addAll(Collection<? extends E> c) {
        // Use linear-time version if applicable
        if (m.size()==0 && c.size() > 0 &&
            c instanceof SortedSet &&
            m instanceof TreeMap) {
            SortedSet<? extends E> set = (SortedSet<? extends E>) c;
            TreeMap<E,Object> map = (TreeMap<E, Object>) m;
            Comparator<? super E> cc = (Comparator<? super E>) set.comparator();
            Comparator<? super E> mc = map.comparator();
            if (cc==mc || (cc != null && cc.equals(mc))) {
                map.addAllForTreeSet(set, PRESENT);
                return true;
            }
        }
        return super.addAll(c);
    }
    //返回子集合,通過 m.subMap()方法實(shí)現(xiàn)
    public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                                  E toElement,   boolean toInclusive) {
        return new TreeSet<>(m.subMap(fromElement, fromInclusive,
                                       toElement,   toInclusive));
    }
    //返回set的頭部
    public NavigableSet<E> headSet(E toElement, boolean inclusive) {
        return new TreeSet<>(m.headMap(toElement, inclusive));
    }
    //返回尾部
    public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
        return new TreeSet<>(m.tailMap(fromElement, inclusive));
    }
    //返回子Set
    public SortedSet<E> subSet(E fromElement, E toElement) {
        return subSet(fromElement, true, toElement, false);
    }
    //返回set的頭部
    public SortedSet<E> headSet(E toElement) {
        return headSet(toElement, false);
    }
    //返回set的尾部
    public SortedSet<E> tailSet(E fromElement) {
        return tailSet(fromElement, true);
    }
    //返回m使用的比較器
    public Comparator<? super E> comparator() {
        return m.comparator();
    }
    //返回第一個(gè)元素
    public E first() {
        return m.firstKey();
    }
    //返回最后一個(gè)元素
    public E last() {
        return m.lastKey();
    }
    //返回set中小于e的最大的元素
    public E lower(E e) {
        return m.lowerKey(e);
    }
    //返回set中小于/等于e的最大元素
    public E floor(E e) {
        return m.floorKey(e);
    }
    //返回set中大于/等于e的最大元素
    public E ceiling(E e) {
        return m.ceilingKey(e);
    }
    //返回set中大于e的最小元素
    public E higher(E e) {
        return m.higherKey(e);
    }
    //獲取TreeSet中第一個(gè)元素,并從Set中刪除該元素
    public E pollFirst() {
        Map.Entry<E,?> e = m.pollFirstEntry();
        return (e == null) ? null : e.getKey();
    }
    //獲取TreeSet中最后一個(gè)元素,并從Set中刪除該元素
    public E pollLast() {
        Map.Entry<E,?> e = m.pollLastEntry();
        return (e == null) ? null : e.getKey();
    }
    //克隆方法
    public Object clone() {
        TreeSet<E> clone = null;
        try {
            clone = (TreeSet<E>) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError();
        }
        clone.m = new TreeMap<>(m);
        return clone;
    }
    //將對(duì)象寫入到輸出流中。
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // Write out any hidden stuff
        s.defaultWriteObject();
        // Write out Comparator
        s.writeObject(m.comparator());
        // Write out size
        s.writeInt(m.size());
        // Write out all elements in the proper order.
        for (E e : m.keySet())
            s.writeObject(e);
    }
    //從輸入流中讀取對(duì)象的信息
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in any hidden stuff
        s.defaultReadObject();
        // Read in Comparator
        Comparator<? super E> c = (Comparator<? super E>) s.readObject();
        // Create backing TreeMap
        TreeMap<E,Object> tm;
        if (c==null)
            tm = new TreeMap<>();
        else
            tm = new TreeMap<>(c);
        m = tm;
        // Read in size
        int size = s.readInt();
        tm.readTreeSet(size, s, PRESENT);
    }

5、TreeSet的兩種排序方式

(1)實(shí)現(xiàn)Comparator接口,重寫compare方法

 
import java.util.*;
class Student{
    private int id;
    private String name;
    private int age;
    public Student(int id, String name, int age) {
        this.id = id;
        this.name = name;
        this.age = age;
    }
    public int getId() {
        return id;
    }
    public void setId(int id) {
        this.id = id;
    }
    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{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}
class MyComparator implements Comparator{
    @Override
    public int compare(Object o1, Object o2) {
        Student s1 = (Student) o1;
        Student s2 = (Student) o2;
        return s1.getAge() - s2.getAge();
    }
}
public class Main {
    public static void main(String[] args) {
        TreeSet treeSet = new TreeSet(new MyComparator());
        treeSet.add(new Student(1, "tom", 23));
        treeSet.add(new Student(2, "Jerry", 20));
        treeSet.add(new Student(3, "Jack", 17));
        treeSet.add(new Student(4, "Marry", 54));
        treeSet.add(new Student(5, "Baby", 8));
        Iterator iterator = treeSet.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }
}

(2)實(shí)現(xiàn)Comparable接口,覆寫compareTo()方法

import java.util.*;
class Student implements Comparable{
    private int id;
    private String name;
    private int age;
    public Student(int id, String name, int age) {
        this.id = id;
        this.name = name;
        this.age = age;
    }
    public int getId() {
        return id;
    }
    public void setId(int id) {
        this.id = id;
    }
    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{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
    @Override
    public int compareTo(Object o) {
        if(!(o instanceof Student)){
            throw new RuntimeException("對(duì)象有問題");
        }
        Student s = (Student) o;
        if(this.age > s.age){
            return -1;
        }else{
            return 1;
        }
    }
}
public class Main {
    public static void main(String[] args) {
        TreeSet treeSet = new TreeSet();
        treeSet.add(new Student(1, "tom", 23));
        treeSet.add(new Student(2, "Jerry", 20));
        treeSet.add(new Student(3, "Jack", 17));
        treeSet.add(new Student(4, "Marry", 54));
        treeSet.add(new Student(5, "Baby", 8));
        Iterator iterator = treeSet.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }
}

三、總結(jié)

1、TreeSet總結(jié)

  • TreeSet實(shí)際上是TreeMap實(shí)現(xiàn)的,所以底層結(jié)構(gòu)也是紅黑樹。TreeSet不需要重寫hashCode()和euqals()方法,因?yàn)樗ブ厥且揽勘容^器來去重,因?yàn)榻Y(jié)構(gòu)是紅黑樹,所以每次插入都會(huì)遍歷比較來尋找節(jié)點(diǎn)插入位置,如果發(fā)現(xiàn)某個(gè)節(jié)點(diǎn)的值是一樣的那就會(huì)直接覆蓋。
  • 當(dāng)我們構(gòu)造TreeSet時(shí);若使用不帶參數(shù)的構(gòu)造函數(shù),則TreeSet的使用自然比較器;若用戶需要使用自定義的比較器,則需要使用帶比較器的參數(shù)。
  • TreeSet是非線程安全的。
  • TreeSet實(shí)現(xiàn)java.io.Serializable的方式。當(dāng)寫入到輸出流時(shí),依次寫入“比較器、容量、全部元素”;當(dāng)讀出輸入流時(shí),再依次讀取。 

2、HashSet、LinkedHashSet 以及 TreeSet。

(1)HashSet

  • 不能保證元素的排列順序,順序有可能發(fā)生變化
  • 不是同步的,非線程安全
  • 集合元素可以是null,但只能放入一個(gè)null
  • 當(dāng)向HashSet結(jié)合中存入一個(gè)元素時(shí),HashSet會(huì)調(diào)用該對(duì)象的hashCode()方法來得到該對(duì)象的hashCode值,然后根據(jù) hashCode值來決定該對(duì)象在HashSet中存儲(chǔ)位置。
  • 簡單的說,HashSet集合判斷兩個(gè)元素相等的標(biāo)準(zhǔn)是兩個(gè)對(duì)象通過equals方法比較相等,并且兩個(gè)對(duì)象的hashCode()方法返回值相等
  • 注意,如果要把一個(gè)對(duì)象放入HashSet中,重寫該對(duì)象對(duì)應(yīng)類的equals方法,也應(yīng)該重寫其hashCode()方法。其規(guī)則是如果兩個(gè)對(duì)象通過equals方法比較返回true時(shí),其hashCode也應(yīng)該相同。另外,對(duì)象中用作equals比較標(biāo)準(zhǔn)的屬性,都應(yīng)該用來計(jì)算hashCode的值。

(2)LinkedHashSet

LinkedHashSet集合同樣是根據(jù)元素的hashCode值來決定元素的存儲(chǔ)位置,但是它同時(shí)使用鏈表維護(hù)元素的次序。這樣使得元素看起 來像是以插入順序保存的,也就是說,當(dāng)遍歷該集合時(shí)候,LinkedHashSet將會(huì)以元素的添加順序訪問集合的元素。

  • LinkedHashSet中不能有相同元素,可以有一個(gè)Null元素,元素嚴(yán)格按照放入的順序排列。
  • LinkedHashSet底層數(shù)據(jù)結(jié)構(gòu)由哈希表和鏈表組成,鏈表保證了元素的有序即存儲(chǔ)和取出一致,哈希表保證了元素的唯一性。
  • LinkedHashSet添加、刪除操作時(shí)間復(fù)雜度都是O(1)。

(3)TreeSet

  • TreeSet支持兩種排序方式,自然排序 和定制排序,其中自然排序?yàn)槟J(rèn)的排序方式。向TreeSet中加入的應(yīng)該是同一個(gè)類的對(duì)象。
  • TreeSet判斷兩個(gè)對(duì)象不相等的方式是兩個(gè)對(duì)象通過equals方法返回false,或者通過CompareTo方法比較沒有返回0
  • TreeSet是中不能有相同元素,不可以有Null元素,根據(jù)元素的自然順序進(jìn)行排序。
  • TreeSet底層的數(shù)據(jù)結(jié)構(gòu)是紅黑樹(一種自平衡二叉查找樹)
  • 添加、刪除操作時(shí)間復(fù)雜度都是O(log(n))

(4)使用場景

HashSet是基于Hash算法實(shí)現(xiàn)的,其性能通常都優(yōu)于TreeSet。我們通常都應(yīng)該使用HashSet,在我們需要排序的功能時(shí),我們才使用TreeSet。

(5)對(duì)象的加入過程

TreeSet集合對(duì)象的加入過程:

TreeSet的底層是通過二叉樹來完成存儲(chǔ)的,無序的集合 當(dāng)我們將一個(gè)對(duì)象加入treeset中,treeset會(huì)將第一個(gè)對(duì)象作為根對(duì)象,然后調(diào)用對(duì)象的compareTo方法拿第二個(gè)對(duì)象和第一個(gè)比較,當(dāng)返回值等于0時(shí),說明2個(gè)對(duì)象內(nèi)容相等,treeset就不把第二個(gè)對(duì)象加入集合。返回>1時(shí),說明第二個(gè)對(duì)象大于第一個(gè)對(duì)象,將第二個(gè)對(duì)象放在右邊,返回-1時(shí),則將第二個(gè)對(duì)象放在左邊,依次類推 。

HashSet集合對(duì)象的加入過程:

hashset底層是hash值的地址,它里面存的對(duì)象是無序的。 第一個(gè)對(duì)象進(jìn)入集合時(shí),hashset會(huì)調(diào)用object類的hashcode根據(jù)對(duì)象在堆內(nèi)存里的地址調(diào)用對(duì)象重寫的hashcode計(jì)算出一個(gè)hash值,然后第一個(gè)對(duì)象就進(jìn)入hashset集合中的任意一個(gè)位置。 第二個(gè)對(duì)象開始進(jìn)入集合,hashset先根據(jù)第二個(gè)對(duì)象在堆內(nèi)存的地址調(diào)用對(duì)象的計(jì)算出一個(gè)hash值,如果第二個(gè)對(duì)象和第一個(gè)對(duì)象在堆內(nèi)存里的地址是相同的,那么得到的hash值也是相同的,直接返回true,hash得到true后就不把第二個(gè)元素加入集合(這段是hash源碼程序中的操作)。如果第二個(gè)對(duì)象和第一個(gè)對(duì)象在堆內(nèi)存里地址是不同的,這時(shí)hashset類會(huì)先調(diào)用自己的方法遍歷集合中的元素,當(dāng)遍歷到某個(gè)元素時(shí),調(diào)用對(duì)象的equals方法,如果相等,返回true,則說明這兩個(gè)對(duì)象的內(nèi)容是相同的,hashset得到true后不會(huì)把第二個(gè)對(duì)象加入集合。

到此這篇關(guān)于Java中的TreeSet集合解析的文章就介紹到這了,更多相關(guān)TreeSet集合內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • 解決spring cloud服務(wù)啟動(dòng)之后回到命令行會(huì)自動(dòng)掛掉問題

    解決spring cloud服務(wù)啟動(dòng)之后回到命令行會(huì)自動(dòng)掛掉問題

    這篇文章主要介紹了解決spring cloud服務(wù)啟動(dòng)之后回到命令行會(huì)自動(dòng)掛掉問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
    2020-09-09
  • SpringBoot中使用MyBatis-Plus實(shí)現(xiàn)分頁接口的詳細(xì)教程

    SpringBoot中使用MyBatis-Plus實(shí)現(xiàn)分頁接口的詳細(xì)教程

    MyBatis-Plus是一個(gè)MyBatis的增強(qiáng)工具,在MyBatis的基礎(chǔ)上只做增強(qiáng)不做改變,為簡化開發(fā)、提高效率而生,在SpringBoot項(xiàng)目中使用MyBatis-Plus可以大大簡化分頁邏輯的編寫,本文將介紹如何在 SpringBoot項(xiàng)目中使用MyBatis-Plus實(shí)現(xiàn)分頁接口
    2024-03-03
  • Spring 應(yīng)用上下文獲取 Bean 的常用姿勢實(shí)例總結(jié)

    Spring 應(yīng)用上下文獲取 Bean 的常用姿勢實(shí)例總結(jié)

    這篇文章主要介紹了Spring 應(yīng)用上下文獲取 Bean,結(jié)合實(shí)例形式總結(jié)分析了Spring 應(yīng)用上下文獲取 Bean的實(shí)現(xiàn)方法與操作注意事項(xiàng),需要的朋友可以參考下
    2020-05-05
  • Spring解決循環(huán)依賴問題的三種方法小結(jié)

    Spring解決循環(huán)依賴問題的三種方法小結(jié)

    在 Spring 中,循環(huán)依賴問題指的是兩個(gè)或多個(gè) bean 之間相互依賴形成的閉環(huán),具體而言,當(dāng) bean A 依賴于 bean B,同時(shí) bean B 也依賴于 bean A,就形成了循環(huán)依賴,本文就給大家介紹了Spring解決循環(huán)依賴問題的三種方法,需要的朋友可以參考下
    2023-09-09
  • Java8新增的重復(fù)注解功能示例

    Java8新增的重復(fù)注解功能示例

    這篇文章主要介紹了Java8新增的重復(fù)注解功能,結(jié)合實(shí)例形式分析了java8重復(fù)注解的功能、定義、使用方法及相關(guān)操作注意事項(xiàng),需要的朋友可以參考下
    2019-10-10
  • 前端存token后端獲取token代碼實(shí)例(Spring?Boot)

    前端存token后端獲取token代碼實(shí)例(Spring?Boot)

    Token其實(shí)就是訪問資源的憑證,一般是用戶通過用戶名和密碼登錄成功之后,服務(wù)器將登陸憑證做數(shù)字簽名,加密之后得到的字符串作為token,這篇文章主要給大家介紹了關(guān)于前端存token,Spring?Boot后端獲取token的相關(guān)資料,需要的朋友可以參考下
    2024-07-07
  • 去掉 IDEA 中 mybatis配置文件的局部背景顏色(圖解)

    去掉 IDEA 中 mybatis配置文件的局部背景顏色(圖解)

    這篇文章通過圖文并茂的形式給大家介紹了去掉IntelliJ IDEA 中 mybatis配置文件的局部背景顏色及mybatis 對(duì)應(yīng)的 xml 文件警告的方法圖解,需要的朋友可以參考下
    2018-09-09
  • 基于JDK動(dòng)態(tài)代理原理解析

    基于JDK動(dòng)態(tài)代理原理解析

    這篇文章主要介紹了基于JDK動(dòng)態(tài)代理原理解析,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2023-05-05
  • Java面試Logback打印日志如何獲取當(dāng)前方法名稱題解

    Java面試Logback打印日志如何獲取當(dāng)前方法名稱題解

    這篇文章主要為大家介紹了Java面試Logback打印日志如何獲取當(dāng)前方法名稱題解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2023-11-11
  • Spring通過Java配置集成Tomcat的方法

    Spring通過Java配置集成Tomcat的方法

    這篇文章主要介紹了Spring通過Java配置集成Tomcat的方法,本文通過實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2021-04-04

最新評(píng)論