HashSet 如何维护桶？为此使用什么数据结构？

Question

当将具有不同 hashCode 的元素添加到 HashSet 时，必须添加一个新元素，对吗？这个新存储桶将添加到什么数据结构中？它是否再次诉诸某种数组并在每次添加新元素时调整其大小，从而使 HashSet O(n) 的添加和删除变得复杂？

在阅读了几篇文章后，我了解到 JDK 的某些实现使用 HashMap 作为 HashSet 的备份集合，但是 HashMap 用于此目的是什么？

Answer 1

您可以随时查看源代码。

在那里你会看到 HashMap 有一个桶数组：

transient Entry[] table;

每个桶本质上都是一个链表：

static class Entry<K,V> implements Map.Entry<K,V> {
         final K key;
         V value;
         Entry<K,V> next;
         final int hash;

该数组为您提供对给定哈希码的存储桶的恒定时间访问，然后您必须循环遍历该列表（希望该列表不超过一两个条目）：

final Entry<K,V> getEntry(Object key) {
         int hash = (key == null) ? 0 : hash(key.hashCode());
         for (Entry<K,V> e = table[indexFor(hash, table.length)];
              e != null;
              e = e.next) {
             Object k;
             if (e.hash == hash &&
                 ((k = e.key) == key || (key != null && key.equals(k))))
                 return e;
         }
         return null;
}

当将具有不同 hashCode 的元素添加到 HashSet 时，必须添加一个新元素，对吗？

当添加一个与现有元素具有相同 hashCode 的元素时，它将进入同一个桶（在链表的末尾）。

当添加具有新 hashCode 的元素时，它可能会也可能不会进入不同的存储桶（因为您拥有的 hashCode 比存储桶多得多）。

所有桶都是在 Map 大小调整时预先创建的。如果达到容量限制，则会使用更多存储桶调整其大小，并将所有内容放入新存储桶中。

这个新存储桶将添加到什么数据结构中？

不添加桶。有一个固定的桶数组。当您需要更多容量时，会使用更大的阵列重建整个结构。

它是否再次诉诸某种数组并在每次添加新元素时调整其大小，从而使 HashSet O(n) 的添加和删除变得复杂？

不是每次。理想情况下永远不会。只有当您错误计算容量并最终需要更多时。然后它变得昂贵，因为所有内容都被复制到一个新数组中。这个过程本质上与ArrayList相同。