Java中的TreeSet集合解析
TreeSet是非同步的,線程不安全的,需要的朋友可以參考下
一、TreeSet介紹
TreeSet是一個有序的集合,基于TreeMap實現(xiàn),支持兩種排序方式:自然排序和定制排序。 TreeSet是非同步的,線程不安全的。
二、源碼分析
1、TreeSet實現(xiàn)的接口
如下圖:
觀察上圖:
- AbstractSet類:該類提供了Set接口的骨架實現(xiàn),通過擴展此類來實現(xiàn)集合的過程與通過擴展AbstractCollection實現(xiàn)集合的過程相同,除了此類的子類中的所有方法和構造函數(shù)都必須遵守由Set接口施加的附加約束(例如,添加方法不能允許將一個對象的多個實例添加到集合中)。
- Navigable接口:支持一系列的導航方法。比如查找與指定目標最匹配項。
- Serializable接口:主要用于序列化,即:能夠將對象寫入磁盤。與之對應的還有反序列化操作,就是將對象從磁盤中讀取出來。因此如果要進行序列化和反序列化,ArrayList的實例對象就必須實現(xiàn)這個接口,否則在實例化的時候程序會報錯(java.io.NotSerializableException)。
- Cloneable接口:實現(xiàn)Cloneable接口的類能夠調用clone方法,如果沒有實現(xiàn)Cloneable接口就調用方法,就會拋出異常(java.lang.CloneNotSupportedException)。
2、TreeSet中的變量
- private transient NavigableMap<E,Object> m:存放元素的集合
- private static final Object PRESENT = new Object():常量,構造一個虛擬的對象PRESENT,默認為map的value值(HashSet中只需要用到鍵,而HashMap是key-value鍵值對,使用PRESENT作為value的默認填充值,解決差異問題)
3、TreeSet的構造方法
(1)同包下的構造方法
TreeSet(NavigableMap<E,Object> m) { this.m = m; }
(2)無參構造方法
public TreeSet() { this(new TreeMap<E,Object>()); }
(3)帶比較器的構造方法
public TreeSet(Comparator<? super E> comparator) { this(new TreeMap<>(comparator)); }
(4)帶集合參數(shù)的構造方法
public TreeSet(Collection<? extends E> c) { this(); addAll(c); }
(5)帶SortMap的構造方法
public TreeSet(SortedSet<E> s) { this(s.comparator()); addAll(s); }
通過上面的構造方法,可以看出TreeSet的底層是用TreeMap實現(xiàn)的。在構造方法中會創(chuàng)建一個TreeMap實例,用于存放元素,另外TreeSet是有序的,也提供了制定比較器的構造函數(shù),如果沒有提供比較器,則采用key的自然順序進行比較大小,如果指定的比較器,則采用指定的比較器,進行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 包含的鍵值對的數(shù)量 public int size() { return m.size(); } //是否為空 public boolean isEmpty() { return m.isEmpty(); } //是否包含指定的key public boolean contains(Object o) { return m.containsKey(o); } //添加元素,調用m.put方法實現(xiàn) public boolean add(E e) { return m.put(e, PRESENT)==null; } //刪除方法,調用m.remove()方法實現(xiàn) public boolean remove(Object o) { return m.remove(o)==PRESENT; } //清除集合 public void clear() { m.clear(); } //將一個集合中的所有元素添加到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()方法實現(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(); } //返回第一個元素 public E first() { return m.firstKey(); } //返回最后一個元素 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中第一個元素,并從Set中刪除該元素 public E pollFirst() { Map.Entry<E,?> e = m.pollFirstEntry(); return (e == null) ? null : e.getKey(); } //獲取TreeSet中最后一個元素,并從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; } //將對象寫入到輸出流中。 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); } //從輸入流中讀取對象的信息 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)實現(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)實現(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("對象有問題"); } 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()); } } }
三、總結
1、TreeSet總結
- TreeSet實際上是TreeMap實現(xiàn)的,所以底層結構也是紅黑樹。TreeSet不需要重寫hashCode()和euqals()方法,因為它去重是依靠比較器來去重,因為結構是紅黑樹,所以每次插入都會遍歷比較來尋找節(jié)點插入位置,如果發(fā)現(xiàn)某個節(jié)點的值是一樣的那就會直接覆蓋。
- 當我們構造TreeSet時;若使用不帶參數(shù)的構造函數(shù),則TreeSet的使用自然比較器;若用戶需要使用自定義的比較器,則需要使用帶比較器的參數(shù)。
- TreeSet是非線程安全的。
- TreeSet實現(xiàn)java.io.Serializable的方式。當寫入到輸出流時,依次寫入“比較器、容量、全部元素”;當讀出輸入流時,再依次讀取。
2、HashSet、LinkedHashSet 以及 TreeSet。
(1)HashSet
- 不能保證元素的排列順序,順序有可能發(fā)生變化
- 不是同步的,非線程安全
- 集合元素可以是null,但只能放入一個null
- 當向HashSet結合中存入一個元素時,HashSet會調用該對象的hashCode()方法來得到該對象的hashCode值,然后根據(jù) hashCode值來決定該對象在HashSet中存儲位置。
- 簡單的說,HashSet集合判斷兩個元素相等的標準是兩個對象通過equals方法比較相等,并且兩個對象的hashCode()方法返回值相等
- 注意,如果要把一個對象放入HashSet中,重寫該對象對應類的equals方法,也應該重寫其hashCode()方法。其規(guī)則是如果兩個對象通過equals方法比較返回true時,其hashCode也應該相同。另外,對象中用作equals比較標準的屬性,都應該用來計算hashCode的值。
(2)LinkedHashSet
LinkedHashSet集合同樣是根據(jù)元素的hashCode值來決定元素的存儲位置,但是它同時使用鏈表維護元素的次序。這樣使得元素看起 來像是以插入順序保存的,也就是說,當遍歷該集合時候,LinkedHashSet將會以元素的添加順序訪問集合的元素。
- LinkedHashSet中不能有相同元素,可以有一個Null元素,元素嚴格按照放入的順序排列。
- LinkedHashSet底層數(shù)據(jù)結構由哈希表和鏈表組成,鏈表保證了元素的有序即存儲和取出一致,哈希表保證了元素的唯一性。
- LinkedHashSet添加、刪除操作時間復雜度都是O(1)。
(3)TreeSet
- TreeSet支持兩種排序方式,自然排序 和定制排序,其中自然排序為默認的排序方式。向TreeSet中加入的應該是同一個類的對象。
- TreeSet判斷兩個對象不相等的方式是兩個對象通過equals方法返回false,或者通過CompareTo方法比較沒有返回0
- TreeSet是中不能有相同元素,不可以有Null元素,根據(jù)元素的自然順序進行排序。
- TreeSet底層的數(shù)據(jù)結構是紅黑樹(一種自平衡二叉查找樹)
- 添加、刪除操作時間復雜度都是O(log(n))
(4)使用場景
HashSet是基于Hash算法實現(xiàn)的,其性能通常都優(yōu)于TreeSet。我們通常都應該使用HashSet,在我們需要排序的功能時,我們才使用TreeSet。
(5)對象的加入過程
TreeSet集合對象的加入過程:
TreeSet的底層是通過二叉樹來完成存儲的,無序的集合 當我們將一個對象加入treeset中,treeset會將第一個對象作為根對象,然后調用對象的compareTo方法拿第二個對象和第一個比較,當返回值等于0時,說明2個對象內容相等,treeset就不把第二個對象加入集合。返回>1時,說明第二個對象大于第一個對象,將第二個對象放在右邊,返回-1時,則將第二個對象放在左邊,依次類推 。
HashSet集合對象的加入過程:
hashset底層是hash值的地址,它里面存的對象是無序的。 第一個對象進入集合時,hashset會調用object類的hashcode根據(jù)對象在堆內存里的地址調用對象重寫的hashcode計算出一個hash值,然后第一個對象就進入hashset集合中的任意一個位置。 第二個對象開始進入集合,hashset先根據(jù)第二個對象在堆內存的地址調用對象的計算出一個hash值,如果第二個對象和第一個對象在堆內存里的地址是相同的,那么得到的hash值也是相同的,直接返回true,hash得到true后就不把第二個元素加入集合(這段是hash源碼程序中的操作)。如果第二個對象和第一個對象在堆內存里地址是不同的,這時hashset類會先調用自己的方法遍歷集合中的元素,當遍歷到某個元素時,調用對象的equals方法,如果相等,返回true,則說明這兩個對象的內容是相同的,hashset得到true后不會把第二個對象加入集合。
到此這篇關于Java中的TreeSet集合解析的文章就介紹到這了,更多相關TreeSet集合內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
解決spring cloud服務啟動之后回到命令行會自動掛掉問題
這篇文章主要介紹了解決spring cloud服務啟動之后回到命令行會自動掛掉問題,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2020-09-09SpringBoot中使用MyBatis-Plus實現(xiàn)分頁接口的詳細教程
MyBatis-Plus是一個MyBatis的增強工具,在MyBatis的基礎上只做增強不做改變,為簡化開發(fā)、提高效率而生,在SpringBoot項目中使用MyBatis-Plus可以大大簡化分頁邏輯的編寫,本文將介紹如何在 SpringBoot項目中使用MyBatis-Plus實現(xiàn)分頁接口2024-03-03前端存token后端獲取token代碼實例(Spring?Boot)
Token其實就是訪問資源的憑證,一般是用戶通過用戶名和密碼登錄成功之后,服務器將登陸憑證做數(shù)字簽名,加密之后得到的字符串作為token,這篇文章主要給大家介紹了關于前端存token,Spring?Boot后端獲取token的相關資料,需要的朋友可以參考下2024-07-07去掉 IDEA 中 mybatis配置文件的局部背景顏色(圖解)
這篇文章通過圖文并茂的形式給大家介紹了去掉IntelliJ IDEA 中 mybatis配置文件的局部背景顏色及mybatis 對應的 xml 文件警告的方法圖解,需要的朋友可以參考下2018-09-09