Java HashSet

HashSet 类实现了Set接口，由一个实际上是HashMap实例的散列表支持。该类不保证集合的迭代顺序，也就是说，该类不保证元素的顺序随时间的推移而不变。这个类允许空元素的存在。该类还为基本操作提供了恒定的时间性能，如添加、删除、包含和大小，假设散列函数在桶中正确地分散了元素，我们将在文章中进一步看到这一点。

HashSet的几个重要特征是

• 实现了Set接口。
• HashSet的底层数据结构是Hashtable。
• 因为它实现了Set接口，所以不允许有重复的值。
• 你在HashSet中插入的对象并不保证以相同的顺序插入。对象是根据它们的哈希代码插入的。
• 在HashSet中允许有NULL元素。
• HashSet也实现了 Serializable 和 Cloneable 接口。

HashSet的层次结构 如下。

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

现在为了保持恒定的时间性能，迭代HashSet需要的时间与HashSet实例的大小（元素的数量）加上支持HashMap实例的 “容量”（桶的数量）之和成比例。因此，如果迭代性能很重要的话，不要把初始容量设置得太高（或者负载因子太低），这是非常重要的。

• 初始容量： 初始容量是指创建hashable（HashSet内部使用hashable数据结构）时的桶的数量。如果当前容量已满，桶的数量会自动增加。

• 负载因子： 负载因子是衡量HashSet在自动增加容量之前允许达到的满度。当哈希表中的条目数超过负载因子和当前容量的乘积时，哈希表会被重新洗牌（也就是重建内部数据结构），这样哈希表就有大约两倍的桶数。

                  Number of stored elements in the table
Load Factor = -----------------------------------------
                        Size of the hash table 

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

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

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

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

语法： HashSet的声明

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

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

HashSet的内部工作： Set接口的所有类在内部都有Map的支持。HashSet在内部使用HashMap来存储其对象。你一定想知道，在HashMap中输入一个值，我们需要一个键值对，但是在HashSet中，我们只传递一个值。

HashMap中的存储： 实际上，我们在HashSet中插入的值是作为地图对象的一个键，对于它的值，java使用一个常量变量。所以在键值对中，所有的值都是一样的。

HashSet在Java中的实现 doc

private transient HashMap map;

// Constructor - 1
// All the constructors are internally creating HashMap Object.
public HashSet()
{
    // Creating internally backing HashMap object
    map = new HashMap();
}

// Constructor - 2
public HashSet(int initialCapacity)
{
    // Creating internally backing HashMap object
    map = new HashMap(initialCapacity);
}

// Dummy value to associate with an Object in Map
private static final Object PRESENT = new Object();

如果我们看一下HashSet类的add()方法。

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

我们可以注意到，HashSet类的add()方法在内部调用了支持HashMap对象的put()方法，将你指定的元素作为键，常量 “PRESENT “作为其值。 remove()方法也以同样的方式工作。它在内部调用Map接口的remove方法。

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

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

实现

// 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，我们需要创建一个HashSet类的对象。HashSet类由各种构造函数组成，允许创建HashSet的可能性。以下是该类中可用的构造函数。

1.HashSet() : 这个构造函数用于建立一个空的HashSet对象，其中默认的初始容量为16，默认的负载因子为0.75。如果我们希望创建一个名字为hs的空HashSet，那么可以这样创建。

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

2.HashSet(int initialCapacity): 这个构造函数用来建立一个空的HashSet对象，其中initialCapacity是在创建对象时指定的。这里，默认的loadFactor仍然是0.75。

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

3.HashSet(int initialCapacity, float loadFactor): 这个构造函数用于建立一个空的HashSet对象，其中initialCapacity和loadFactor在对象创建时被指定。

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

4.HashSet(Collection): 这个构造函数用来建立一个HashSet对象，其中包含来自给定集合的所有元素。简而言之，当需要从任何集合对象转换到HashSet对象时，就会使用这个构造函数。如果我们希望创建一个名字为hs的HashSet，可以这样创建。

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

实现 。

// Java program to Demonstrate Working of HashSet Class
  
// Importing required classes
import java.util.*;
  
// Main class
// HashSetDemo
class GFG {
  
    // Main driver method
    public static void main(String[] args)
    {
  
        // Creating an empty HashSet
        HashSet<String> h = new HashSet<String>();
  
        // Adding elements into HashSet
        // using add() method
        h.add("India");
        h.add("Australia");
        h.add("South Africa");
  
        // Adding duplicate elements
        h.add("India");
  
        // Displaying the HashSet
        System.out.println(h);
        System.out.println("List contains India or not:"
                           + h.contains("India"));
  
        // Removing items from HashSet
        // using remove() method
        h.remove("Australia");
        System.out.println("List after removing Australia:"
                           + h);
  
        // Display message
        System.out.println("Iterating over list:");
  
        // Iterating over hashSet items
        Iterator<String> i = h.iterator();
  
        // Holds true till there is single element remaining
        while (i.hasNext())
  
            // Iterating over elements
            // using next() method
            System.out.println(i.next());
    }
}

输出

[South Africa, Australia, India]
List contains India or not:true
List after removing Australia:[South Africa, India]
Iterating over list:
South Africa
India

对HashSet进行各种操作

让我们看看如何在HashSet上执行一些常用的操作。

操作1： 添加元素

为了向HashSet添加一个元素，我们可以使用add()方法。然而，在HashSet中并不保留插入的顺序。 我们需要注意的是，重复的元素是不允许的，所有重复的元素都会被忽略掉。

例子

// Java program to Adding Elements to HashSet
  
// Importing required classes
import java.io.*;
import java.util.*;
  
// Main class
// AddingElementsToHashSet
class GFG {
  
    // Method 1
    // Main driver method
    public static void main(String[] args)
    {
        // Creating an empty HashSet of string entities
        HashSet<String> hs = new HashSet<String>();
  
        // Adding elements using add() method
        hs.add("Geek");
        hs.add("For");
        hs.add("Geeks");
  
        // Printing all string el=ntries inside the Set
        System.out.println("HashSet elements : " + hs);
    }
}

输出

HashSet elements : [Geek, For, Geeks]

操作2： 移除元素

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

例子

// Java program Illustrating Removal Of Elements of HashSet
  
// Importing required classes
import java.io.*;
import java.util.*;
  
// Main class
// RemoveElementsOfHashSet
class GFG {
  
    // Main driver method
    public static void main(String[] args)
    {
        // Creating an
        HashSet<String> hs = new HashSet<String>();
  
        // Adding elements to above Set
        // using add() method
        hs.add("Geek");
        hs.add("For");
        hs.add("Geeks");
        hs.add("A");
        hs.add("B");
        hs.add("Z");
  
        // Printing the elements of HashSet elements
        System.out.println("Initial HashSet " + hs);
  
        // Removing the element B
        hs.remove("B");
  
        // Printing the updated HashSet elements
        System.out.println("After removing element " + hs);
  
        // Returns false if the element is not present
        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循环。

例子

// Java Program to Illustrate Iteration Over HashSet
  
// Importing required classes
import java.io.*;
import java.util.*;
  
// Main class
// IterateTheHashSet
class GFG {
  
    // Main driver method
    public static void main(String[] args)
    {
  
        // Creating an empty HashSet of string entries
        HashSet<String> hs = new HashSet<String>();
  
        // Adding elements to above Set
        // using add() method
        hs.add("Geek");
        hs.add("For");
        hs.add("Geeks");
        hs.add("A");
        hs.add("B");
        hs.add("Z");
  
        // Iterating though the HashSet using iterators
        Iterator itr = hs.iterator();
  
        // Holds true till there is single element
        // remaining in Set
        while (itr.hasNext())
  
            // Traversing elements and printing them
            System.out.print(itr.next() + ", ");
        System.out.println();
  
        // Using enhanced for loop for traversal
        for (String s : hs)
  
            // Traversing elements and printing them
            System.out.print(s + ", ");
        System.out.println();
    }
}

输出

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

HashSet操作的时间复杂度： HashSet的底层数据结构是散列的。因此，HashSet的添加、删除和查找（包含方法）操作的摊销（平均或通常情况下）时间复杂度需要O ( 1)时间。

HashSet中的方法

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

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

java.util.Collection接口中声明的方法

HashSet vs HashMap

HashSet vs TreeSet