Unterschiedlicher Standardwert 'initialCapacity' HashSet und LinkedHashSet

Question

Beim Erstellen eines HashSet und eines LinkedHashSet aus einer Sammlung wird der Wert initialCapacity in der Standardimplementierung auf andere Werte gesetzt.

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); 
} 

Ich bin sicher, dass es ein ganz triftiger Grund dafür ist, aber ich kann nicht, es zu sehen.

Answer 1

Aus dem Code, den Sie uns gezeigt, hier sind die Spezifikationen für HashSet und LinkedHashSet:

data structure | initial capacity  | load factor 
HashSet  | max(1.333 * size, 16) | 0.75 
LinkedHashSet | max(2 * size, 11)  | 0.75 

Aus der Spitze von meinem Kopf, es teurer ist wahrscheinlich eine LinkedHashSet als ein einfaches HashSet wieder aufzuwärmen, wie die Der ehemalige hat eine verknüpfte Liste, die auch neu strukturiert werden muss. Wenn wir die Anfangskapazität erhöhen, könnten wir die anfängliche Kapazität für einige typische Anwendungsfälle nicht überschreiten.

Wenn die Anfangskapazität einer Hashtabellen-Datenstruktur in Java überschritten wird, muss sie erweitert werden. Dies erfordert unter anderem, dass jeder Eintrag in der Tabelle zu einem neuen Bucket aufgeräumt werden muss. Die Kosten dafür sollten ungefähr gleich sein, sowohl in LinkedHashSet als auch in HashSet. Jedoch hat eine LinkedHashSet eine zusätzliche Anforderung, wenn die Kapazität erweitert wird, da es eine verknüpfte Liste verwaltet, die die Einträge durchläuft. Diese Liste muss möglicherweise auch in dem Prozess neu strukturiert werden. Daher würde ich erwarten, dass die Kosten für die Kapazitätserweiterung in LinkedHashSet höher liegen als in HashSet. Indem wir LinkedHashSet eine größere Anfangskapazität geben, können wir diese kostspielige Kapazitätserweiterung für eine längere Zeit vermeiden.

LinkedHashSet Javadoc