<分区>
当将具有不同 hashCode 的元素添加到 HashSet 时，是否需要添加一个新元素，对吗？这个新桶会添加到什么数据结构中？它是否再次求助于某种数组并在每次添加新元素时调整其大小从而使添加和删除到 HashSet O(n) 复杂？
看了一些帖子后，我了解到一些 JDK 的实现使用 HashMap 作为 HashSet 的备份集合，那么 HashMap 有什么用呢？
<分区>
当将具有不同 hashCode 的元素添加到 HashSet 时，是否需要添加一个新元素，对吗？这个新桶会添加到什么数据结构中？它是否再次求助于某种数组并在每次添加新元素时调整其大小从而使添加和删除到 HashSet O(n) 复杂？
看了一些帖子后，我了解到一些 JDK 的实现使用 HashMap 作为 HashSet 的备份集合，那么 HashMap 有什么用呢？
最佳答案
你总是可以look at the source code .
在那里你会看到 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;
}
When an element with a different hashCode is added to a HashSet, a new got to be added right?
当添加一个与现有元素具有相同 hashCode 的元素时，它将进入同一个桶(在链表的末尾)。
添加具有新哈希代码的元素时，它可能会或可能不会转到不同的存储桶(因为您的哈希代码比存储桶多得多)。
所有的bucket都是在Map调整大小时预先创建的。如果达到容量限制，则会使用更多存储桶调整其大小，并将所有内容放入新存储桶中。
To what data structure would this new bucket be added?
不添加桶。有一个固定的桶阵列。当您需要更多容量时，将使用更大的阵列重建整个结构。
Does it again resort to some sort of array and resizes that each time a new element is added thus making the addition and deletion into the HashSet O(n) complex?
不是每次。理想情况下永远不会。仅当您错误计算容量并最终需要更多容量时。然后它变得昂贵，因为所有内容都被复制到一个新数组中。这个过程与 ArrayList 基本相同。
关于java - HashSet 如何维护桶？什么数据结构用于此？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15286710/