Java的Set集合，你真的會用嗎？HashSet/TreeSet/LinkedHashSet
引言
當(dāng)我們需要對元素去重的時候，會使用Set集合，可選的Set集合有三個，分別是HashSet、LinkedHashSet、TreeSet，這三個常用的Set集合有什么區(qū)別呢？底層實現(xiàn)原理是什么樣？這篇文章一起來深度剖析。
共同點這三個類都實現(xiàn)了Set接口，所以使用方式都是一樣的，使用add()方法添加元素，使用remove()刪除元素，使用contains()方法判斷元素是否存在，使用iterator()方法迭代遍歷元素，這三個類都可以去除重復(fù)元素。
特性
- HashSet是最基礎(chǔ)的Set集合，可以去除重復(fù)元素，元素存儲是無序的。
- LinkedHashSet在HashSet功能基礎(chǔ)上，增加了按照元素插入順序或者訪問順序的迭代方式。
- TreeSet在HashSet功能基礎(chǔ)上，可以保證按照元素大小順序排列。
底層實現(xiàn)
- HashSet是基于HashMap實現(xiàn)的，使用組合的方式，并非繼承。
- LinkedHashSet繼承自HashSet，而內(nèi)部則是采用組合LinkedHashMap的方式實現(xiàn)的。[流汗] 就是這么亂，一會兒看一下源碼就明白了。
- TreeSet是基于TreeMap實現(xiàn)的，采用組合的方式，跟上面兩個Set集合沒關(guān)系。
圖片
下面詳細(xì)看一下這三個Set集合源碼的底層實現(xiàn)：
HashSet源碼實現(xiàn)
類屬性
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
/**
* 使用HashMap存儲數(shù)據(jù)
*/
private transient HashMap<E, Object> map;
/**
* value的默認(rèn)值
*/
private static final Object PRESENT = new Object();
}可以看出HashSet實現(xiàn)了Set接口，內(nèi)部采用HashMap存儲元素，利用了HashMap的key不能重復(fù)的特性，實現(xiàn)元素去重。而value使用默認(rèn)值，是一個空對象，沒有任何作用，純粹占坑。
初始化
HashSet常用的構(gòu)造方法有兩個，有參構(gòu)造方法，可以指定初始容量和負(fù)載系數(shù)。
/**
* 無參構(gòu)造方法
*/
HashSet<Integer> hashSet1 = new HashSet<>();
/**
* 有參構(gòu)造方法，指定初始容量和負(fù)載系數(shù)
*/
HashSet<Integer> hashSet = new HashSet<>(16, 0.75f);再看一下構(gòu)造方式對應(yīng)的源碼實現(xiàn)：
/**
* 無參構(gòu)造方法
*/
public HashSet() {
map = new HashMap<>();
}
/**
* 有參構(gòu)造方法，指定初始容量和負(fù)載系數(shù)
*/
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}HashSet的構(gòu)造方式源碼也很簡單，都是利用的HashMap的構(gòu)造方法實現(xiàn)。
常用方法源碼
再看一下HashSet常用方法源碼實現(xiàn)：
/**
* 添加元素
*/
public boolean add(E e) {
return map.put(e, PRESENT) == null;
}
/**
* 刪除元素
*/
public boolean remove(Object o) {
return map.remove(o) == PRESENT;
}
/**
* 判斷是否包含元素
*/
public boolean contains(Object o) {
return map.containsKey(o);
}
/**
* 迭代器
*/
public Iterator<E> iterator() {
return map.keySet().iterator();
}HashSet方法源碼也很簡單，都是利用HashMap的方法實現(xiàn)邏輯。利用HashMap的key不能重復(fù)的特性，value使用默認(rèn)值，contains()方法和iterator()方法也都是針對key進(jìn)行操作。
LinkedHashSet源碼實現(xiàn)
類屬性
LinkedHashSet繼承自HashSet，沒有任何私有的屬性。
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
}初始化
LinkedHashSet常用的構(gòu)造方法有三個，有參構(gòu)造方法，可以指定初始容量和負(fù)載系數(shù)。
/**
* 無參構(gòu)造方法
*/
Set<Integer> linkedHashSet1 = new LinkedHashSet<>();
/**
* 有參構(gòu)造方法，指定初始容量
*/
Set<Integer> linkedHashSet2 = new LinkedHashSet<>(16);
/**
* 有參構(gòu)造方法，指定初始容量和負(fù)載系數(shù)
*/
Set<Integer> linkedHashSet3 = new LinkedHashSet<>(16, 0.75f);再看一下構(gòu)造方法的源碼實現(xiàn)：
/**
* 無參構(gòu)造方法
*/
public LinkedHashSet() {
super(16, .75f, true);
}
/**
* 有參構(gòu)造方法，指定初始容量
*/
public LinkedHashSet() {
super(16, .75f, true);
}
/**
* 有參構(gòu)造方法，指定初始容量和負(fù)載系數(shù)
*/
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}LinkedHashSet的構(gòu)造方法使用的是父類HashSet的構(gòu)造方法，而HashSet的構(gòu)造方法使用的是LinkedHashMap的構(gòu)造方法，設(shè)計的就是這么亂！
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
/**
* HashSet的構(gòu)造方法，底層使用的是LinkedHashMap，專門給LinkedHashSet使用
*
* @param initialCapacity 初始容量
* @param loadFactor 負(fù)載系數(shù)
* @param dummy 這個字段沒啥用
*/
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
}LinkedHashSet的其他方法也是使直接用的父類HashSet的方法，就不用看了。
LinkedHashSet額外實現(xiàn)了按照元素的插入順序或者訪問順序進(jìn)行迭代的功能，是使用LinkedHashMap的實現(xiàn)，不了解LinkedHashMap的，可以看一下上篇文章對LinkedHashMap的源碼解析。
TreeSet源碼實現(xiàn)
類屬性
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable {
/**
* 用來存儲數(shù)據(jù)
*/
private transient NavigableMap<E, Object> m;
/**
* value的默認(rèn)值
*/
private static final Object PRESENT = new Object();
}TreeSet內(nèi)部使用NavigableMap存儲數(shù)據(jù)，而NavigableMap是TreeMap的父類，后面在初始化NavigableMap的時候，會用TreeMap進(jìn)行替換。而value使用默認(rèn)空對象，與HashSet類似。
初始化
TreeSet有兩個構(gòu)造方法，有參構(gòu)造方法，可以指定排序方式，默認(rèn)是升序。
/**
* 無參構(gòu)造方法
*/
TreeSet<Integer> treeSet1 = new TreeSet<>();
/**
* 有參構(gòu)造方法，傳入排序方式，默認(rèn)升序，這里傳入倒序
*/
TreeSet<Integer> treeSet2 = new TreeSet<>(Collections.reverseOrder());再看一下構(gòu)造方法的源碼實現(xiàn)：
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
/**
* 無參構(gòu)造方法
*/
public TreeSet() {
this(new TreeMap<E, Object>());
}
/**
* 有參構(gòu)造方法，傳入排序方式，默認(rèn)升序，這里傳入倒序
*/
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}TreeSet的構(gòu)造方法內(nèi)部是直接使用的TreeMap的構(gòu)造方法，是基于TreeMap實現(xiàn)的。
常用方法源碼
/**
* 添加元素
*/
public boolean add(E e) {
return m.put(e, PRESENT) == null;
}
/**
* 刪除元素
*/
public boolean remove(Object o) {
return m.remove(o) == PRESENT;
}
/**
* 判斷是否包含元素
*/
public boolean contains(Object o) {
return m.containsKey(o);
}
/**
* 迭代器
*/
public Iterator<E> iterator() {
return m.navigableKeySet().iterator();
}TreeSet常用方法的底層實現(xiàn)都是使用的TreeMap的方法邏輯，就是這么偷懶。
TreeSet可以按元素大小順序排列的功能，也是使用TreeMap實現(xiàn)的，感興趣的可以看一下上篇文章講的TreeMap源碼。由于TreeSet可以元素大小排列，所以跟其他Set集合相比，增加了一些按照元素大小范圍查詢的方法。
其他方法列表：
作用 | 方法簽名 |
獲取第一個元素 | E first() |
獲取最后一個元素 | E last() |
獲取大于指定鍵的最小鍵 | E higher(E e) |
獲取小于指定鍵的最大元素 | E lower(E e) |
獲取大于等于指定鍵的最小鍵 | E ceiling(E e) |
獲取小于等于指定鍵的最大鍵 | E floor(E e) |
獲取并刪除第一個元素 | E pollFirst() |
獲取并刪除最后一個元素 | E pollLast() |
獲取前幾個元素（inclusive表示是否包含當(dāng)前元素） | NavigableSetheadSet(E toElement, boolean inclusive) |
獲取后幾個元素（inclusive表示是否包含當(dāng)前元素） | NavigableSettailSet(E fromElement, boolean inclusive) |
獲取其中一段元素集合（inclusive表示是否包含當(dāng)前元素） | NavigableSetsubSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) |
獲取其中一段元素集合（左開右開） | SortedSetsubSet(E fromElement, E toElement) |
獲取前幾個元素（不包含當(dāng)前元素） | SortedSetheadSet(E toElement) |
獲取后幾個元素（不包含當(dāng)前元素） | SortedSettailSet(E fromElement) |
總結(jié)
HashSet、LinkedHashSet、TreeSet，這三個常用的Set集合的共同點是都實現(xiàn)了Set接口，所以使用方式都是一樣的，使用add()方法添加元素，使用remove()刪除元素，使用contains()方法判斷元素是否存在，使用iterator()方法迭代遍歷元素，這三個類都可以去除重復(fù)元素。
不同點是：HashSet的關(guān)鍵特性：
- 是最基礎(chǔ)的Set集合，可以去除重復(fù)元素。
- HashSet是基于HashMap實現(xiàn)的，使用組合的方式，并非繼承。
- 利用了HashMap的key不重復(fù)的特性，而value是一個默認(rèn)空對象，其他方法也都是使用HashMap實現(xiàn)。
LinkedHashSet的關(guān)鍵特性：
- LinkedHashSet繼承自HashSet，而內(nèi)部則是采用組合LinkedHashMap的方式實現(xiàn)的。
- LinkedHashSet在HashSet功能基礎(chǔ)上，增加了按照元素插入順序或者訪問順序的迭代方式，代價是額外增加一倍的存儲空間。
- 方法內(nèi)部都是使用LinkedHashMap實現(xiàn)的。
TreeSet的關(guān)鍵特性：
- TreeSet是基于TreeMap實現(xiàn)的，也是采用組合的方式。
- TreeSet在HashSet功能基礎(chǔ)上，可以保證按照元素大小順序排列，代價是查詢、插入、刪除接口的時間復(fù)雜度從O(1)退化到O(log n)。
- 方法內(nèi)部都是使用TreeMap實現(xiàn)的。
