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