Java 中 HashSet 的工作原理

Java Set 接口

Java Set 接口表示一组元素，这些元素排列得像数组。它不允许重复元素。当我们尝试添加已存在的元素到 Set 时，它将不会存储。它用于模拟数学上的集合抽象。

Java HashSet 类

Java HashSet 类表示一组元素（对象）。它不保证元素的顺序。它构造一个使用哈希表存储元素的集合。它包含唯一的元素。它继承了 AbstractSet 类。它还实现了 Set 接口。它使用一种称为哈希的技术来存储元素。HashSet 在 Java 中内部使用 HashMap。

假设我们想创建一个 HashSet 来存储一组字符串，然后创建对象如下：

其中 <String> 是泛型类型参数。它表示存储在 HashSet 中的元素类型。

HashSet 实现 Set 接口。它保证唯一性。这是通过将元素存储为键，而值始终相同来实现的。HashSet 没有检索 HashSet 中对象的方法。只有一种方法可以通过 Iterator 获取 HashSet 中的对象。当我们创建一个 HashSet 对象时，它内部会创建一个 HashMap 实例，其默认初始容量为 16。

HashSet 使用构造函数 HashSet(int capacity)，该函数表示 HashSet 中可以存储多少个元素。当需要存储更多元素时，容量可能会自动增加。

HashSet 使用另一个构造函数 HashSet(int capacity, float loadfactor)。这里，loadfactor 定义了 HashSet 容量将自动增加的点。例如，容量和 loadfactor 的乘积是 101*0.5=50.5。这意味着在向 HashSet 中存储第 50 个元素后；其容量将自动增加以存储更多元素。HashSet 的初始默认容量为 16。默认的 load factor 为 0.75。

HashSet 实现

下面，我们实现 add() 方法，该方法将元素添加到 HashSet 中。

输出

Set is [America, India, Russia]
Elements using iterator:
America
India
Russia

在以下示例中，我们尝试添加一些重复值。

输出

Set is [China, America, India, Russia]
Elements using iterator:
China
America
India
Russia

在上面的示例中，我们添加了一些重复值。我们可以观察到重复值并未存储在 HashSet 中。当我们向 Set 对象的 add() 方法传递重复元素时，它内部会返回 false。

这里，一个问题出现了，它是如何返回 false 的。当我们在 Java API i.e. rt.jar 中打开 HashSet 的 add() 方法实现时，我们会发现其中的代码如下：

在上面的代码中，对 add(object) 的调用在内部委托给 put(key, value)。其中 key 是我们传递的对象，value 是另一个对象，称为 PRESENT。它是 java.util.HashSet 中的一个常量。

我们通过 HashMap 在内部实现了 Set 的唯一性。当我们创建一个 HashSet 对象时，它会创建一个 HashMap 对象。我们知道 HashMap 中的每个键都是唯一的。所以，我们将参数传递给 add(E e) 方法。这里，我们需要将某个值与键关联。它会关联一个虚拟值（new Object()），由 Object 引用 PRESENT 来引用。

当我们像 hs.add("India") 这样向 HashSet 添加元素时，Java 内部所做的是，它会将该元素 E（此处为“India”）作为键放入 HashMap（在创建 HashSet 对象期间生成）。它还会放入一个虚拟值，即 Object 的对象被用作键的值。

HashMap 的 put 方法

关于 put(key, value) 方法的重要几点是：

• 如果键是唯一的并且已添加到 map 中，它将返回 null
• 如果键是重复的，它将返回该键的旧值。

当我们调用 HashSet 中的 add() 方法时，Java 内部会检查 map.put(key, value) 方法的返回值是否为 null。

• 如果 map.put(key, value) 方法返回 null，那么 map.put(e, PRESENT)==null 方法在内部将返回 true，并且该元素将被添加到 HashSet 中。
• 如果 map.put(key, value) 方法返回该键的旧值，那么 map.put(e, PRESENT)==null 方法在内部将返回 false，并且该元素将不会添加到 HashSet 中。

从 HashSet 中检索对象

我们使用 iterator() 方法从 HashSet 中检索对象。它是 **java.util.HashSet** 类的一个方法。它返回一个迭代器，用于备份 map.keySet().iterator() 方法返回的 Map。