java - 不同的默认 'initialCapacity' HashSet 和 LinkedHashSet

Question

当从一个集合构造一个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);
}

我确信这有一个完全正当的理由，但我没有看到。

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

LinkedHashSet Javadoc