Set集合了解一下

前言

本文使用用的是jdk1.8

Set 接口

我們前面再Collection集合的文章中已經(jīng)簡單的說過Set集合的特點。

  • 不包含重復元素，即兩個元素e1.equals(e2)不可相等。

需要注意的是：

當可變對象存儲到Set集合中的時候，如果通過一種可以影響對象的equals函數(shù)的比較結果的方式改變了該對象的話那么Set集合的行為則是不確定的。

Set 集合的常見實現(xiàn)類

image
  • HashSet：底層是通過HashMap來實現(xiàn)的，所以底層數(shù)據(jù)結構式是 散列表+紅黑樹 的數(shù)據(jù)結構。
  • TreeSet：底層數(shù)據(jù)結構是通過NavigableMap來實現(xiàn)的，底層數(shù)據(jù)結構是 紅黑樹?？杀ＷC元素的排列方式
  • LinkedHashSet：繼承自HashSet，和LinkedHashMap意義相似，底層數(shù)據(jù)結構是 散列表+雙向鏈表

HashSet

總的來說：

  • 實現(xiàn)了Set接口，底層其實是一個HashMap實例，所以由于HashMap的特性，無法保證元素的迭代的順序(HashMap擴容后的重散列會導致元素存儲位置的變更)。同時和HashMap一樣可以使用null元素做鍵值，但只能是一個。
  • 對Set結合進行迭代所需的時間與HashSet實例的大小(元素的數(shù)量)和底層HashMap實例（桶的數(shù)量）的“容量”的和成比例。如果某個Set的迭代性能比較重要，不要將初始容量設置的太高，或者將加載因子設置的太小(會出現(xiàn)很多空桶)。
  • 非同步，并發(fā)不安全?？梢猿绦蛲獠渴謩油?，也可以借助Collections.synchronizedSet函數(shù)來對該Set集合進行包裝來實現(xiàn)同步。
  • 迭代器是快速失敗的

HashSet的屬性及函數(shù)

image

一眼看上去還是很簡單的。只有兩個屬性，一個是它具體實現(xiàn)類HsahMap，另一個則是一個Object實例。這個Object實例在這里是充當HashMap實例中所有元素的公共value的。因為我們HashSet底層是通過HashMap來實現(xiàn)的，所有元素實際都存儲在key中，那么所對應的value如果不賦值則是null值得存在。所以HashSet的處理方式就是將所有元素的value都賦予該Object實例。

所以整個HashSet整體上來說幾乎所有的操作都是在底層操作了一個HashMap實例。根據(jù)上圖我們來看一下HashSet所實現(xiàn)的Set接口的函數(shù)都是怎么實現(xiàn)的。

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

public void clear() {
    map.clear();
}

public boolean contains(Object o) {
    return map.containsKey(o);
}

public Iterator<E> iterator() {
    return map.keySet().iterator();
}

public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}

public int size() {
    return map.size();
}

所有的構造函數(shù)所做的也是統(tǒng)一的初始化HashMap的操作

public HashSet() {
    map = new HashMap<>();
}

public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

TreeSet

總的來說：

  • 底層實現(xiàn)：和HashSet實現(xiàn)方式一樣，底層其實是由一個TreeMap實例來實現(xiàn)的。并實現(xiàn)了NavigableSet接口，是一個基于TreeMap的NavigableSet的實現(xiàn)
  • 有序：由于實現(xiàn)的NavigableSet接口繼承自SortedSet接口，所以存入TreeSet的所有元素都必須是實現(xiàn)了Comparable接口的，即保證這些元素在存入TreeSet的時候在通過compareTo函數(shù)進行比較并自然排序的時候不會報ClassCastException?；蛘咭部梢栽赟et實例構造的時候通過傳入的 Comparator來進行控制排序。
  • 非同步：并發(fā)線程不安全。還是老樣子，倘若想同步需要函數(shù)外手動進行控制，或者在創(chuàng)建Set集合的時候借助Collections類。Collections.synchronizedSortedSet的方法來對某個Set集合進行包裝。
  • 迭代器：迭代器是快速失敗的
  • 復雜度：基本操作函數(shù)如add,remove,contains的復雜度都是log(n)級別的(TreeMap底層紅黑樹)。

TreeSet的屬性和函數(shù)

image

從圖可以很明顯的看出它的實現(xiàn)機制和HashSet是一模一樣的。底層通過NavigableMap來實現(xiàn)，而NavigableMap則只有TreeMap這一個實現(xiàn)類。我們也可以稱之為底層是由TreeMap來實現(xiàn)的，而Object實例則是充當所有元素的value的存在。

image

我們來看一下TreeSet的5個構造函數(shù)都是如何實現(xiàn)的

public TreeSet() {
    this(new TreeMap<E,Object>());
}

public TreeSet(Collection<? extends E> c) {
    this();
    addAll(c);
}

public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}

TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}

public TreeSet(SortedSet<E> s) {
    this(s.comparator());
    addAll(s);
}

還是清晰的。都是通過構造一個TreeMap來實現(xiàn)整個TreeSet的所有操作的。

LinkedHashSet

總的來說：

  • 實現(xiàn)：LinkedHashSet底層由散列表和雙向鏈表來實現(xiàn)的。這一點和LinkedHashMap一樣。LinkedHashSet由HashSet和LinkedList共同來實現(xiàn)的。底層是HashMap，只是各節(jié)點Entry另外的還添加了兩個屬性before和after，通過雙向列表來鏈接。
  • 迭代：迭代有序，由于所有元素都通過LinkedeList雙向鏈表來維護，所以將按照元素插入到set中的順序（插入順序）進行迭代。需要注意的是如果一個元素已經(jīng)存在于LinkedHashSet中如果再插入該元素的話，該元素會被重新插入。并且迭代的時候和HashSet容量沒有關系。因為它結構中維護的一個雙向鏈表，迭代的時候是迭代這個雙向鏈表。相比于此HashSet迭代時則要受到容器容量很大的限制。
  • 優(yōu)點
    • 使用LinkedHashSet可以不用像HashSet一樣元素雜亂無序，而保證元素一定的有序性，可以做到TreeSet的功能卻不用TreeSet的成本。
    • 初始容量的大小對LinkedHasSet的影響要比對HashSet小很多，因為它在迭代的時候不受容器大小的影響。
  • 缺點
    • 性能比HashSet要差一點兒，因為還要維護一個雙向鏈表。
  • 允許null。非同步的，迭代是快速失敗的

LinkedHashSet的屬性和函數(shù)

image

很純粹的類，沒有自己實現(xiàn)的東西。所有的函數(shù)都是繼承自各個父類

我們來看一下它的構造函數(shù)：

public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);
}

public LinkedHashSet(int initialCapacity) {
    super(initialCapacity, .75f, true);
}

public LinkedHashSet() {
    super(16, .75f, true);
}


public LinkedHashSet(Collection<? extends E> c) {
    super(Math.max(2*c.size(), 11), .75f, true);
    addAll(c);
}

可以看出，都是去構造其父類HashSet。

總結

可以看到整個Set集合的實現(xiàn)都是Map映射。

  • HashSet：無序，允許為null，底層是HashMap(散列表+紅黑樹)，非線程同步
  • TreeSet：有序，不允許為null，底層是TreeMap(紅黑樹)，非線程同步
  • LinkedHashSet：迭代有序，允許為null，底層是HashMap+雙向鏈表，非線程同步
最后編輯于 ：
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

友情鏈接更多精彩內容