【原】精解四大集合框架：Set核心知識總結(jié)

田維常 2020-09-23

展開全文

Set繼承于Collection接口，是一個不允許出現(xiàn)重復(fù)元素,，并且無序的集合,，主要有HashSet和TreeSet兩大實(shí)現(xiàn)類，另外LinkedHashSet也有一定的使用頻率,。

在判斷重復(fù)元素的時候,，Set集合會調(diào)用hashCode()和equal()方法來實(shí)現(xiàn)。

類圖UML

Set常用方法

與List一樣都是接口,，Set接口也提供了集合操作的基本方法,。Java四大集合之一，但與List不同的是,，Set還提供了equals(Object o)和hashCode(),，供其子類重寫，以實(shí)現(xiàn)對集合中插入重復(fù)元素的處理,；

 1public interface Set<E> extends Collection<E> {
 2    //添加
 3    boolean add(E e);
 4    boolean addAll(Collection<? extends E> c);
 5
 6    //刪除
 7    boolean remove(Object o);
 8    boolean removeAll(Collection<?> c);
 9    void clear();
10
11    //長度
12    int size();
13    //是否為空
14    boolean isEmpty();
15
16    //是否包含
17    boolean contains(Object o);
18    boolean containsAll(Collection<?> c);
19    boolean retainAll(Collection<?> c); 
20
21    //獲取Set集合的迭代器：
22    Iterator<E> iterator();
23
24    //把集合轉(zhuǎn)換成數(shù)組
25    Object[] toArray();
26    <T> T[] toArray(T[] a);
27
28    //判斷元素是否重復(fù),，為子類提高重寫方法
29    boolean equals(Object o);
30    int hashCode();
31}

接口里知識定義了方法，具體的實(shí)現(xiàn)請看下面兩個常用實(shí)現(xiàn)類,。

HashSet

HashSet 是用來存儲沒有重復(fù)元素的集合類,，并且是無序的。實(shí)現(xiàn)了 Set 接口,。底層其實(shí)主要是使用 HashMap 機(jī)制實(shí)現(xiàn),，所以也是線程不安全。

部分源碼：

1public class HashSet<E>  extends AbstractSet<E>  implements Set<E>, Cloneable, java.io.Serializable{
2    private transient HashMap<E,Object> map;
3    //這里這個PRESENT就是作為HashMap中的key
4    private static final Object PRESENT = new Object();
5    public HashSet() {
6        map = new HashMap<>();
7    }

特征：

不可重復(fù)
無序
線程不安全,，若多個線程同時操作HashSet,，必須通過代碼實(shí)現(xiàn)同步；
集合元素可以是 null,，但只能放入一個 null

使用場景：去重,、不要求順序

原理：HashSet底層由HashMap實(shí)現(xiàn)，插入的元素被當(dāng)做是HashMap的key,，根據(jù)hashCode值來確定集合中的位置,，由于Set集合中并沒有角標(biāo)的概念，所以并沒有像List一樣提供get（）方法,。當(dāng)獲取HashSet中某個元素時,，只能通過遍歷集合的方式進(jìn)行equals()比較來實(shí)現(xiàn)；

常用方法

 1    //添加
 2    public boolean add(E e) {
 3        return map.put(e, PRESENT)==null;
 4    }
 5    //移除
 6    public boolean remove(Object o) {
 7        return map.remove(o)==PRESENT;
 8    }
 9    //清空
10    public void clear() {
11        map.clear();
12    }
13    //獲取迭代器
14    public Iterator<E> iterator() {
15        return map.keySet().iterator();
16    }
17    //判斷是否為空
18    public boolean isEmpty() {
19        return map.isEmpty();
20    }
21    //求集合大小
22    public int size() {
23        return map.size();
24    }

正如上面所說,，底層使用 HashMap 的 key 不能重復(fù)機(jī)制來實(shí)現(xiàn)沒有重復(fù)的 HashSet,。

TreeSet

TreeSet 實(shí)現(xiàn)了 SortedSet 接口，意味著可以排序，它是一個有序并且沒有重復(fù)的集合類,，底層是通過 TreeMap 實(shí)現(xiàn)。TreeSet 并不是根據(jù)插入的順序來排序,，而是字典自然排序,。線程不安全。從名字上可以看出,，此集合的實(shí)現(xiàn)和樹結(jié)構(gòu)有關(guān),。與HashSet集合類似，TreeSet也是基于Map來實(shí)現(xiàn),，具體實(shí)現(xiàn)TreeMap(后面講解),，其底層結(jié)構(gòu)為紅黑樹（特殊的二叉查找樹）。

TreeSet 支持兩種排序方式：自然升序排序和自定義排序,。

部分源碼

 1public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable{
 2
 3    private transient NavigableMap<E,Object> m;
 4
 5    private static final Object PRESENT = new Object();
 6
 7    TreeSet(NavigableMap<E,Object> m) {
 8        this.m = m;
 9    }
10
11    public TreeSet() {
12        this(new TreeMap<E,Object>());
13    }

常用方法

 1 //求集合大小
 2 public int size() {
 3     return m.size();
 4 }
 5 //判斷是否為空
 6 public boolean isEmpty() {
 7     return m.isEmpty();
 8 }
 9 //判斷是否包含
10 public boolean contains(Object o) {
11     return m.containsKey(o);

12 }

特征：

不可重復(fù)
有序,，默認(rèn)自然升序排序
線程不安全，若多個線程同時操作HashSet,，必須通過代碼實(shí)現(xiàn)同步,；
集合元素不可以為 null
對插入的元素進(jìn)行排序，是一個有序的集合（主要與HashSet的區(qū)別）;
底層使用紅黑樹結(jié)構(gòu),，而不是哈希表結(jié)構(gòu),；

原理：

TreeSet 底層是基于 treeMap（紅黑樹結(jié)構(gòu)）實(shí)現(xiàn)的，可以自定義比較器對元素進(jìn)行排序,，或是使用元素的自然順序,。

使用場景：去重、要求排序

LinkedHashSet

LinkedHashSet 是使用 HashSet 機(jī)制實(shí)現(xiàn),，它是一個可以保證插入順序或是訪問順序,，并且沒有重復(fù)的集合類。線程不安全,。

部分源碼

 1public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable {
 2
 3    public LinkedHashSet(int initialCapacity, float loadFactor) {
 4        super(initialCapacity, loadFactor, true);
 5    }
 6
 7    public LinkedHashSet(int initialCapacity) {
 8        super(initialCapacity, .75f, true);
 9    }
10
11    public LinkedHashSet() {
12        super(16, .75f, true);
13    }