Java Set 常用集合 HashSet、LinkedHashSet、TreeSet

Java 中的 Set 是非常常用的資料型別，Set 是無序的 Collection，Java Set 有三個常用的實作類，分別是：HashSet、LinkedHashSet、TreeSet

本文基于 JDK8 分析

HashSet

HashSet 繼承自 AbstractSet，實作了 Set 介面，底層基于 HashMap 實作，是一個不允許有重復元素的無序集合，允許 null 元素，非執行緒安全，HashSet 還實作了 Cloneable、Serializable 介面，所以 HashSet 是支持復制、序列化的

所以說，HashMap 是替 HashSet 打工的，就像老板手下的員工，任勞任怨，做牛做馬，像極了被剝削的我們（小聲嗶嗶）

// 用于存盤元素的 HashMap
private transient HashMap<E,Object> map;
// 湊數的值元素，
private static final Object PRESENT = new Object();

HashSet 有五個建構式，解釋下第二個建構式：默認加載因子為 0.75 的情況下，假設 c 的元素個數就是 map 此時的最大閾值，最大閾值為 (int) (c.size()/.75f)，再加一，通過 HashMap 的擴容機制（取大于當前容量的最小二次冪），就可以取得最適合的容量大小

// 構造一個默認容量為 16 的 HashMap
public HashSet()  {
    map = new HashMap<>();
}
// 將 Collection 中的元素賦給 HashMap
public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}
// 指定 HashMap 的初始容量和加載因子
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}
// 指定 HashMap 的初始容量
public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}
// 供 LinkedHashSet 使用
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

HashSet 常用方法

第一個是 add 方法，HashSet 使用 HashMap 保證元素不重復，熟悉 HashMap 的都知道，HashMap 的 Key 是不允許重復的，所以可以把要添加的元素作為 HashMap 的 Key 保存，但 Value 還是要有的，所以 HashSet 又定義了一個靜態常量物件 PRESENT 來湊數，實際上并沒有什么意義

private static final Object PRESENT = new Object();

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

到這里就一目了然了，HashSet 中添加元素的方法其實就是呼叫 HashMap 的 put 方法，如果 put 方法的回傳值為 null，證明以 e 為鍵的元素不存在，則可以添加；否則會把原有的值洗掉并覆寫，并回傳原來的值，所以當 add 方法中的條件判斷成立，則證明添加成功，反之則失敗，如果不了解 HashMap 的機制，可以看一下下面這張圖


至于其他的 remove、contains 就更不用說了，全是 HashMap 的知識，不再贅述

LinkedHashSet

LinkedHashSet 是 HashSet 的子類，實作了 Set 介面，Set 有的特點它都有，既然 HashSet 靠 HashMap 干活，那是否 LinkedHashSet 也有自己的小弟呢？（沒錯，說的就是你 LinkedHashMap）

還記得之前提到在 HashSet 有一個專供 LinkedHashSet 使用的構造方法嗎？這個構造方法只能由 LinkedHashSet 呼叫，引數 dummy 并沒有實際意義，只是為了和 HashSet 中其他引數區分開罷了（多載原理）

LinkedHashMap 基于雙向鏈表實作，相比于 HashMap 最大的不同就是有序，LinkedHashSet 中除了四個構造器以外再無其他方法，全部繼承自 HashSet，如果想了解更多，就去看看 LinkedHashMap 吧

// HashSet 中專供 LinkedHashSet 使用的構造方法
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

// LinkedHashSet 的構造方法
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);
}

TreeSet

在此之前先了解一下 SortedSet，SortSet 擴展了 Set 并提供其元素的總排序，要求所有元素都必須實作 Comparable 介面，而且所有元素都必須是可比較的，即兩個物件可以互相作為 compareTo 方法的引數，從這里可以看出，SortedSet 所謂的有序并不是我們通常認為的先后插入順序，而是根據物件的比較函式對元素排序，SortSet 介面的方法如下：

// 回傳用于對此集合中的元素進行排序的比較器，如果此集合使用其元素的自然順序，則回傳 null
Comparator<? super E> comparator();
// 回傳此集合的部分元素，元素范圍從 fromElement（包括）到 toElement（不包括）
SortedSet<E> subSet(E fromElement, E toElement);
// 回傳此集合的部元素，其中元素全部小于 toElement
SortedSet<E> headSet(E toElement);
// 回傳此集合的部分元素，其中元素全部大于或等于 fromElement
SortedSet<E> tailSet(E fromElement);
// 回傳此集合中當前的第一個（最低）元素
E first();
// 回傳此集合中當前的最后一個（最高）元素
E last();

NavigableSet 實作了 Sorted 介面，其本身也是一個介面，對 SortedHash 進行了擴展，支持導航方法，例如查找與指定目標最匹配項等，TreeSet 繼承自 AbstractSet，實作了 NavigableSet 介面，TreeSet 基于 TreeMap 實作，其構造方法如下：

private transient NavigableMap<E,Object> m;

// 構造一個指定的 NavigableMap 的集合
TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}
// 默認方法，根據元素的自然排序進行排序
public TreeSet() {
    this(new TreeMap<E,Object>());
}
// 指定比較器進行排序
public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}
// 構造一個包含指定集合中元素的集合，根據元素的自然排序進行排序
public TreeSet(Collection<? extends E> c) {
    this();
    addAll(c);
}
// 構造一個包含相同元素的集合，并使用與指定排序集相同的排序
public TreeSet(SortedSet<E> s) {
    this(s.comparator());
    addAll(s);
}

TreeSet 也是基于 TreeMap 作業的，TreeMap 也是一個可排序的 Map，排序原理也是依靠比較器，更多的細節請了解 TreeMap

標籤：其他

上一篇：Python爬蟲案例：js解密 爬取漫畫

下一篇：求助！vc++無法構建程式！