当从一个集合构造一个HashSet
和一个LinkedHashSet
时,initialCapacity
在默认实现中被设置为不同的值。
哈希集:
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
链接哈希集:
public LinkedHashSet(Collection<? extends E> c) {
super(Math.max(2*c.size(), 11), .75f, true);
addAll(c);
}
我确信这有一个完全正当的理由,但我没有看到。
最佳答案
根据您向我们展示的代码,以下是 HashSet
和 LinkedHashSet
的规范:
data structure | initial capacity | load factor
HashSet | max(1.333 * size, 16) | 0.75
LinkedHashSet | max(2 * size, 11) | 0.75
在我的脑海中,重新散列 LinkedHashSet 可能比普通 HashSet 的成本更高,因为前者有一个链表贯穿其中,可能还需要重构/重新计算。通过增大初始容量,我们可以避免超出某些典型用例的初始容量。
在Java中,当哈希表数据结构的初始容量超过时,就需要对其进行扩容。除其他事项外,这要求表中的每个条目都需要重新散列到一个新的桶中。这样做的成本在 LinkedHashSet
和普通 HashSet
中应该大致相同。 但是, LinkedHashSet
在扩展容量时有一个额外的要求,因为它维护了一个贯穿条目的链表。此列表可能还需要在此过程中进行重构。因此,我预计 LinkedHashSet
中扩展容量的成本会高于普通 HashSet
。通过为 LinkedHashSet
提供更大的初始容量,我们可以在更长时间内避免这种代价高昂的容量扩展。
关于java - 不同的默认 'initialCapacity' HashSet 和 LinkedHashSet,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41692230/