Java中的HashSet

Java HashSet 类实现了Set接口，由一个实际上是HashMap实例的哈希表支持。不保证哈希集迭代顺序，这意味着该类不能保证元素随时间的顺序不变。该类允许空元素。该类还为基本操作（如添加，删除，包含和大小）提供了恒定时间性能，假设哈希函数将元素适当地分散在桶中，这将在本文中进一步阐述。

Java HashSet特点

下面提到HashSet的一些重要特点:

• 实现了Set接口。
• HashSet的底层数据结构是Hashtable。
• 由于它实现了Set接口，所以不允许出现重复的值。
• 插入HashSet中的对象不保证以相同的顺序插入。对象是根据它们的哈希码插入的。
• 允许NULL元素在HashSet中存在。
• HashSet还实现了序列化和克隆接口。

声明HashSet

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, Serializable

其中 E 是一个HashSet中存储元素的类型。

Java HashSet示例

// Java program to illustrate the concept
// of Collection objects storage in a HashSet
import java.io.*;
import java.util.*;
  
class CollectionObjectStorage {
    
    public static void main(String[] args)
    {
        // Instantiate an object of HashSet
        HashSet<ArrayList> set = new HashSet<>();
  
        // create ArrayList list1
        ArrayList<Integer> list1 = new ArrayList<>();
  
        // create ArrayList list2
        ArrayList<Integer> list2 = new ArrayList<>();
  
        // Add elements using add method
        list1.add(1);
        list1.add(2);
        list2.add(1);
        list2.add(2);
        set.add(list1);
        set.add(list2);
  
        // print the set size to understand the
        // internal storage of ArrayList in Set
        System.out.println(set.size());
    }
}

输出：

1

在存储一个对象之前，HashSet使用hashCode()和equals()方法检查是否存在现有条目。在上面的示例中，如果两个列表具有相同的元素和相同的顺序，则认为它们相等。当您在两个列表上调用hashCode()方法时，由于它们相等，它们都会给出相同的哈希值。

_注意： HashSet不存储重复项 _ 。如果给定两个相等的对象，则它只存储第一个对象，这里是list1。

HashSet的层次结构如下所示：

HashSet的内部工作原理

所有Set接口的类都由Map内部支持。 HashSet使用HashMap来存储其内部对象。您可能会想，要在HashMap中输入一个值，我们需要一个键值对，但是在HashSet中，我们只传递一个值。

在HashMap中的存储方式： 实际上，我们在HashSet中插入的值充当地图对象的键，对于它的值，Java使用一个常量变量。因此，在键值对中，所有值都将相同。

HashSet在Java文档中的实现

private transient HashMap map;

// 构造函数 - 1
// 所有的构造函数都在内部创建HashMap对象。
public HashSet()
{
    // 内部创建HashMap对象
    map = new HashMap();
}

// 构造函数 - 2
public HashSet(int initialCapacity)
{
    // 内部创建HashMap对象
    map = new HashMap(initialCapacity);
}

// 用于在Map中与对象相关联的虚拟值
private static final Object PRESENT = new Object();

如果我们查看HashSet类的 _add() _ 方法：

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

我们可以注意到，HashSet类的add()方法内部调用了 _put() _ 方法，通过将您指定的元素作为键和常量“PRESENT”作为其值来支持HashMap对象。 _remove() _ 方法也是以相同的方式工作。它内部调用了Map接口的remove方法。

public boolean remove(Object o)
{
  return map.remove(o) == PRESENT;
}

HashSet不仅存储唯一对象，还存储唯一对象的集合，如ArrayList，LinkedList，Vector，..等等。

HashSet类的构造函数

要创建HashSet，我们需要创建HashSet类的对象。 HashSet类包括各种构造函数，允许可能的HashSet创建。以下是此类中可用的构造函数。

1. HashSet()

此构造函数用于在其中默认初始容量为16，默认装载因子为0.75的空HashSet对象中构建元素。如果我们想要创建一个名为hs的空HashSet，则可以创建：

HashSet<E> hs = new HashSet<E>();

2. HashSet(int initialCapacity)

此构造函数用于在对象创建时指定initialCapacity的空HashSet对象中构建元素。这里，默认的loadFactor仍为0.75。

HashSet<E> hs = new HashSet<E>(int initialCapacity);

3. HashSet(int initialCapacity, float loadFactor)

此构造函数用于在对象创建时指定initialCapacity和loadFactor的空HashSet对象中构建元素。

HashSet<E> hs = new HashSet<E>(int initialCapacity, float loadFactor);

4. HashSet(Collection)

此构造函数用于构建包含给定集合中所有元素的HashSet对象。简而言之，当需要从任何Collection对象转换为HashSet对象时，可以使用此构造函数。如果我们希望创建名为hs的HashSet，则可以创建如下：

HashSet<E> hs = new HashSet<E>(Collection C);

下面是上述主题的实现：

// Java程序演示HashSet类的工作
  
// 导入所需的类
import java.util.*;
  
// 主类
// HashSetDemo
class GFG {
  
    // 主驱动程序方法
    public static void main(String[] args)
    {
  
        // 创建一个空的HashSet
        HashSet<String> h = new HashSet<String>();
  
        // 使用add()方法将元素添加到HashSet
        h.add("India");
        h.add("Australia");
        h.add("South Africa");
  
        // 添加重复元素
        h.add("India");
  
        // 显示HashSet
        System.out.println(h);
        System.out.println("列表是否包含印度：" + h.contains("India"));
  
        // 使用remove()方法从HashSet中删除项目
        h.remove("Australia");
        System.out.println("移除澳大利亚后的列表：" + h);
  
        // 显示消息
        System.out.println("正在遍历列表：");
  
        // 遍历hashSet项
        Iterator<String> i = h.iterator();
  
        // 只要有单个元素保持真实状态
        while (i.hasNext())
  
            // 使用next()方法迭代元素
            System.out.println(i.next());
    }
}

输出：

[South Africa, Australia, India]
列表是否包含印度：true
移除澳大利亚后的列表：[South Africa, India]
正在遍历列表：
South Africa
India

HashSet中的方法

在HashSet上执行各种操作

接下来，我们将了解如何在HashSet上执行一些常用操作。

1. 在HashSet中添加元素

要在HashSet中添加元素，我们可以使用add()方法。但需要注意的是，HashSet中不保留插入顺序。我们需要记住，不允许重复元素，并忽略所有重复元素。

示例

// Java程序：向 HashSet 添加元素
  
// 导入所需的类
import java.io.*;
import java.util.*;
  
// 主类
// AddingElementsToHashSet
class GFG {
  
    // 方法1
    // 主驱动程序
    public static void main(String[] args)
    {
        // 创建一个字符串实体的空 HashSet
        HashSet<String> hs = new HashSet<String>();
  
        // 使用 add() 方法添加元素
        hs.add("Geek");
        hs.add("For");
        hs.add("Geeks");
  
        // 打印集合中的所有字符串条目
        System.out.println("HashSet elements : " + hs);
    }
}

输出:

HashSet elements : [Geek, For, Geeks]

2. HashSet 中的删除元素

可以使用 remove() 方法从 HashSet 中删除值。

例如

// Java程序说明HashSet中的元素删除
  
// 导入所需的类
import java.io.*;
import java.util.*;
  
// 主类
// RemoveElementsOfHashSet
class GFG {
  
    // 主驱动程序
    public static void main(String[] args)
    {
        // 创建一个字符串实体的空 HashSet
        HashSet<String> hs = new HashSet<String>();
  
        // 使用 add() 方法将元素添加到上述集合中
        hs.add("Geek");
        hs.add("For");
        hs.add("Geeks");
        hs.add("A");
        hs.add("B");
        hs.add("Z");
  
        // 打印 HashSet 元素
        System.out.println("Initial HashSet " + hs);
  
        // 删除元素B
        hs.remove("B");
  
        // 打印更新后的HashSet元素
        System.out.println("After removing element " + hs);
  
        // 如果元素不存在则返回false
        System.out.println("Element AC exists in the Set : "
                           + hs.remove("AC"));
    }
}

输出:

Initial HashSet [A, B, Geek, For, Geeks, Z]
After removing element [A, Geek, For, Geeks, Z]
Element AC exists in the Set : false

3. 遍历 HashSet

使用 iterator() 方法遍历 HashSet 中的元素。另外，使用增强的 for 循环也是最受欢迎的方法之一。

例如

代码块

输出

A, B, Geek, For, Geeks, Z, 
A, B, Geek, For, Geeks, Z, 

HashSet 操作的时间复杂度： HashSet 的底层数据结构是哈希表，因此 HashSet 的 add、remove 和查找（contains 方法）操作的摊还（平均或常规）时间复杂度为 O(1) 时间。

HashSet 的性能

HashSet 扩展 Abstract Set 类并实现了 Set、Cloneable 和 Serializable 接口，其中 E 是此集合维护的元素类型。HashSet 的直接已知子类是 LinkedHashSet。

现在，为了保持常数时间的性能，遍历 HashSet 需要的时间与 HashSet 实例的大小（元素数量）加上后端 HashMap 实例的“容量”（桶数）成比例。因此，如果迭代性能很重要，则不要将初始容量设置得太高（或加载因子设置得太低）。

• 初始容量： 初始容量指创建哈希表时的桶数（HashSet内部使用哈希表数据结构）。当当前大小达到最大值时，桶数将自动增加。

• 负载因子： 负载因子是HashSet允许其容量在自动增加之前达到的最大值的一个度量。当哈希表中的元素数超过负载因子和当前容量的乘积时，哈希表将被重新哈希（即内部数据结构将被重建），以便哈希表具有大约两倍的桶数。

                  表中存储的元素数量
负载因子 = -----------------------------------------
                        哈希表大小

例子： 如果内部容量为16，负载因子为0.75，那么当表中有12个元素时，桶数将自动增加。

对性能的影响：

负载因子和初始容量是影响HashSet操作性能的两个主要因素。负载因子为0.75提供了非常有效的时间和空间复杂度性能。如果我们将负载因子值增加到超过这个值，那么内存开销将会减少（因为它会减少内部重建操作），但是它会影响哈希表中的添加和搜索操作。为了减少重新哈希操作，我们应该明智地选择初始容量。如果初始容量大于最大条目数除以负载因子，将不会发生重新哈希操作。

注意： 在HashSet中的实现是不同步的，即如果多个线程同时访问一个哈希集，并且至少有一个线程修改了集合，那么必须在外部同步。通常通过对一些自然封装集合的对象进行同步来实现。如果没有这样的对象，则应使用Collections.synchronizedSet方法包装集合。最好在创建时完成，以防止意外的非同步访问集合，如下所示：

Set s = Collections.synchronizedSet(new HashSet(…));

与HashSet一起使用的方法

1. 从类java.util.AbstractSet继承的方法

2. 从类java.util.AbstractCollection继承的方法

3. 由接口java.util.Collection声明的方法

Java中HashSet常见问题解答

Q1. HashSet是什么？

答案：

HashSet是一种类，它扩展了AbstractSet并实现了Set接口。

Q2. 为什么使用HashSet？

答案：

HashSet用于避免重复数据，并使用快速的方法查找值。

Q3. HashSet和HashMap的区别。

答案：

Q4. Java中HashSet和TreeSet之间的区别。

答案：