Java中的HashSet指南

1.概述

在这篇文章中，我们将深入探讨HashSet。它是最受欢迎的Set实现之一，同时也是Java集合框架的一个组成部分。

**2.介绍HashSet的方法**

HashSet是Java集合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;

先熟悉一下hashcode，详细了解一下基于散列的数据结构中的元素是如何组织的，会是一个不错的主意。

归纳总结：

一个HashMap是一个桶数组，默认容量为16个元素 – 每个桶数组对应一个不同的哈希代码值。
如果不同的对象有相同的哈希码值，它们会被存储在一个桶中
如果达到了负载因子，就会创建一个新的数组，其大小是前一个数组的两倍，所有元素都会被重新散列，并重新分配到新存储桶中
为了检索一个值，我们对一个键进行哈希处理，对其进行修改，然后进入相应的桶，在有多个对象的情况下，通过潜在的链表进行搜索

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中的元素的一个迭代器。元素的访问没有特定的顺序，迭代器是fail-fast的。

我们可以在这里观察到随机的迭代顺序。

@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");
    }
}

另外，如果我们使用了迭代器的移除方法，那么我们就不会遇到这个异常了。

@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());
}

不能保证迭代器的fail-fast行为，因为在存在非同步并发修改的情况下，不可能做出任何硬性保证。

失败的迭代器在尽力而为的基础上抛出ConcurrentModificationException。因此，编写一个依靠这个异常来保证其正确性的程序是错误的。

**4.如何保持HashSet的唯一性**

当我们把一个对象放入HashSet时，它使用该对象的hashcode值来确定一个元素是否已经在集合中了。

每个哈希码值都对应于某个桶的位置，其中可以包含各种元素，对于这些元素，计算出来的哈希值是一样的。但两个具有相同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。在第二种情况下，我们覆盖了默认容量，在第三种情况下，我们覆盖了两者。

较低的初始容量会降低空间复杂度，但会增加重新散列的频率，这是一个昂贵的过程。

另一方面，高的初始容量增加了迭代的成本和初始内存的消耗。

根据经验：

高的初始容量对大量的条目加上很少或没有迭代的情况下是很好的
初始容量低，适合条目少、迭代多的情况。

因此，在这两者之间取得正确的平衡是非常重要的。通常情况下，默认的实现是经过优化的，而且工作得很好，如果我们觉得有必要调整这些参数以适应要求，我们需要审慎地进行调整。

6.结语

在这篇文章中，我们概述了HashSet的效用，它的目的以及它的基础工作。我们看到，鉴于其恒定的时间性能和避免重复的能力，它在可用性方面是多么有效。

我们研究了API中的一些重要方法，它们是如何帮助我们作为一个开发者使用HashSet发挥其潜力的。

像往常一样，可以在GitHub上找到代码片段。