Java集合之Set、HashSet、LinkedHashSet和TreeSet深度解析
Set
List是有序集合的根接口, Set是無序集合的根接口,無序也就意味著元素不重復(fù) 。
更嚴(yán)格地說,Set集合不包含一對元素e1和e2 ,使得eequals(e2) ,并且最多一個空元素。
使用Set存儲的特點與List相反:元素?zé)o序、不可重復(fù)。
常用的實現(xiàn)方式:HashSet、LinkedHashSet和TreeSet。
具體實現(xiàn) | 優(yōu)點 | 缺點 |
HashSet | 底層數(shù)據(jù)結(jié)構(gòu)是哈希表,可以存儲Null元素,效率高 | 線程不安全,需要重寫hashCode()和equals()來保證元素唯一性 |
LinkedHashSet | 底層數(shù)據(jù)結(jié)構(gòu)是鏈表和哈希表(鏈表保證了元素的順序與存儲順序一致,哈希表保證了元素的唯一性),效率高 | 線程不安全 |
TreeSet | 底層數(shù)據(jù)結(jié)構(gòu)是二叉樹,元素唯一且已經(jīng)排好序 | 需要重寫hashCode和equals()來保證元素唯一性 |
當(dāng)向HashSet結(jié)合中存入一個元素時,HashSet會調(diào)用該對象的hashCode()方法來得到該對象的hashCode值,然后根據(jù) hashCode值來決定該對象在HashSet中存儲位置。
簡單的說,HashSet集合判斷兩個元素相等的標(biāo)準(zhǔn)是兩個對象通過equals方法比較相等,并且兩個對象的hashCode()方法返回值也相等。
LinkedHashSet集合同樣是根據(jù)元素的hashCode值來決定元素的存儲位置,但是它同時使用鏈表維護(hù)元素的次序。
這樣使得元素看起來像是以插入順序保存的,也就是說,當(dāng)遍歷該集合時候,LinkedHashSet將會以元素的添加順序訪問集合的元素。
在使用Set存儲數(shù)據(jù)時,為保障元素唯一性,常常要重寫hashCode。
重寫hashCode方法時,盡量遵循以下原則:
- 相同的對象返回相同的hashCode值
- 不同的對象返回不同的hashCode值,否則,就會增加沖突的概率
- 盡量的讓hashCode值散列開(用異或運算可使結(jié)果的范圍更廣)
- HashSet
- HashSet中沒有重復(fù)元素,底層由HashMap實現(xiàn),不保證元素的順序(此處的沒有順序是指:元素插入的順序與輸出的順序不一致),HashSet允許使用Null元素,HashSet是非同步的。
- LinkedHashSet
- LinkedHashSet繼承自HashSet,其底層是基于LinkedHashMap來實現(xiàn)的,有序,非同步。
- LinkedHashSet在迭代訪問Set中的全部元素時,性能比HashSet好,但是插入時性能稍微遜色于HashSet。
- TreeSet
- TreeSet底層是基于TreeMap實現(xiàn)的,所以元素有序。TreeSet支持兩種排序方式,自然排序和定制排序,其中自然排序為默認(rèn)的排序方式。當(dāng)我們構(gòu)造TreeSet時,若使用不帶參數(shù)的構(gòu)造函數(shù),則TreeSet的使用
- 自然比較器;若用戶需要使用自定義的比較器,則需要使用帶比較器的參數(shù)。
- TreeSet是線程不安全的。
- 自然排序要求元素必須實現(xiàn)Compareable接口,并重寫里面的compareTo()方法,元素通過比較返回的int值來判斷排序序列,返回0說明兩個對象相同。
- 比較器排序需要在TreeSet初始化是時候傳入一個實現(xiàn)Comparator接口的比較器對象,或者采用匿名內(nèi)部類的方式new一個Comparator對象,重寫里面的compare()方法。
- TreeSet判斷兩個對象不相等的方式是兩個對象通過equals方法返回false,或者通過CompareTo方法比較沒有返回0。
- 在使用Set存儲元素時,元素雖然無放入順序,但Set的底層實現(xiàn)其實是Map,元素在Set中的位置是有該元素的HashCode決定的,所以其位置其實是固定的。
- TreeSet是SortedSet接口的唯一實現(xiàn)類,TreeSet可以確保集合元素處于排序狀態(tài)。TreeSet支持兩種排序方式,自然排序和定制排序,其中自然排序為默認(rèn)的排序方式。
至于具體使用哪種集合時,參考:
在List和Set兩個分支中,ArrayList和HashSet是對應(yīng)分支中適應(yīng)性最廣的,兩者再比較,ArrayList則適用性更廣一些。也就是說如果要確定用List,但不確定用哪種List,就可以使用ArrayList;如果確定用Set,但不確定用哪種Set,就可以使用HashSet。如果只知道用集合,就用ArrayList 。
HashSet
1 HashSet是什么
HashSet的繼承關(guān)系:
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable
HashSet是一個無序集合,其底層結(jié)構(gòu)是HashMap,簡單來說,HashSet是value是固定值( Object PRESENT = new Object() )的HashMap。
2 HashSet的特點
- HashSet的 底層實現(xiàn)是HashMap (HashSet的值存放于HashMap的key上,HashMap的value是一個統(tǒng)一的值)。
- HashSet中的 元素?zé)o序且不能重復(fù) (從插入HashSet元素的順序和遍歷HashSet的順序?qū)Ρ瓤梢钥闯觯?/li>
- HashSet是 線程不安全 的。如果要保證線程安全,其中一種方法是將其改造成線程安全的類,示例:
Set set = Collections.synchronizedSet(new HashSet(...));
- HashSet 允許存入null 。
3 HashSet如何檢查重復(fù)
當(dāng)你把對象加入HashSet時,HashSet會先計算對象的hashcode值來判斷對象加入的位置,同時也會與其他加入的對象的hashcode值作比較,如果沒有相同的hashcode,HashSet會假設(shè)對象沒有重復(fù)出現(xiàn)。但是如果發(fā)現(xiàn)有相同hashcode值的對象,這時會調(diào)用 equals() 方法來檢查hashcode相等的對象是否真的相同。如果兩者相同,HashSet就不會讓加入操作成功。
hashCode()與 equals()的相關(guān)規(guī)定
- 如果兩個對象相等,則hashcode一定也是相同的;
- 兩個對象相等,對兩個equals方法返回true;
- 兩個對象有相同的hashcode值,它們也不一定是相等的;
- 如果equals方法被覆蓋過,則hashCode方法也必須被覆蓋;
- hashCode()的默認(rèn)行為是對堆上的對象產(chǎn)生獨特值。如果沒有重寫hashCode(),則該 class的兩個對象無論如何都不會相等(即使這兩個對象指向相同的數(shù)據(jù))。
4 HashSet常用方法
- 構(gòu)造一個新的空HashSet,默認(rèn)初始容量為16,負(fù)載因子為0.75
public HashSet()
- 構(gòu)造一個新的空HashSet,指定初始容量,負(fù)載因子為0.75
public HashSet(int initialCapacity)
- 構(gòu)造一個新的空HashSet,指定初始容量和負(fù)載因子
public HashSet(int initialCapacity, float loadFactor)
- 添加元素
public boolean add(E e)
- 清空集合
public void clear()
- 如果此集合包含指定的元素,則返回 true
public boolean contains(Object o)
- 如果此集合不包含任何元素,則返回 true
public boolean isEmpty()
- 獲取此集合中元素的迭代器
public Iterator<E> iterator()
- 刪除元素
public boolean remove(Object o)
- 返回此集合中的元素數(shù)
public int size()
5 HashSet與HashMap的區(qū)別
HashMap | HashSet |
實現(xiàn)了Map接口 | 實現(xiàn)了Set接口 |
存儲鍵值對 | 僅存儲對象 |
調(diào)用put()向map中添加元素 | 調(diào)用 add()方法向Set中添加元素 |
HashMap使用鍵(Key)計算Hashcode | HashSet使用成員對象來計算hashcode值,對于兩個對象來說hashcode可能相同,所以equals()方法用來判斷對象的相等性,如果兩個對象不同的話,那么返回false |
HashMap相對于HashSet 較快,因為它是使用唯一的鍵獲取對象 | HashSet較HashMap來說比較慢 |
HashSet源碼
由于HashSet的底層實現(xiàn)HashMap,所以其方法的實現(xiàn)基本都是對HashMap的操作。
變量:
//HashSet集合中的內(nèi)容是通過HashMap數(shù)據(jù)結(jié)構(gòu)來存儲的 private transient HashMap<E,Object> map; //向HashSet中添加數(shù)據(jù),數(shù)據(jù)在上面的map結(jié)構(gòu)是作為key存在的,而value統(tǒng)一都是 //PRESENT,這樣做是因為Set只使用到了HashMap的key,所以此處定義一個靜態(tài)的常 //量Object類,來充當(dāng)HashMap的value private static final Object PRESENT = new Object();
1 構(gòu)造方法
- HashSet()
//直接 new 一個HashMap對象出來,采用無參的 HashMap 構(gòu)造函數(shù), //HashMap對象具有默認(rèn)初始容量(16)和加載因子(0.75) public HashSet() { map = new HashMap<>(); }
- HashSet(int initialCapacity, float loadFactor)
//指定初始容量和加載因子,創(chuàng)建HashMap實例 public HashSet(int initialCapacity, float loadFactor) { map = new HashMap<>(initialCapacity, loadFactor); }
- HashSet(int initialCapacity)
//指定初始容量,創(chuàng)建HashMap public HashSet(int initialCapacity) { map = new HashMap<>(initialCapacity); }
- HashSet(int initialCapacity, float loadFactor, boolean dummy)
//以指定的initialCapacity和loadFactor構(gòu)造一個新的空鏈接哈希集合。 //此構(gòu)造函數(shù)為包訪問權(quán)限,不對外公開,實際只是對LinkedHashSet的支持。 //實際底層會以指定的參數(shù)構(gòu)造一個空LinkedHashMap實例來實現(xiàn)。 HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor); }
加載因子指的是能存儲的元素占總的容量的比例。
在 HashMap 中,能夠存儲元素的數(shù)量就是: 總的容量*加載因子 。
每當(dāng)向HashSet新增元素時,如果HashMap集合中的元素大于前面公式計算的結(jié)果,就必須要進(jìn)行擴(kuò)容操作,從時間和空間考慮,加載因子一般都選默認(rèn)的0.75。
2 添加元素
當(dāng)把對象加入HashSet時,HashSet會先計算對象的 hashcode 值來判斷對象加入的位置,同時也會與其他加入的對象的hashcode值作比較,如果沒有相符的hashcode,HashSet會假設(shè)對象沒有重復(fù)出現(xiàn)。
但是如果發(fā)現(xiàn)有相同hashcode 值的對象,這時會調(diào)用 equals()方法來檢查hashcode相等的對象是否真的相同。如果兩者相同,則覆蓋舊元素。
//將 e 作為 key,PRESENT 作為 value 插入到 map 集合中,如果 e //不存在,則插入成功返回 true;如果存在,則返回false //本質(zhì)上是調(diào)用HashMap的put方法來實現(xiàn)的 public boolean add(E e) { return map.put(e, PRESENT)==null; }
3 刪除元素
//刪除成功返回 true,刪除的元素不存在會返回 false //本質(zhì)上是調(diào)用HashMap的remove方法來實現(xiàn)的 public boolean remove(Object o) { return map.remove(o)==PRESENT; }
4 查找元素
//調(diào)用 HashMap 的 containsKey(Object o) 方法,找到了返回 true,找不到返回 false //因為HashSet的本質(zhì)上是用HashMap來存儲元素的,HashSet的值是HashMap中的key,所以 //此處調(diào)用了HashMap的containsKey方法來判斷 public boolean contains(Object o) { return map.containsKey(o); }
5 清空集合/判斷是否為空/獲取HashSet元素個數(shù)
這幾個方法都是直接調(diào)用其底層實現(xiàn)HashMap的方法的,源碼:
//清空集合 public void clear() { map.clear(); } //判斷是否為空 public boolean isEmpty() { return map.isEmpty(); } //獲取集合元素個數(shù) public int size() { return map.size(); }
6 迭代器
//因為HashSet的本質(zhì)上是用HashMap來存儲元素的,HashSet的值是HashMap中的key,所以 //此處調(diào)用了HashMap的keySet方法來遍歷HashSet中的元素 public Iterator<E> iterator() { return map.keySet().iterator(); }
LinkedHashSet
1 LinkedHashSet是什么
LinkedHashSet是有序集合,其繼承關(guān)系:
public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable
LinkedHashSet底層是通過LinkedHashMap來實現(xiàn)的,LinkedHashMap其實也就是value是固定值的LinkedHashMap。
因此LinkedHashSet中的元素順序是可以保證 的,也就是說遍歷序和插入序是一致的。
2 LinkedHashSet的特點
- 底層是用LinkedHashMap來實現(xiàn)的。
- 線程不安全 。
- 元素有序,是按照插入的順序排序的。
- 最多只能存一個Null。
3 LinkedHashSet支持按元素訪問順序排序嗎
LinkedHashSet所有的構(gòu)造方法都是調(diào)用HashSet的同一個構(gòu)造方法:
HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor); }
然后,通過調(diào)用LinkedHashMap的構(gòu)造方法初始化Map:
public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false; }
可以看出:這里把a(bǔ)ccessOrder寫死為false。所以, LinkedHashSet是不支持按訪問順序?qū)υ嘏判虻模荒馨床迦腠樞蚺判?
。
4 LinkedHashSet常用方法
1、構(gòu)造一個具有默認(rèn)初始容量(16)和負(fù)載因子(0.75)的LinkedHashSet
public LinkedHashSet()
2、構(gòu)造一個具有指定初始容量和默認(rèn)負(fù)載因子(0.75)的LinkedHashSet
public HashSet(int initialCapacity)
3、構(gòu)造具有指定的初始容量和負(fù)載因子的LinkedHashSet
public HashSet(int initialCapacity, float loadFactor)
LinkedHashSet源碼
LinkedHashSet源碼很簡單,大都和其父類HashSet相同,此處只介紹其構(gòu)造方法。
1、LinkedHashSet(int initialCapacity, float loadFactor)
public LinkedHashSet(int initialCapacity, float loadFactor) { //調(diào)用其父類HashSet的構(gòu)造器,指定初始容量和增長因子,構(gòu)造一個LinkedHashMap super(initialCapacity, loadFactor, true); }
2、LinkedHashSet(int initialCapacity)
public LinkedHashSet(int initialCapacity) { //調(diào)用其父類HashSet的構(gòu)造器,指定初始容量,增長因子為0.75,構(gòu)造一個LinkedHashMap super(initialCapacity, .75f, true); }
3、public LinkedHashSet()
public LinkedHashSet() { //調(diào)用其父類HashSet的構(gòu)造器,初始容量為16,增長因子為0.75,構(gòu)造一個LinkedHashMap super(16, .75f, true); }
TreeSet
1 TreeSet是什么
TreeSet是一個有序集合,基于TreeMap實現(xiàn)。
TreeSet的繼承關(guān)系:
public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable
2 TreeSet特點
- TreeSet支持元素的自然排序和按照在創(chuàng)建時指定的Comparator比較器進(jìn)行排序。
- TreeSet()是使用二叉樹的原理對新 add()的對象按照指定的順序排序(升序、降序),每增加一個對象都會進(jìn)行排序,將對象插入的二叉樹指定的位置。
- TreeSet中要存儲自定義類的對象時, 自己定義的類必須實現(xiàn) Comparable 接口,并且覆寫相應(yīng)的 compareTo()函數(shù),才可以正常使用。
- 當(dāng)自定義對象之間進(jìn)行比較時,如果該對象小于、等于或大于指定對象,則分別返回負(fù)整數(shù)、零或正整數(shù)。
- TreeSet的基本操作(add、remove 和 contains)的時間復(fù)雜度是log(n) 。
- TreeSet是非線程安全的。
- TreeSet的迭代器是fail-fast策略的。
- TreeSet中元素不允許為Null,不允許重復(fù)值。
3 TreeSet常用方法
構(gòu)造方法
//創(chuàng)建一個空的 TreeSet,使用自然排序 public TreeSet() //指定比較器,如果比較器是 null 將使用自然排序 public TreeSet(Comparator<? super E> comparator)
添加元素
//添加一個元素 public boolean add(E e) //添加集合中的元素 public boolean addAll(Collection<? extends E> c)
刪除元素
public boolean remove(Object o)
查找元素
public boolean contains(Object o)
獲取TreeSet元素個數(shù)/判斷TreeSet是否為空/清空TreeSet
//獲取TreeSet元素個數(shù) public int size() //判斷TreeSet是否為空 public boolean isEmpty() //清空TreeSet public void clear()
返回此TreeSet中存在的最大元素/最小元素
//返回此TreeSet中存在的最大元素 public E last() { return m.lastKey(); } //返回此TreeSet中存在的最小元素 public E first() { return m.firstKey(); }
返回此集合中小于某個元素的最大的元素
public E lower(E e)
返回此集合中大于某個元素的最小的元素
public E higher(E e)
floor/ceiling
//返回在這個集合中小于或者等于給定元素的最大元素 public E floor(E e) //返回在這個集合中大于或者等于給定元素的最小元素 public E ceiling(E e)
檢索和刪除最?。ǖ谝粋€)元素
public E pollFirst()
檢索和刪除最大(最后)元素
public E pollLast()
TreeSet源碼
//存儲數(shù)據(jù)的底層數(shù)據(jù)結(jié)構(gòu) private transient NavigableMap<E,Object> m; //由于 TreeSet 只需要使用 Key 進(jìn)行存儲,因此 Value 存儲的是一個虛擬值 private static final Object PRESENT = new Object();
1、構(gòu)造方法
//使用 TreeMap 創(chuàng)建一個空的 TreeSet,使用自然排序, //添加的元素需要實現(xiàn) Comparable 接口,即是可比較的 public TreeSet() { this(new TreeMap<E,Object>()); } //指定比較器,如果比較器是 null 將使用自然排序 public TreeSet(Comparator<? super E> comparator) { this(new TreeMap<>(comparator)); } //構(gòu)建一個treeSet,包含參數(shù)c中的元素,排序是基于元素的自然順序 public TreeSet(Collection<? extends E> c) { this(); addAll(c); }
2、添加元素 調(diào)用TreeMap中的put()方法進(jìn)行添加元素。
public boolean add(E e) { return m.put(e, PRESENT)==null; }
將集合C中的所有元素添加到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<?> cc = 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); }
3、刪除元素
調(diào)用TreeMap中的remove()方法來刪除TreeSet中的元素,若set中存在要刪除的元素,刪除,返回true,不存在,返回false。
內(nèi)部調(diào)用navigableMap的remove方法,因為treeMap是其實現(xiàn)類,所以實際執(zhí)行的時候,調(diào)用的是treeMap的remove方法。
public boolean remove(Object o) { return m.remove(o)==PRESENT; }
4、查找元素 若set中存在該元素,返回true,不存在,返回false。
public boolean contains(Object o) { return m.containsKey(o); }
5、獲取TreeSet元素個數(shù)/判斷TreeSet是否為空/清空TreeSet
//獲取TreeSet元素個數(shù) public int size() { return m.size(); } //判斷TreeSet是否為空 public boolean isEmpty() { return m.isEmpty(); } //清空TreeSet public void clear() { m.clear(); }
6、返回此TreeSet中存在的最大元素/最小元素
//返回此TreeSet中存在的最大元素 public E last() { return m.lastKey(); } //返回此TreeSet中存在的最小元素 public E first() { return m.firstKey(); }
7、返回此集合中小于某個元素的最大的元素 返回此集合中最大的元素,該元素嚴(yán)格小于給定的元素。如果此TreeSet集合中不存在這樣的元素,則此方法返回Null。
public E lower(E e) { return m.lowerKey(e); }
8、返回此集合中大于某個元素的最小的元素 從集合中返回指定元素中最接近的最大元素,如果沒有,則返回Null。
public E higher(E e) { return m.higherKey(e); }
9、floor/ceiling
floor(E e)方法返回在這個集合中小于或者等于給定元素的最大元素,如果不存在這樣的元素,返回null。
ceiling(E e)方法返回在這個集合中大于或者等于給定元素的最小元素,如果不存在這樣的元素,返回null。
public E floor(E e) { return m.floorKey(e); } public E ceiling(E e) { return m.ceilingKey(e); }
10、檢索和刪除最?。ǖ谝粋€)元素
public E pollFirst() { Map.Entry<E,?> e = m.pollFirstEntry(); return (e == null) ? null : e.getKey(); }
11、檢索和刪除最大(最后)元素
public E pollLast() { Map.Entry<E,?> e = m.pollLastEntry(); return (e == null) ? null : e.getKey(); }
到此這篇關(guān)于Java集合之Set、HashSet、LinkedHashSet和TreeSet深度解析的文章就介紹到這了,更多相關(guān)Java的set集合內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Java微信公眾平臺開發(fā)(5) 文本及圖文消息回復(fù)的實現(xiàn)
這篇文章主要為大家詳細(xì)介紹了Java微信公眾平臺開發(fā)第五步,回文本及圖文消息回復(fù)的實現(xiàn)代碼,具有一定的參考價值,感興趣的小伙伴們可以參考一下2017-04-04Spring整合Quartz實現(xiàn)動態(tài)定時器的示例代碼
本篇文章主要介紹了Spring整合Quartz實現(xiàn)動態(tài)定時器的示例代碼,具有一定的參考價值,感興趣的小伙伴們可以參考一下。2017-01-01maven關(guān)于pom文件中的relativePath標(biāo)簽使用
在Maven項目中,子工程通過<relativePath>標(biāo)簽指定父工程的pom.xml位置,以確保正確繼承父工程的配置,這個標(biāo)簽可以配置為默認(rèn)值、空值或自定義值,默認(rèn)情況下,Maven會向上一級目錄尋找父pom;若配置為空值2024-09-09關(guān)于JSONObject.toJSONString出現(xiàn)地址引用問題
這篇文章主要介紹了關(guān)于JSONObject.toJSONString出現(xiàn)地址引用問題,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2022-03-03Java如何導(dǎo)出多個excel并打包壓縮成.zip文件
本文介紹了Java如何導(dǎo)出多個excel文件并將這些文件打包壓縮成zip格式,首先,需要從數(shù)據(jù)庫中獲取數(shù)據(jù)并導(dǎo)出到指定位置形成excel文件,接著,將這些數(shù)據(jù)分散到不同的excel文件中,最后,使用相關(guān)的Java工具類對這些excel文件進(jìn)行打包壓縮2024-09-09Java中的do while循環(huán)控制語句基本使用
這篇文章主要介紹了Java中的do while循環(huán)控制語句基本使用方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-01-01