Warum haben verschiedene Java-Sammlungen unterschiedliche Standardkapazitäten?

11

Bei der Betrachtung verschiedener Sammlungskonstruktoren stellt sich die Frage. Warum erstellt ArrayList () eine leere Liste mit einer Anfangskapazität von zehn und ArrayDeque () erstellt eine leere Array-Deque mit einer Anfangskapazität, die ausreicht, um 16 Elemente aufzunehmen.

java collections Alter Badman Gray
quelle
Ich war nicht neu, hatte aber ein Kapazitätslimit. Ich füge einfach neue Elemente mit add () hinzu. Es funktioniert immer.
Tulains Córdova
1
Ich denke, er spricht über die anfängliche Arraygröße des Arrays in der ArrayList-Implementierung. Wie der Name schon sagt, ist ArrayList nur ein einfaches altes Array unter der Decke und erstellt automatisch größere Arrays, wenn Sie versuchen, mehr Elemente hinzuzufügen, als die aktuelle Arraygröße enthält.
dsw88
1
Ich denke, StringBuilder ist eine andere, die eine Standardkapazität hat, war es 10 oder 16?
Ingo
@Ingo Interessant. Ich war mir nicht einmal bewusst, dass Dinge außerhalb von Sammlungen mit Kapazitäten überfüllt waren, aber ich nehme an, dass dies sinnvoll ist. Zu der Zeit gab es kein Tag für Kapazität, so dass ich kein großes Interesse an anderen Verwendungszwecken weckte.
Alter Badman Gray

Antworten:

17

Kurze Antwort

Da die ArrayDeque-Kapazität eine Zweierpotenz sein muss und 16 die kleinste Zweierpotenz ist, die mindestens 10 beträgt.

ArrayDeque muss überall viele% -Operationen verwenden, um ein lineares Array zu umschließen, das vorgibt, kreisförmig zu sein.

a % bkann ausgedrückt werden als a & (b - 1) ob b eine Zweierpotenz ist. Das bitweise UND ist massiv schneller, sodass die Kapazität von ArrayDeque auf die Zweierpotenz beschränkt ist. Alle% -Operationen werden in der Implementierung mit Bitmasking anstelle des tatsächlichen% ausgeführt.

Dies ist auch der Grund, warum die neuere HashMap keine Primzahlentabellengrößen, sondern eine Zweierpotenz verwendet , da die% -Operation so oft und bitweise ausgeführt werden muss und so viel schneller ist.

Wenn die Basislinie 10 ist, sollten Strukturen mit einer Potenz von zwei Einschränkungen 16 verwenden, da es die kleinste Potenz von zwei ist, die mindestens 10 beträgt.

Esailija
quelle
3

Schließen Sie nicht aus, dass es keinen bestimmten Grund gibt.

Es könnte sein, dass diese beiden Sammlungen von verschiedenen Teams geschrieben wurden. Beide wählten eine kleine Zahl als Standardkapazität, aber das erste Team dachte dezimal und wählte 10, während das zweite Team binär dachte und 16 wählte.

rem
quelle
1

@ Esailijas Antwort ist gut für diesen speziellen Fall.

Im Allgemeinen ist es jedoch ein Kompromiss, der von vielen Faktoren abhängt. Ich werde einige Beispiele nennen:

  • Wie wird die Datenstruktur normalerweise verwendet ? Datenstrukturen, die als Datenpuffer verwendet werden, bevorzugen typischerweise eine viel höhere Kapazität als Datenstrukturen, die beispielsweise für kleine Tupel verwendet werden.
  • Welche Standarddatengröße passt in eine Cache-Zeile auf Ihrer Ziel-CPU-Plattform? Es kann einen großen Unterschied für die Leistung bedeuten, wenn die Standardeinstellung in die Cache-Zeile passt. Die Auswahl von 10 ist in Java standardmäßig möglich, da ein Array mit 10 32-Bit-Wörtern plus dem Array- / Objekt-Overhead in eine 64-Byte-Cache-Zeile passt.
  • Wie viel schätzen Sie Speicherplatz im Vergleich zur Laufzeiteffizienz ? Wenn Sie eine bessere Laufzeitleistung wünschen, ist es im Allgemeinen besser, mehr Speicherplatz vorab zuzuweisen, um später zusätzliche Neuzuweisungen zu vermeiden.

Aufgrund dieser Kompromisse ist es durchaus verständlich, dass verschiedene Erfassungsimplementierungen unterschiedliche optimale Standardkapazitäten aufweisen können.

mikera
quelle