Verschiedene Standard 'initialCapacity' HashSet und LinkedHashSet

9

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

HashSet:

%Vor%

LinkedHashSet:

%Vor%

Ich bin mir sicher, dass es einen vollkommen gültigen Grund dafür gibt, aber ich sehe es nicht.

    
marthursson 17.01.2017, 08:27
quelle

1 Antwort

4

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

%Vor%

In meinem Kopf ist es wahrscheinlich kostspieliger, ein LinkedHashSet als reines HashSet zu reashashen, da erstere eine verknüpfte Liste durchläuft, die möglicherweise auch neu strukturiert / neu berechnet 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 in LinkedHashSet und plain HashSet ungefähr gleich sein. Allerdings muss eine LinkedHashSet eine zusätzliche Anforderung beim Erweitern der Kapazität erfüllen, da sie 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 den Kapazitätsausbau in LinkedHashSet höher sind als in plain HashSet . Indem wir eine höhere Anfangskapazität geben, können wir diese kostspielige Kapazitätserweiterung für längere Zeit vermeiden.

LinkedHashSet Javadoc

    
Tim Biegeleisen 17.01.2017, 08:39
quelle

Tags und Links