深入了解java之HashSet

本文我們深入讨論HashSet，Set接口最常用的實作，也是java Collection Framework的一個組成部分。

HashSet簡介

HashSet是java集合API中基礎資料結構之一，我們回顧起實作中最基本的方面：

• 存儲唯一進制素，允許null值
• 基于HashMap實作
• 不維護插入順序
• 不是線程安全的

注意，當建立HashSet執行個體時，内部HashMap被初始化：

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

如果你對HashMap感興趣，可以閱讀深入了解Java HashMap。

HashSet API

本節我們通過一些簡單示例說明HashSet最常用的方法。

add()

add方法往set中增加元素。該方法約定當set中不存在該元素時将增加，如果增加成功傳回true，反之傳回false。

HashSet增加元素示例代碼如下：

@Test
public void whenAddingElement_shouldAddElement() {
    Set<String> hashset = new HashSet<>();

    assertTrue(hashset.add("String Added"));
}
           

從實作角度看，add方法是極其重要的，實作細節描述了HashSet内部工作機制，利用HashMap的put方法：

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

HashMap類型的map變量為HashSet的内部引用變量。

private transient HashMap<E, Object> map;
           

首先熟悉hashcode并深入了解基于hash資料結構如何組織元素是非常有必要，這裡簡單總結如下：

• HashMap基于内部數組（桶），預設容量為16，每個桶對應不同的hashcode值。
• 如果不同對象有相同的hashcode值，則這些對象被存儲在相同的桶中。
• 如果達到載入因子對應容量時，會建立大小為原來的兩倍的新數組，所有元素需要重新計算哈希值，并重新分布相應的桶中。
• 擷取值，首先哈希key并修改對應哈希值，然後找到相應桶，如果桶中有多個對象，則需要搜尋其中連結list并傳回對應值。

contains()

contains()方法的目的是檢查給定HashSet是否存儲指定元素。如果找到傳回true，反之為false。示例代碼：

@Test
public void whenCheckingForElement_shouldSearchForElement() {
    Set<String> hashsetContains = new HashSet<>();
    hashsetContains.add("String Added");

    assertTrue(hashsetContains.contains("String Added"));
}
           

當給這個方法傳遞參數對象時，哈希值就會被計算出來。然後在相應的bucket位置解析和周遊相應的值。

remove()

remove()方法從set中删除指定元素。如果set包含指定元素傳回true。示例如下：

@Test
public void whenRemovingElement_shouldRemoveElement() {
    Set<String> removeFromHashSet = new HashSet<>();
    removeFromHashSet.add("String Added");

    assertTrue(removeFromHashSet.remove("String Added"));
}
           

clear()

如果我們打算删除set中所有元素，可以使用該方法。底層實作簡單清除内部HashMap中所有元素。示例代碼：

@Test
public void whenClearingHashSet_shouldClearHashSet() {
    Set<String> clearHashSet = new HashSet<>();
    clearHashSet.add("String Added");
    clearHashSet.clear();

    assertTrue(clearHashSet.isEmpty());
}
           

size()

HashSet API中基本方法之一。實際中大量使用，因為有助于識别在HashSet中元素的數量。底層實作隻是将計算委托給HashMap的size()方法。示例代碼：

@Test
public void whenCheckingTheSizeOfHashSet_shouldReturnThesize() {
    Set<String> hashSetSize = new HashSet<>();
    hashSetSize.add("String Added");

    assertEquals(, hashSetSize.size());
}
           

iterator()

該方法傳回set元素的疊代器。不保證原始的插入順序，疊代器是快速失敗方式。示例代碼：

@Test
public void whenIteratingHashSet_shouldIterateHashSet() {
    Set<String> hashset = new HashSet<>();
    hashset.add("First");
    hashset.add("Second");
    hashset.add("Third");
    Iterator<String> itr = hashset.iterator();
    while(itr.hasNext()){
        System.out.println(itr.next());
    }
}
           

set的疊代器被建立之後，如果set被修改，除非我們通過疊代器自己的删除方法，否則會抛出ConcurrentModificationException異常，示例代碼：

@Test(expected = ConcurrentModificationException.class)
public void whenModifyingHashSetWhileIterating_shouldThrowException() {

    Set<String> hashset = new HashSet<>();
    hashset.add("First");
    hashset.add("Second");
    hashset.add("Third");
    Iterator<String> itr = hashset.iterator();
    while (itr.hasNext()) {
        itr.next();
        hashset.remove("Second");
    }
}
           

這裡我們使用疊代器自身的remove方法代替，則不會抛出異常：

@Test
public void whenRemovingElementUsingIterator_shouldRemoveElement() {

    Set<String> hashset = new HashSet<>();
    hashset.add("First");
    hashset.add("Second");
    hashset.add("Third");
    Iterator<String> itr = hashset.iterator();
    while (itr.hasNext()) {
        String element = itr.next();
        if (element.equals("Second"))
            itr.remove();
    }

    assertEquals(, hashset.size());
}
           

Fail-Fast行為不保證在所有場景都發生，因為并發修改情況下行為不可預測。是以，基于該異常程式設計是不可取的。

HashSet如何保證唯一性

當我們往HashSet中增加對象元素時，對象的hashcode值決定元素是否已經存在。

對象hashcode每次計算都一樣，每個hashcode值對應容納不同對象桶的位置。但如果兩個對象hashcode有可能相同，在同一桶中的對象使用equals方法進行比較。

HashSet的性能

HashSet性能受兩個參數影響：初始化容量及負載因子（客座率）。

将元素添加到HashSet的預期時間複雜度是O(1)，它可以在最壞的情況下(隻有一個bucket)下降到O(n)——是以，保持合适的HashSet容量非常重要。

特别注意的是：從JDK8之後，最壞情況時間複雜度為O(logn)。

負載因子描述最大填充級别，超過Set則需重新擴充至原來兩倍。我們使用自定義的參數可以建立HashSet：

Set<String> hashset = new HashSet<>();
Set<String> hashset = new HashSet<>();
Set<String> hashset = new HashSet<>(, f);
           

第一行使用預設值，初始容量為16，負載因子為0.75。第二行代碼覆寫了預設容量，第三行代碼兩個參數都被覆寫。

低初始容量節約空間，但增加重新哈希的頻率，需要昂貴的開銷。另一方面，高初始容量，增加疊代次數和初始記憶體消耗。

一般來說：

• 高初始容量對擁有大量元素且幾乎沒有疊代情況有益。
• 低初始容量對擁有較小元素且有很多疊代情況有益。

是以，在兩者之間找到适當的平衡非常重要。通常情況下，預設參數經過優化且工作良好。如果我們覺得需要調整這些參數以适應需求，那麼我們需要明智地進行決策選擇。

總結

在本文中，我們概括了HashSet的用法及底層工作原理。了解其應用的效率及較好的性能，以及如何避免重複元素。

同時學習了HashSet的一些重要方法，能夠幫助開發者充分利用其潛能。