不同的默认'initialCapacity'HashSet和LinkedHashSet

Question

从集合构造a HashSet和a时LinkedHashSet,initialCapacity在默认实现中将其设置为不同的值.

HashSet的:

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

LinkedHashSet:

public LinkedHashSet(Collection<? extends E> c) {
    super(Math.max(2*c.size(), 11), .75f, true);
    addAll(c);
}

我确信这有一个完全正确的理由,但我没有看到它.

Answer 1

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这样做的成本在和 plain中应该大致相同HashSet。 然而，aLinkedHashSet在扩展容量时有一个额外的要求，因为它维护一个贯穿条目的链表。在此过程中可能还需要重构此列表。因此，我预计扩大产能的成本会比LinkedHashSet普通的更高HashSet。通过提供LinkedHashSet更大的初始容量，我们可以在较长时间内避免这种代价高昂的容量扩张。

LinkedHashSet Javadoc