3

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

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

4

3 回答 3

5

您可以随时查看源代码。

在那里你会看到 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 比存储桶多）。

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

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

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

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

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

于 2013-03-08T04:28:13.563 回答
0

即使只是阅读HashSet和HashMap的 Javadoc 也可以收集到很多信息。HashSet 由 HashMap 支持。

根据 HashMap Javadoc，它由初始容量和负载因子定义。在超过负载因子之前不会调整后备哈希表的大小，因此要回答您的一个问题，不，不会在地图中的每次新添加/删除时都发生调整大小。

于 2013-03-08T04:31:40.797 回答
0

HashMap使用数组Map.Entry：数组中的元素是一对key,value。

插入元素时，根据哈希码计算桶的位置。如果插入的密钥与存储在桶中的密钥不同（哈希码冲突），则选择下一个空桶。该算法的结果是，在数组“几乎已满”的哈希映射上的操作将相当昂贵：实际上，如果只有一个空闲桶，它们将是 O(n)。

为了避免这个问题，HashMap当它的当前计数大于内部阵列容量的某个百分比时自动调整大小（“负载因子”，默认为 75%）。这意味着一个 75 个元素HashMap将被一个 100 个元素的数组烘焙。降低负载因子会增加内存开销，但会使平均执行顺序偏向接近恒定。

请注意，如果每个元素都具有相同的 hashCode，最坏情况下的插入可能仍然是 O(n)。

于 2013-03-08T04:39:17.653 回答