HashSet vs. ArrayList Die CPU-Auslastung ist hoch

Meine Vermutung ist, dass HashSet , da es sich um eine Hash-basierte Struktur handelt, den hashCode jedes Strings seit dem Moment des Einfügens in das HashSet berechnet, d. h. in der Methode init . Dies kann der Zeitraum sein, in dem die CPU hoch geht, und es ist Teil des Preises, den wir dafür zahlen, einen besseren Durchsatz beim Iterieren der Werte der Struktur zu erhalten.

Wenn ich recht habe, sollte nach dem Beenden der Methode init die CPU abfallen, und die Geschwindigkeit des Programms sollte enorm steigen, und das ist der Vorteil von HashSet.

Übrigens: Eine sichere Art der Optimierung ist die Vordimensionierung der Struktur:

• ArrayList sollte eine anfängliche Größe haben, die der maximalen Anzahl der Elemente entspricht, die enthalten sind.
• Und HashSetze eine Anfangsgröße von 1,7 größer als das Maximum.

BTW: Der Standard-Hashalgorithmus von String.hash berechnet alle Zeichen der Zeichenfolge. Vielleicht könnten Sie sich damit zufrieden geben, nur die ersten 100 Zeichen zu berechnen (abhängig von der Art der Daten, die Sie gerade bearbeiten). Dann könnten Sie Ihre Strings in Ihre eigene Klasse kapseln, indem Sie die hashCode -Methode mit Ihrem eigenen Hash-Algorithmus überschreiben und die equals -Methode überschreiben, um eine strikte Vergleichung durchzuführen.

Ich habe eine einfache Klasse erstellt, um 20 Threads zu erzeugen, die jede Sekunde auf den Wörterbuch-Checker zugreifen, wie es am Ende dieses Posts steht.

Ich kann Ihre Ergebnisse nicht replizieren. Dies liegt möglicherweise an den Eingabedaten, auf die ich Zugriff habe. Ich habe Ihre TestClass Implementierung verwendet, um ~ 130.000 Wörter aus der englischen Open Word List zu importieren ( EOWL ). Es wird keine fortlaufende hohe CPU-Auslastung mit ArrayList oder HashSet als Typ von stringList festgestellt.

Ich vermute, dass Ihr Problem auf Ihre Eingabedaten zurückzuführen ist. Ich habe versucht, mein Eingabewörterbuch zweimal hinzuzufügen, um Duplikate zu erstellen - offensichtlich mit ArrayList , das macht die Liste doppelt so lang, aber mit HashSet bedeutet das, dass der Code Duplikate verwirft. Sie stellen fest, dass etwa 1/5 Ihrer Eingabedaten doppelt vorhanden sind. Mit 1/2 Duplikaten in meinen Tests sehe ich eine leichte erhöhte CPU für etwa 2 Sekunden und dann fällt sie wieder auf fast nichts, wenn stringList initialisiert ist.

Dieser "Blip" könnte länger dauern, wenn Ihre Eingabezeichenfolgen komplexer sind als die einzelnen Wörter, die ich verwende. Vielleicht ist das dein Problem. Alternativ - vielleicht haben Sie einen anderen Code, der diesen Teil umhüllt, der die CPU belastet.

N.B. Ich würde Sie warnen, wie andere Kommentare zu Ihrer Implementierung von init haben. In meinen Experimenten sah ich, dass viele Threads die Wörterbuchprüfung aufrufen konnten, bevor das Wörterbuch vollständig initialisiert wurde, was zu inkonsistenten Ergebnissen für das gleiche Testwort führte. Warum nicht aus dem Konstruktor aufrufen, wenn es ein Singleton-Objekt sein soll?

Code-Listen

Ihre TestClass mit einigen Eingabedaten:

Thread, um darauf zuzugreifen:

JDK HashSet basiert auf einem HashMap<T, Object> , wobei Wert ein Singleton 'vorhandenes' Objekt ist. Dies bedeutet, dass der Speicherverbrauch eines HashSets mit HashMap identisch ist: Um SIZE-Werte zu speichern, benötigen Sie 32 * SIZE + 4 * CAPACITY bytes (plus Größe Ihrer Werte).

Für ArrayList ist dies die Kapazität der java.util.ArrayList multipliziert mit der Referenzgröße (4 bytes on 32bit, 8bytes on 64bit) + [Object header + one int and one references] .

Also HashSet ist definitiv keine speicherfreundliche Sammlung.

Hängt davon ab, ob Sie eine 32-bit oder eine 64-bit VM verwenden. Allerdings wird HashSet durch 8-byte references schlechter getroffen als ArrayList - das Hinzufügen eines zusätzlichen 4 bytes pro Verweis, basierend auf dem verknüpften Speicherverbrauchsdiagramm, bringt ArrayList auf ~12 bytes pro Element und HashSet bis ~52 bytes pro Element.)

ArrayList wird mit einem Array von Objekten implementiert. Die folgende Abbildung zeigt die Speichernutzung und das Layout einer ArrayList auf einer 32-Bit-Java-Laufzeitumgebung:

Speichernutzung und Layout einer ArrayList auf einer 32-Bit-Java-Laufzeitumgebung

Die obige Abbildung zeigt, dass bei der Erstellung eines ArrayList ein ArrayList -Objekt mit 32 bytes des Speichers zusammen mit einem Objekt-Array mit einer Standardgröße von 10 , insgesamt 88 bytes von Speicher für eine leere ArrayList . Dies bedeutet, dass ArrayList nicht genau skaliert ist und daher eine Standardkapazität hat, die zufällig 10 entries ist.

Attribute einer ArrayList

Default capacity - 10

Empty size - 88 Bytes

Overhead - 48 Bytes plus 4 Bytes pro Eintrag

Overhead für 10K Sammlung - ~ 40K

Search/insert/delete performance - O (n) - Die Zeit ist linear abhängig von der Anzahl der Elemente

Ein HashSet verfügt über weniger Funktionen als eine HashMap, da es nicht mehr als einen Nulleintrag enthalten kann und keine doppelten Einträge enthalten kann. Die Implementierung ist ein Wrapper um eine HashMap, wobei das HashSet-Objekt verwaltet, was in das HashMap-Objekt eingefügt werden darf. Die zusätzliche Funktion der Einschränkung der Fähigkeiten einer HashMap bedeutet, dass HashSets einen etwas höheren Speicheraufwand haben.

Speichernutzung und Layout eines HashSet auf einer 32-Bit-Java-Laufzeitumgebung

Die obige Abbildung zeigt den flachen Heap (Speicherbelegung des einzelnen Objekts) in Byte zusammen mit dem beibehaltenen Heap (Speicherbelegung des einzelnen Objekts und seiner untergeordneten Objekte) in Byte für ein java.util.HashSet-Objekt. Die flache Heap-Größe ist 16 bytes und die beibehaltene Heap-Größe ist 144 bytes . Wenn ein HashSet erstellt wird, ist seine Standardkapazität - die Anzahl der Einträge, die in den Satz eingefügt werden können - 16 entries . Wenn ein HashSet mit der Standardkapazität erstellt wird und keine Einträge in den Satz eingefügt werden, belegt es 144 bytes . Dies ist eine zusätzliche 16 bytes gegenüber der Speicherauslastung einer HashMap.

Die folgende Tabelle zeigt die Attribute eines HashSets:

Attribute eines HashSets

Default capacity - 16 Einträge

Empty size - 144 Bytes

Overhead - 16 Bytes plus HashMap-Overhead

Overhead for a 10K collection - 16 Bytes plus HashMap-Overhead

Search/insert/delete performance - O (1) - Die Zeit ist eine konstante Zeit, unabhängig von der Anzahl der Elemente (unter der Annahme, keine Hash-Kollisionen)