Java HashSet指南

1.概述

在本文中,我們將深入研究HashSet。它是最受歡迎的Set實現之一,並且是Java Collections Framework的組成部分。

2. HashSet簡介

HashSet是Java Collections API中的基本數據結構之一

讓我們回想一下此實現的最重要方面:

  • 它存儲唯一元素並允許為空
  • 它由HashMap支持
  • 它不保持插入順序
  • 它不是線程安全的

請注意,在創建HashSet的實例時,將初始化此內部HashMap

public HashSet() {

 map = new HashMap<>();

 }

如果您想更深入地了解HashMap的工作原理,可以在這裡閱讀有關它的文章。

3. API

在本節中,我們將回顧最常用的方法,並看一些簡單的示例。

3.1。add()

add()方法可用於將元素添加到集合中。方法合同規定,僅當元素不存在於集合中時才添加元素。如果添加了元素,則該方法返回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;

 }

map變量是對內部HashMap的引用

private transient HashMap<E, Object> map;

最好先熟悉哈希碼,以詳細了解元素在基於哈希的數據結構中的組織方式,這是一個好主意。

總結:

  • HashMap是一組存儲桶,默認容量為16個元素–每個存儲桶對應一個不同的哈希碼值
  • 如果各種對象具有相同的哈希碼值,它們將存儲在同一個存儲桶中
  • 如果達到負載因子,則會創建一個新數組,其大小是前一個數組的兩倍,並且所有元素都將重新混合併在新的相應存儲區之間重新分配
  • 要檢索一個值,我們對一個鍵進行計算哈希值,對其進行mod取餘,然後轉到相應的存儲桶並在可能存在多個對象的情況下搜索潛在的鍊錶。

3.2。 contains()

contains方法的目的是檢查給定的HashSet中是否存在元素。如果找到該元素,則返回true ,否則返回false。

我們可以檢查HashSet中的元素:

@Test

 public void whenCheckingForElement_shouldSearchForElement() {

 Set<String> hashsetContains = new HashSet<>();

 hashsetContains.add("String Added");



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

 }

每當將對像傳遞給此方法時,都會計算哈希值。然後,解析並遍歷相應的存儲桶位置。

3.3。remove()

該方法從集合中刪除指定的元素(如果存在)。如果集合包含指定的元素,則此方法返回true

讓我們看一個可行的例子:

@Test

 public void whenRemovingElement_shouldRemoveElement() {

 Set<String> removeFromHashSet = new HashSet<>();

 removeFromHashSet.add("String Added");



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

 }

3.4。clear()

當我們打算從集合中刪除所有項目時,將使用此方法。基礎實現只是清除基礎HashMap中的所有元素。

讓我們看看實際情況:

@Test

 public void whenClearingHashSet_shouldClearHashSet() {

 Set<String> clearHashSet = new HashSet<>();

 clearHashSet.add("String Added");

 clearHashSet.clear();



 assertTrue(clearHashSet.isEmpty());

 }

3.5。size()

這是API中的基本方法之一。它被大量使用,因為它有助於識別HashSet中存在的元素數量。基本實現只是將計算委託給HashMap的size()方法。

讓我們看看實際情況:

@Test

 public void whenCheckingTheSizeOfHashSet_shouldReturnThesize() {

 Set<String> hashSetSize = new HashSet<>();

 hashSetSize.add("String Added");



 assertEquals(1, hashSetSize.size());

 }

3.6。isEmpty()**

我們可以使用此方法來確定HashSet的給定實例是否為空。如果集合不包含任何元素,則此方法返回true

@Test

 public void whenCheckingForEmptyHashSet_shouldCheckForEmpty() {

 Set<String> emptyHashSet = new HashSet<>();



 assertTrue(emptyHashSet.isEmpty());

 }

3.7。 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());

 }

 }

如果在通過任何方式創建迭代器後(除了通過迭代器自己的remove方法之外)隨時修改集合,則迭代器將拋出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(2, hashset.size());

 }

迭代器的快速失敗行為無法得到保證,因為在存在不同步的並發修改的情況下不可能做出任何嚴格的保證。

快速失敗的迭代器會盡最大努力拋出ConcurrentModificationException 。因此,編寫依賴於此異常的程序的正確性是錯誤的。

4. HashSet如何保持唯一性?

當我們將對象放入HashSet時,它將使用對象的哈希碼值來確定元素是否已在集合中。

每個哈希碼值對應於一個特定的存儲桶位置,該存儲桶位置可以包含各種元素,為其計算的哈希值相同。但是具有相同hashCode的兩個對象可能不相等

因此,將使用*equals()*方法比較同一存儲桶中的對象。

5. HashSet的性能

HashSet的性能主要受以下兩個參數影響:其初始容量負載因子

將元素添加到集合中的預期時間複雜度為O(1) ,在最壞的情況下(僅存在一個存儲桶 ,該複雜度可能降至O(n )–因此,保持正確的HashSet容量至關重要。

重要說明:自JDK 8起,最差的時間複雜度為O(log \ n)* 。

負載因數描述最大填充量是多少,在該最大填充量以上時,需要調整一組的大小。

我們還可以使用初始容量負載因子的自定義值創建一個HashSet

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

 Set<String> hashset = new HashSet<>(20);

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

在第一種情況下,將使用默認值–初始容量為16,負載係數為0.75。在第二個中,我們覆蓋默認容量,在第三個中,我們覆蓋這兩個。

低的初始容量會降低空間複雜性,但會增加重新哈希的頻率,這是一個昂貴的過程。

另一方面,**高的初始容量會增加迭代成本和初始內存消耗。
**

根據經驗:

  • 較高的初始容量適用於大量條目,而幾乎不需要迭代
  • 初始容量低對於迭代次數少的幾個條目來說是好的

因此,在兩者之間取得正確的平衡非常重要。通常,默認實現是經過優化的並且可以正常工作,如果我們覺得需要調整這些參數以適合要求,則需要明智地做。

六,結論

在本文中,我們概述了HashSet的實用程序,其目的以及其基礎工作。鑑於其恆定的時間性能和避免重複的能力,我們在可用性方面看到了效率。

我們研究了API中的一些重要方法,這些方法如何幫助我們作為開發人員充分利用HashSet的潛力。

與往常一樣,可以在GitHub上找到代碼段。****

0 條評論,你可以發表評論,我們會進行改進
Comment author placeholder