Java中的TreeSet集合解析
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)掛掉問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-09-09SpringBoot中使用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-03Spring 應(yīng)用上下文獲取 Bean 的常用姿勢實(shí)例總結(jié)
這篇文章主要介紹了Spring 應(yīng)用上下文獲取 Bean,結(jié)合實(shí)例形式總結(jié)分析了Spring 應(yīng)用上下文獲取 Bean的實(shí)現(xiàn)方法與操作注意事項(xiàng),需要的朋友可以參考下2020-05-05Spring解決循環(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前端存token后端獲取token代碼實(shí)例(Spring?Boot)
Token其實(shí)就是訪問資源的憑證,一般是用戶通過用戶名和密碼登錄成功之后,服務(wù)器將登陸憑證做數(shù)字簽名,加密之后得到的字符串作為token,這篇文章主要給大家介紹了關(guān)于前端存token,Spring?Boot后端獲取token的相關(guān)資料,需要的朋友可以參考下2024-07-07去掉 IDEA 中 mybatis配置文件的局部背景顏色(圖解)
這篇文章通過圖文并茂的形式給大家介紹了去掉IntelliJ IDEA 中 mybatis配置文件的局部背景顏色及mybatis 對(duì)應(yīng)的 xml 文件警告的方法圖解,需要的朋友可以參考下2018-09-09Java面試Logback打印日志如何獲取當(dāng)前方法名稱題解
這篇文章主要為大家介紹了Java面試Logback打印日志如何獲取當(dāng)前方法名稱題解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-11-11