Java中的HashSet内部实现或者HashSet如何在Java中内部工作是一个非常重要的面试问题。我们应该知道的一些重点是

• HashSet的后备数据结构是什么？HashSet在哪里存储其元素？
• HashSet中的add()方法如何工作？
• HashSet中的remove()方法如何工作？
• 如何从HashSet中检索元素？

在本文中，我们将介绍Java中HashSet的内部实现，并尝试解释上述要点。请注意，本文中提供的HashSet类的所有代码段均来自JDK 10.

由于HashSet内部使用HashMap进行操作，因此了解Java中的HashMap内部实现将对理解HashSet的内部实现有很大帮助。

HashSet在哪里存储其元素

Java内部的HashSet使用HashMap来存储其元素。在HashSet类中，定义了一个HashMap，用于存储其元素。

private transient HashMap<E,Object> map;

如果看到为HashSet定义的所有构造函数，则所有这些构造函数都会创建一个HashMap。

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

public HashSet(Collection<? extends E> c) {
  map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
  addAll(c);
}

public HashSet(int initialCapacity, float loadFactor) {
  map = new HashMap<>(initialCapacity, loadFactor);
}

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

HashSet中的初始容量，负载因子和存储桶

我们应该对术语"初始容量"，"负载因子"和"存储桶"有清楚的了解，以便更好地了解HashSet的内部实现。

如前所述，HashSet使用HashMap来存储其元素，而HashMap依次内部使用Node类型的数组来存储元素，其中Node <K，V>是HashMap类中的内部类。

• 容量–如果我们在创建HashSet时未指定任何容量，则该阵列的默认初始容量为16. 如果我们使用还传递了初始容量的构造函数，则该阵列将具有指定的初始容量。
• 桶-在HashMap中，桶的概念用于存储元素，其中数组的每个索引被概念化为一个桶。因此，总共有16个(默认情况下)存储桶。对于每个添加到HashSet的(值)，使用密钥计算哈希值，基于该哈希值，选择这些存储桶之一来存储元素。
• 负载系数–负载系数是HashSet存储的阈值。一旦达到阈值，HashSet的容量就会加倍。默认负载因子为0.75，这意味着如果达到了容量的75％，则将调整HashSet的大小。

Java HashSet中的添加方法如何工作

我们必须要考虑的是，如果HashSet在内部使用HashMap来添加元素，那么HashSet中的add(E e)方法为什么只将值作为参数而不是(键，值)对。毕竟，HashMap将其元素存储为(键，值)对。

在Java HashSet实现中；从add(E e)方法中，调用HashMap的put()方法以添加元素，并且HashSet也发送一个(键，值)对。内部发生的事情是，传递给添加到HashSet的值成为HashMap的键，并且始终将虚拟对象" PRESENT"作为值添加。

虚拟对象PRESENT在HashSet实现中定义如下：

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

add(E e)方法的实现如下：

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

在这里，我们可以看到传递用于存储在HashSet中的值成为HashMap中的键。实际上，这就是确保仅唯一值存储在HashSet中的方式。在HashMap中，值可以重复，但Key应该是唯一的。正如我们已经看到的那样，该值成为HashMap中保持唯一的键。

如何从HashSet中检索值

HashSet中没有方法来获取单个值。我们可以遍历HashSet并获取所有值。 HashSet的迭代器方法返回后备HashMap的keySet。我们已经看到添加到HashSet的值成为HashMap中的键，因此我们实际得到的是HashSet的值。

keySet()–返回此映射中包含的键的Set视图。

iterator()方法的实现如下

public Iterator<E> iterator() {
  return map.keySet().iterator();
}

如何从HashSet中删除值

为了删除值，会发生相同的互换。在调用支持HashMap的remove()方法时，我们在HashSet的remove()方法中提供的要删除的值成为关键。

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

在这里请注意，HashMap的remove方法返回与key关联的值。现在我们知道，将值添加到HashMap时始终将其作为" PRESENT"传递，这就是比较map.remove(o)== PRESENT;的原因。

重要说明

• HashSet由HashMap实例支持。
• 在HashSet的内部实现中，总是将虚拟对象" PRESENT"添加到支持HashMap的值。传递给添加到HashSet的值成为HashMap中的键。
• 为HashSet计算哈希值时，将使用值本身来计算哈希值，因为值已经在HashMap中。