Java 中的 HashSet 指南

站长

2024年08月01日 22:36 · 阅读数 19

1. 概述

在本文中，我们将深入研究HashSet。它是最流行的 Set实现之一，也是 Java Collections Framework 的一个组成部分。HashSet是Java中一个基于哈希表实现的集合类，它保证集合中元素的唯一性，不保证元素的顺序。以下将详细解释HashSet的原理。

基于HashMap实现

HashSet的核心是基于HashMap实现的。它内部维护了一个HashMap对象，所有元素都存储在HashMap的key中，value则统一设置为一个虚拟对象。

哈希函数和哈希冲突

哈希函数: HashSet使用对象的hashCode()方法来计算元素的哈希值，将元素映射到哈希表中。
哈希冲突: 当两个不同对象的hashCode()方法返回相同的哈希值时，就会发生哈希冲突。HashSet使用链表来解决哈希冲突，将具有相同哈希值的元素存储在同一个链表中。

元素唯一性

HashSet利用HashMap的key唯一性来保证元素唯一性。当添加元素时，会先计算元素的哈希值，然后在HashMap中查找是否存在相同的key。如果存在相同key，则添加失败，保证元素唯一性。

性能

添加和删除: HashSet的添加和删除操作平均时间复杂度为O(1)，在大多数情况下非常高效。
查找: HashSet的查找操作平均时间复杂度也为O(1)。
迭代: 由于HashSet不保证元素顺序，迭代元素的顺序不可预测。

2. HashSet简介

HashSet是 Java Collections API 中的基本数据结构之一。

让我们回顾一下此实施中的最重要的方面：

它存储唯一元素并允许为空
它由HashMap支持
它不保持插入顺序
它不是线程安全的

请注意，当创建HashSet实例时，这个内部HashMap会被初始化：**

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

3. API

在本节中，我们将回顾最常用的方法并查看一些简单的例子。

3.1.添加()

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 个元素 - 每个存储桶对应一个不同的哈希码值
如果多个对象具有相同的哈希码值，则它们将存储在单个存储桶中
如果达到负载因子，则会创建一个大小为前一个数组两倍的新数组，并且所有元素都会重新散列并重新分配到新的相应存储桶中
为了检索一个值，我们对一个键进行哈希处理，对其进行修改，然后转到相应的存储桶，并在存在多个对象的情况下搜索潜在的链接列表

3.2.包含()

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.删除()

如果指定元素存在，则该方法会将其从集合中删除。如果集合包含指定元素，则此方法返回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.大小()

这是 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.迭代器()

该方法返回一个遍历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(logn)* 。

负载因子描述了最大填充水平，超过此水平，集合就需要调整大小。

我们还可以创建一个具有自定义初始容量和负载因子的 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的潜力。

转载自:https://juejin.cn/post/7397026285913325568