Wie berechnet man den Speicherverbrauch einer HashMap in Java?

Question

Ich wurde in einem Vorstellungsgespräch gebeten, den Speicherverbrauch für HashMap und wie viel Speicherplatz sie schätzungsweise verbrauchen wird, wenn Sie 2 Millionen Einträge darin haben.

Zum Beispiel:

Map <String,List<String>> mp=new HashMap <String,List<String>>();

Das Mapping sieht folgendermaßen aus.

key   value
----- ---------------------------
abc   ['hello','how']
abz   ['hello','how','are','you']

Wie kann ich den Speicherverbrauch dieses HashMap-Objekts in Java abschätzen?

Answer 1

Die kurze Antwort

Um herauszufinden, wie groß ein Objekt ist, würde ich einen Profiler verwenden. In YourKit können Sie zum Beispiel nach dem Objekt suchen und es dann dazu bringen, seine Größe zu berechnen. So erhalten Sie eine ungefähre Vorstellung davon, wie viel Speicherplatz verbraucht würde, wenn das Objekt eigenständig wäre, und dies ist eine konservative Größe für das Objekt.

Die Spitzfindigkeiten

Wenn Teile des Objekts in anderen Strukturen wiederverwendet werden, z. B. in String-Literalen, wird nicht so viel Speicherplatz frei, wenn man es verwirft. Das Verwerfen eines Verweises auf die HashMap könnte sogar überhaupt keinen Speicher freigeben.

Was ist mit der Serialisierung?

Die Serialisierung des Objekts ist ein Ansatz, um eine Schätzung zu erhalten, aber sie kann sehr ungenau sein, da der Serialisierungs-Overhead und die Kodierung im Speicher und in einem Byte-Stream unterschiedlich sind. Wie viel Speicher verwendet wird, hängt von der JVM ab (und davon, ob sie 32/64-Bit-Referenzen verwendet), aber das Serialisierungsformat ist immer dasselbe.

z.B..

In der JVM von Sun/Oracle kann ein Integer 16 Bytes für den Header, 4 Bytes für die Zahl und 4 Bytes Padding (die Objekte sind im Speicher 8-Byte-ausgerichtet), insgesamt 24 Bytes, benötigen. Wenn Sie jedoch einen Integer serialisieren, benötigt er 81 Bytes, serialisieren Sie zwei Integer, benötigen sie 91 Bytes, d.h. die Größe des ersten Integers ist aufgebläht und der zweite Integer ist kleiner als der Speicherplatz.

String ist ein viel komplexeres Beispiel. In der Sun/Oracle JVM enthält er 3 int Werte und eine char[] Hinweis. Sie können also davon ausgehen, dass es 16 Byte Header plus 3 * 4 Byte für die int s, 4 Bytes für die char[] , 16 Bytes für den Overhead der char[] und dann zwei Bytes pro Zeichen, ausgerichtet an der 8-Byte-Grenze...

Welche Flaggen können die Größe verändern?

Wenn Sie 64-Bit-Referenzen haben, wird die char[] Referenz ist 8 Byte lang, was 4 Byte Auffüllung bedeutet. Wenn Sie eine 64-Bit-JVM haben, können Sie +XX:+UseCompressedOops um 32-Bit-Referenzen zu verwenden. (Ein Blick auf die Bitgröße der JVM allein sagt also nichts über die Größe der Referenzen aus)

Wenn Sie eine -XX:+UseCompressedStrings verwendet die JVM ein Byte[] anstelle eines Char-Arrays, wenn sie kann. Dies kann Ihre Anwendung etwas verlangsamen, aber den Speicherverbrauch drastisch verbessern. Wenn ein byte[] verwendet wird, beträgt der Speicherverbrauch 1 Byte pro Zeichen ;) Hinweis: Bei einem 4-Zeichen-String, wie im Beispiel, ist die verwendete Größe aufgrund der 8-Byte-Grenze gleich.

Was meinen Sie mit "Größe"?

Wie bereits erwähnt, sind HashMap und List komplexer, da viele, wenn nicht alle, Strings wiederverwendet werden können, möglicherweise String-Literale. Was Sie mit "Größe" meinen, hängt davon ab, wie sie verwendet wird, d. h. wie viel Speicher würde die Struktur allein verbrauchen? Wie viel würde frei werden, wenn die Struktur verworfen würde? Wie viel Speicher wird benötigt, wenn Sie die Struktur kopieren? Auf diese Fragen kann es unterschiedliche Antworten geben.

Was können Sie ohne einen Profiler tun?

Wenn Sie feststellen können, dass die wahrscheinliche konservative Größe klein genug ist, spielt die genaue Größe keine Rolle. Im konservativen Fall müssen Sie wahrscheinlich jede Zeichenfolge und jeden Eintrag von Grund auf neu konstruieren. (Ich sage nur wahrscheinlich, da eine HashMap 1 Milliarde Einträge fassen kann, obwohl sie leer ist. Strings mit einem einzigen Zeichen können ein Sub-String eines Strings mit 2 Milliarden Zeichen sein)

Sie können ein System.gc() ausführen, den freien Speicher entnehmen, die Objekte erstellen, ein weiteres System.gc() ausführen und sehen, um wie viel sich der freie Speicher verringert hat. Möglicherweise müssen Sie das Objekt viele Male erstellen und einen Durchschnitt ermitteln. Wiederholen Sie diese Übung viele Male, aber sie kann Ihnen einen guten Eindruck vermitteln.

(BTW Während System.gc() nur ein Hinweis ist, führt die Sun/Oracle JVM standardmäßig jedes Mal eine vollständige GC durch)

Answer 2

Ich denke, dass die Frage geklärt werden sollte, weil es einen Unterschied zwischen der Größe der HashMap und der Größe der HashMap + der in der HashMap enthaltenen Objekte gibt.

Betrachtet man die Größe der HashMap, so speichert die HashMap in dem von Ihnen genannten Beispiel einen Verweis auf die Zeichenfolge "aby" und einen Verweis auf die Liste. Die mehreren Elemente in der Liste spielen also keine Rolle. Nur der Verweis auf die Liste wird im Wert gespeichert.

In einer 32-Bit-JVM hat ein Map-Eintrag 4 Bytes für die "aby"-Referenz + 4 Bytes für die List-Referenz + 4 Bytes für die int-Eigenschaft "hashcode" des Map-Eintrags + 4 Bytes für die "next"-Eigenschaft des Map-Eintrags.

Sie fügen auch die 4*(X-1) Bytes Referenzen hinzu, wobei "X" die Anzahl der leeren Buckets ist, die die HashMap beim Aufruf des Konstruktors erstellt hat new HashMap<String,List<String>>() . Nach http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html sollte es 16 sein.

Es gibt auch loadFactor, modCount, threshold und size, die alle primitive int-Typen (16 Bytes mehr) und Header (8 Bytes) sind.

Die Größe der obigen HashMap würde also 4 + 4 + 1 + (4*15) + 16 + 8 = 93 Bytes betragen.

Dies ist eine Annäherung auf der Grundlage von Daten, die der HashMap gehören. Ich denke, dass der Interviewer vielleicht daran interessiert war, zu sehen, ob Sie sich der Funktionsweise der HashMap bewusst sind (z. B. die Tatsache, dass der Standardkonstruktor ein Array von 16 Buckets für den Map-Eintrag erstellt, die Tatsache, dass die Größe der in der HashMap gespeicherten Objekte keinen Einfluss auf die Größe der HashMap hat, da sie nur die Referenzen speichert).

HashMap sind so weit verbreitet, dass es sich unter bestimmten Umständen lohnen sollte, die Konstruktoren mit Anfangskapazität und Belastungsfaktor zu verwenden.

Answer 3

Summary:

memory = hashmap_array_size*bucket_size
+ n*chained_list_node_size
+ sum(key string sizes)
+ sum(list_string_size(string_list) for each hashmap List<String> value)

= 254 MB
(theoretical in-interview estimate)

Test program total-memory-used-size for 2 million sample entries: (see below)
= 640 MB
(I recommend a simple test program like this for a quick true-total-size estimate)

Eine minimale Schätzung (die tatsächliche Umsetzung ist wahrscheinlich etwas aufwändiger):

Angenommene Datenstruktur:

Bucket: (Pointer to String key, Pointer to hash-chain-list first-node)

Chained List Node: (Pointer to List<String> value, Next-pointer)
(HashMap is a chained hash - each bucket has a list/tree of values)
(as of Java 8, the list switches to a tree after 8 items)

List<String> instance: (Pointer to first node)

List<String> Node: (Pointer to String value, Next-pointer)

Annahme zur Vereinfachung dieser Schätzung: Null Kollisionen, jeder Bereich hat maximal 1 Wert (fragen Sie den Interviewer, ob dies in Ordnung ist - um eine grobe, erste Antwort zu geben)

Vermutung: 64-Bit-JVM, also 64-Bit-Zeiger, also pointer_size=8 Bytes

Vermutung: Das der HashMap zugrunde liegende Array ist zu 50 % gefüllt (standardmäßig wird die HashMap bei 75 % Füllung mit der doppelten Größe neu aufbereitet), also hashmap_array_size = 2*n

memory = hashmap_array_size*bucket_size
+ n*chained_list_node_size
+ sum(key string sizes)
+ sum(list_string_size(string_list) for each hashmap List<String> value)

So:

memory = (n*2)*(8*2)
+ n*(8*2) + ((2 length_field + 3 string_length)*n)
+ (n*(8 + 3*(8*2)
+ 3*(2 length_field + 4 string_length))
= 2000000*(2*8*2 + 8*2 + (2+3) + (8 + 3*8*2 + 3*(2+4)))
= 254000000
= 254 MB

n = number of items in the hash map

bucket_size = pointer_size*2

chained_list_node_size = pointer_size*2

list_string_size(list) = pointer_size +
list.size()*list_string_node_size
+ sum(string value sizes in this List<String> list)

list_string_node_size = pointer_size*2

String length bytes = length_field_size + string_characters
(UTF-8 is 1 byte per ascii character)
(length_field_size = size of integer = 2)

Assume all keys are length 3.
(we have to assume something to calculate space used)
so: sum(key string sizes) = (2 length_field + 3 string_length)*n

Assume all value string-lists are length 3 and each string is of length 4. So:
sum(list_string_size(string_list) for each hashmap List<String> value)
= n*(8 + 3*(8*2) + 3*(2 length_field + 4 string_length))

Ein einfaches Testprogramm würde eine bessere wirkliche Antwort geben:

import java.util.*;
class TempTest {
    public static void main(String[] args) {
        HashMap<String, List<String>> map = new HashMap<>();
        System.gc();
        printMemory();
        for (int i = 0; i < 2000000; ++i) {
            map.put(String.valueOf(i), Arrays.asList(String.valueOf(i), String.valueOf(i) + "b", String.valueOf(i) + "c"));
        }
        System.gc();
        printMemory();
    }

    private static void printMemory() {
        Runtime runtime = Runtime.getRuntime();
        long totalMemory = runtime.totalMemory();
        long freeMemory = runtime.freeMemory();

        System.out.println("Memory: Used=" + (totalMemory - freeMemory) + " Total=" + totalMemory + " Free=" + freeMemory);
    }
}

Bei mir waren es 640 MB (nach.Gebraucht - vor.Gebraucht).

Answer 4

Kann man nicht im Voraus wissen, ohne zu wissen, was alle Zeichenfolgen sind und wie viele Elemente in jeder Liste sind, oder ohne zu wissen, ob die Zeichenfolgen alle eindeutige Referenzen sind.

Die einzige Möglichkeit, dies herauszufinden, besteht darin, das Ganze in ein Byte-Array (oder eine temporäre Datei) zu serialisieren und genau zu sehen, wie viele Bytes das waren.