wake-up-neo.net

Arbeitsspeicheraufwand von Java HashMap im Vergleich zu ArrayList

Ich frage mich, was ist der Speicheraufwand von Java HashMap im Vergleich zu ArrayList?

Update:

Ich möchte die Geschwindigkeit für die Suche nach bestimmten Werten eines großen Pakets (6 Millionen +) identischer Objekte verbessern.

Daher denke ich über die Verwendung einer oder mehrerer HashMap anstelle von ArrayList nach. Aber ich frage mich, was ist der Overhead von HashMap.

Soweit ich es verstehe, wird der Schlüssel nicht gespeichert, sondern nur der Hash des Schlüssels. Es sollte also etwa Größe des Hash des Objekts + ein Zeiger sein.

Aber welche Hash-Funktion wird verwendet? Ist es das von Object angebotene oder ein anderes?

34
elhoim

Wenn Sie HashMap mit ArrayList vergleichen, nehme ich an, dass Sie eine Art Suchen/Indizieren der ArrayList durchführen, wie z. B. die binäre Suche oder eine benutzerdefinierte Hashtabelle ...? Denn ein .get (key) über 6 Millionen Einträge wäre bei einer linearen Suche nicht durchführbar.

Mit dieser Annahme habe ich einige empirische Tests durchgeführt und kam zu dem Schluss, dass "Sie 2,5-mal so viele kleine Objekte in derselben Menge von RAM speichern können, wenn Sie ArrayList mit binärer Suche oder benutzerdefinierter Hash-Map-Implementierung verwenden versus HashMap ". Mein Test basierte auf kleinen Objekten mit nur 3 Feldern, von denen eines der Schlüssel ist und der Schlüssel eine ganze Zahl ist. Ich habe einen 32bit JDK 1.6 verwendet. Weitere Hinweise zu dieser Zahl von "2.5" finden Sie unten.

Die wichtigsten Dinge zu beachten sind:

(a) Es ist nicht der Platz für Referenzen oder "Lastfaktor", der Sie tötet, sondern der für die Objekterstellung erforderliche Overhead. Wenn es sich bei dem Schlüssel um einen Grundtyp oder um eine Kombination aus zwei oder mehr Grundwerten oder Referenzwerten handelt, erfordert jeder Schlüssel ein eigenes Objekt, das einen Overhead von 8 Byte aufweist.

(b) Nach meiner Erfahrung benötigen Sie den Schlüssel normalerweise als Teil des Werts (z. B. zum Speichern von Kundendatensätzen, die nach Kundennummer indiziert sind, möchten Sie die Kundennummer immer noch als Teil des Kundenobjekts). Dies bedeutet, dass es IMO etwas verschwenderisch ist, dass eine HashMap separat Verweise auf Schlüssel und Werte speichert.

Vorsichtsmaßnahmen:

  1. Der am häufigsten verwendete Typ für HashMap-Schlüssel ist String. Der Overhead für die Objekterstellung gilt hier nicht, daher wäre der Unterschied geringer.

  2. Ich habe eine Zahl von 2,8 erhalten, wobei 8880502 Einträge in die ArrayList eingefügt wurden, im Vergleich zu 3148004 in der HashMap in -Xmx256M JVM, aber mein ArrayList-Ladefaktor war 80% und meine Objekte waren recht klein - 12 Byte plus 8 Byte Objekt-Overhead.

  3. Meine Figur und meine Implementierung erfordern, dass der Schlüssel im Wert enthalten ist. Andernfalls hätte ich das gleiche Problem mit dem Objekterstellungsaufwand und es wäre nur eine weitere Implementierung von HashMap.

Mein Code:

public class Payload {
    int key,b,c;
    Payload(int _key) { key = _key; }
}


import org.junit.Test;

import Java.util.HashMap;
import Java.util.Map;


public class Overhead {
    @Test
    public void useHashMap()
    {
        int i=0;
        try {
            Map<Integer, Payload> map = new HashMap<Integer, Payload>();
            for (i=0; i < 4000000; i++) {
                int key = (int)(Math.random() * Integer.MAX_VALUE);
                map.put(key, new Payload(key));
            }
        }
        catch (OutOfMemoryError e) {
            System.out.println("Got up to: " + i);
        }
    }

    @Test
    public void useArrayList()
    {
        int i=0;
        try {
            ArrayListMap map = new ArrayListMap();
            for (i=0; i < 9000000; i++) {
                int key = (int)(Math.random() * Integer.MAX_VALUE);
                map.put(key, new Payload(key));
            }
        }
        catch (OutOfMemoryError e) {
            System.out.println("Got up to: " + i);
        }
    }
}


import Java.util.ArrayList;


public class ArrayListMap {
    private ArrayList<Payload> map = new ArrayList<Payload>();
    private int[] primes = new int[128];

    static boolean isPrime(int n)
    {
        for (int i=(int)Math.sqrt(n); i >= 2; i--) {
            if (n % i == 0)
                return false;
        }
        return true;
    }

    ArrayListMap()
    {
        for (int i=0; i < 11000000; i++)    // this is clumsy, I admit
            map.add(null);
        int n=31;
        for (int i=0; i < 128; i++) {
            while (! isPrime(n))
                n+=2;
            primes[i] = n;
            n += 2;
        }
        System.out.println("Capacity = " + map.size());
    }

    public void put(int key, Payload value)
    {
        int hash = key % map.size();
        int hash2 = primes[key % primes.length];
        if (hash < 0)
            hash += map.size();
        do {
            if (map.get(hash) == null) {
                map.set(hash, value);
                return;
            }
            hash += hash2;
            if (hash >= map.size())
                hash -= map.size();
        } while (true);
    }

    public Payload get(int key)
    {
        int hash = key % map.size();
        int hash2 = primes[key % primes.length];
        if (hash < 0)
            hash += map.size();
        do {
            Payload payload = map.get(hash);
            if (payload == null)
                return null;
            if (payload.key == key)
                return payload;
            hash += hash2;
            if (hash >= map.size())
                hash -= map.size();
        } while (true);
    }
}
42
Tim Cooper

Am einfachsten wäre es, die Quelle zu betrachten und auf diese Weise herauszufinden. Sie vergleichen jedoch wirklich Äpfel und Orangen - Listen und Karten sind konzeptionell sehr unterschiedlich. Es kommt selten vor, dass Sie aufgrund der Speicherbelegung zwischen ihnen wählen würden.

Was ist der Hintergrund hinter dieser Frage?

15
Jon Skeet

Alles, was in beiden gespeichert wird, sind Zeiger. Je nach Architektur sollte ein Zeiger 32 oder 64 Bit (oder mehr oder weniger) aufweisen.

Eine Array-Liste von 10 tendiert dazu, mindestens 10 "Zeiger" zuzuordnen (und auch einige einmalige Zusatzkosten).

Eine Karte muss das Doppelte (20 Zeiger) zuweisen, da sie zwei Werte gleichzeitig speichert. Darüber hinaus muss es den "Hash" speichern. Das sollte größer als die Karte sein, bei einer Belastung von 75% sollte es bei ungefähr 13 32-Bit-Werten (Hashes) liegen.

wenn Sie also eine spontane Antwort wünschen, sollte das Verhältnis etwa 1: 3,25 betragen, aber Sie sprechen nur über Zeigerspeicher - sehr klein, wenn Sie nicht eine riesige Anzahl von Objekten speichern - und wenn ja, die Möglichkeit, dies zu tun Sofortige Referenzierung (HashMap) vs. Iterate (Array) sollte VIEL wichtiger sein als die Speichergröße.

Oh, auch: Arrays können an die genaue Größe Ihrer Sammlung angepasst werden. HashMaps können ebenfalls verwendet werden, wenn Sie die Größe angeben, aber wenn sie größer als diese Größe wird, wird ein größeres Array neu zugewiesen und nicht von einem Teil verwendet, sodass es auch etwas Verschwendung geben kann.

8
Bill K

Ich habe auch keine Antwort für Sie, aber bei einer schnellen Google-Suche wurde eine Funktion in Java gefunden, die hilfreich sein könnte.

Runtime.getRuntime (). FreeMemory ();

Daher schlage ich vor, dass Sie eine HashMap und eine ArrayList mit den gleichen Daten füllen. Den freien Speicher aufzeichnen, das erste Objekt löschen, den Speicher aufzeichnen, das zweite Objekt löschen, den Speicher aufzeichnen, die Differenzen berechnen, ..., Gewinn !!! 

Sie sollten dies wahrscheinlich mit Datenmengen tun. dh mit 1000 beginnen, dann 10000, 100000, 1000000.

EDIT: Korrigiert, dank amischiefr.

BEARBEITEN: Tut mir leid, dass Sie Ihren Beitrag bearbeitet haben, aber das ist ziemlich wichtig, wenn Sie dies verwenden möchten (und es ist ein bisschen zu viel für einen Kommentar) . FreeMemory funktioniert nicht so, wie Sie denken. Erstens wird der Wert durch die Garbage Collection geändert. Zweitens wird der Wert geändert, wenn Java mehr Speicherplatz zuweist. Wenn Sie nur den freeMemory-Aufruf verwenden, erhalten Sie keine nützlichen Daten.

Versuche dies:

public static void displayMemory() {
    Runtime r=Runtime.getRuntime();
    r.gc();
    r.gc(); // YES, you NEED 2!
    System.out.println("Memory Used="+(r.totalMemory()-r.freeMemory()));
}

Oder Sie können den verwendeten Speicher zurückgeben und speichern und dann mit einem späteren Wert vergleichen. Denken Sie auf jeden Fall an die 2 gcs und subtrahieren Sie von totalMemory ().

Nochmals, es tut mir leid, Ihren Beitrag zu bearbeiten!

7
sanscore

Hashmaps versuchen einen Lastfaktor beizubehalten (normalerweise zu 75% voll). Man kann sich eine Hashmap als eine dünn gefüllte Array-Liste vorstellen. Das Problem bei einem direkten Vergleich der Größe ist, dass dieser Belastungsfaktor der Karte mit der Größe der Daten wächst. ArrayList dagegen wächst durch Verdoppelung der internen Arraygröße. Bei relativ kleinen Größen sind sie vergleichbar. Wenn Sie jedoch immer mehr Daten in die Karte packen, sind viele leere Referenzen erforderlich, um die Hash-Leistung zu erhalten.

In beiden Fällen empfehle ich, die erwartete Größe der Daten zu erstellen, bevor Sie mit dem Hinzufügen beginnen. Dadurch erhalten die Implementierungen eine bessere Anfangseinstellung und werden in beiden Fällen wahrscheinlich weniger verbrauchen.

Update:

basierend auf Ihrem aktualisierten Problem check out Glasierte Listen . Dies ist ein nettes kleines Werkzeug, das von einigen Google-Mitarbeitern geschrieben wurde, um Vorgänge auszuführen, die dem von Ihnen beschriebenen ähnlich sind. Es ist auch sehr schnell. Ermöglicht Clustering, Filterung, Suche usw.

3
reccles

HashMap enthält einen Verweis auf den Wert und einen Verweis auf den Schlüssel.

ArrayList hält einfach einen Verweis auf den Wert.

Angenommen, der Schlüssel verwendet den gleichen Speicher des Werts, verwendet HashMap 50% mehr Speicher (obwohl dies streng genommen nicht die HashMap ist, die diesen Speicher verwendet, weil sie lediglich einen Verweis darauf enthält). 

Andererseits bietet HashMap konstante Zeitleistung für die grundlegenden Operationen (get und put) Obwohl es zwar mehr Speicherplatz benötigt, ist das Abrufen eines Elements unter Verwendung einer HashMap jedoch viel schneller als mit einer ArrayList.

Das nächste, was Sie tun sollten, ist sich nicht darum zu kümmern, wer mehr Speicher benötigt, aber wozu sind sie gut für

Durch die Verwendung der richtigen Datenstruktur für Ihr Programm wird mehr CPU/Speicher eingespart als bei der Implementierung der Bibliothek darunter.

EDIT 

Nach der Antwort von Grant Welch entschied ich mich für 2.000.000 ganze Zahlen zu messen.

Hier ist der Quellcode

Dies ist die Ausgabe 

$
$javac MemoryUsage.Java  
Note: MemoryUsage.Java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
$Java -Xms128m -Xmx128m MemoryUsage 
Using [email protected] size: 0
Total memory: 133.234.688
Initial free: 132.718.608
  Final free: 77.965.488

Used: 54.753.120
Memory Used 41.364.824
[email protected] size: 2000000
$
$Java -Xms128m -Xmx128m MemoryUsage H
Using [email protected] size: 0
Total memory: 133.234.688
Initial free: 124.329.984
  Final free: 4.109.600

Used: 120.220.384
Memory Used 129.108.608
[email protected] size: 2000000
3
OscarRyz

Grundsätzlich sollten Sie das "richtige Werkzeug für den Job" verwenden. Da es verschiedene Fälle gibt, in denen Sie ein Schlüssel/Wert-Paar benötigen (wo Sie eine HashMap verwenden können) und verschiedene Fälle, in denen Sie nur eine Liste von Werten benötigen (wo Sie eine ArrayList verwenden können), dann die Frage "welche man braucht mehr Speicher ", ist meiner Meinung nach irrelevant, da es nicht darauf ankommt, eines über das andere zu wählen.

Um die Frage zu beantworten, da HashMap Schlüssel/Wert-Paare speichert, während ArrayList nur Werte speichert, würde ich davon ausgehen, dass das Hinzufügen von Schlüsseln allein zur HashMap bedeuten würde, dass sie mehr Speicherplatz beansprucht derselbe Wert Typ (zB wenn die Werte in beiden Strings sind).

2
Avrom

Ich denke, hier wird die falsche Frage gestellt.

Wenn Sie die Geschwindigkeit verbessern möchten, mit der Sie in einem List mit sechs Millionen Einträgen nach einem Objekt suchen können, sollten Sie prüfen, ob wie schnell die Abrufvorgänge dieses Datentyps ausgeführt werden.

Wie üblich geben die Javadocs für diese Klassen ziemlich deutlich an, welche Art von Leistung sie bieten:

HashMap :

Diese Implementierung bietet eine zeitlich konstante Leistung für die Grundoperationen (get und put), vorausgesetzt, die Hash-Funktion verteilt die Elemente ordnungsgemäß auf die Buckets.

Dies bedeutet, dass HashMap.get (Schlüssel) O(1) ist.

ArrayList :

Die Operationen size, isEmpty, get, set, iterator und listIterator werden in konstanter Zeit ausgeführt. Die Additionsoperation wird in einer amortisierten konstanten Zeit ausgeführt, dh das Hinzufügen von n Elementen erfordert O(n) Zeit. Alle anderen Operationen verlaufen in linearer Zeit (grob gesagt).

Dies bedeutet, dass die meisten Operationen von ArrayList nur O(1) sind, aber wahrscheinlich nicht die, die Sie verwenden würden, um Objekte zu finden, die einem bestimmten Wert entsprechen.

Wenn Sie jedes Element in ArrayList durchlaufen und auf Gleichheit prüfen oder contains() verwenden, bedeutet dies, dass Ihre Operation zur O(n)-Zeit (oder schlechter) ausgeführt wird.

Wenn Sie mit O(1) oder O(n) nicht vertraut sind, bezieht sich dies auf die Dauer einer Operation. Wenn Sie in diesem Fall eine Leistung mit konstanter Zeit erzielen können, möchten Sie diese nutzen. Wenn HashMap.get()O(1) ist, bedeutet dies, dass Abrufvorgänge ungefähr die gleiche Zeit in Anspruch nehmen, unabhängig davon, wie viele Einträge sich in der Map befinden .

Die Tatsache, dass so etwas wie ArrayList.contains()O(n) ist, bedeutet, dass die benötigte Zeit mit der Größe der Liste zunimmt. Eine Iteration durch ein ArrayList mit sechs Millionen Einträgen wird also überhaupt nicht sehr effektiv sein.

2
matt b

Ich kenne die genaue Zahl nicht, aber HashMaps sind viel schwerer. Beim Vergleich der beiden Werte ist die interne Darstellung von ArrayList selbstverständlich, aber HashMaps behalten Entry-Objekte (Entry) bei, die Ihren Speicherverbrauch erhöhen können.

Es ist nicht viel größer, aber größer. Eine gute Möglichkeit, dies zu visualisieren, wäre ein dynamischer Profiler wie YourKit , mit dem Sie alle Heap-Zuordnungen sehen können. Es ist ziemlich nett.

1
Malaxeur

Dieser Beitrag gibt viele Informationen zu Objektgrößen in Java.

1
elhoim

Diese site listet den Speicherverbrauch für mehrere häufig verwendete (und nicht so häufig verwendete) Datenstrukturen auf. Von dort aus kann man sehen, dass die HashMap ungefähr den fünffachen Platz einer ArrayList beansprucht. Die Karte weist außerdem pro Eintrag ein zusätzliches Objekt zu.

Wenn Sie eine vorhersagbare Iterationsreihenfolge benötigen und LinkedHashMap verwenden, ist der Speicherbedarf noch höher.

Sie können Ihre eigenen Speichermessungen mit Memory Measurer durchführen.

Es sind jedoch zwei wichtige Fakten zu beachten:

  1. Viele Datenstrukturen (einschließlich ArrayList und HashMap) weisen Speicherplatz zu, den sie derzeit nicht benötigen, da sie sonst häufig eine kostspielige Größenänderungsoperation ausführen müssen. Daher hängt der Speicherverbrauch pro Element davon ab, wie viele Elemente sich in der Sammlung befinden. Ein ArrayList mit den Standardeinstellungen verwendet beispielsweise den gleichen Speicher für 0 bis 10 Elemente.
  2. Wie andere bereits gesagt haben, werden auch die Schlüssel der Karte gespeichert. Wenn sie sich ohnehin nicht im Speicher befinden, müssen Sie diese Speicherkosten ebenfalls hinzufügen. Ein zusätzliches Objekt benötigt normalerweise nur 8 Bytes Overhead, zuzüglich des Speichers für seine Felder und möglicherweise etwas Auffüllen. Das wird also auch viel Speicher sein.
0
Philipp Wendler

Wie Jon Skeet feststellte, sind dies völlig unterschiedliche Strukturen. Eine Map (z. B. HashMap) ist eine Zuordnung von einem Wert zu einem anderen. Das heißt, Sie haben einen Schlüssel, der einem Wert in einer Art Key-> Value-Beziehung zugeordnet wird. Der Schlüssel ist gehasht und wird zur schnellen Suche in einem Array platziert.

Eine Liste ist dagegen eine Sammlung von Elementen mit der Reihenfolge - ArrayList verwendet ein Array als Back-End-Speichermechanismus, was aber irrelevant ist. Jedes indizierte Element ist ein einzelnes Element in der Liste.

bearbeiten: Basierend auf Ihrem Kommentar habe ich folgende Informationen hinzugefügt:

Der Schlüssel wird in einer Hashmap gespeichert. Dies liegt daran, dass ein Hash für zwei verschiedene Elemente nicht eindeutig ist. Daher muss der Schlüssel im Fall von Hash-Kollisionen gespeichert werden. Wenn Sie lediglich sehen möchten, ob ein Element in einer Gruppe von Elementen vorhanden ist, verwenden Sie ein Set (die Standardimplementierung davon ist HashSet). Wenn die Reihenfolge von Bedeutung ist, Sie jedoch eine schnelle Suche benötigen, verwenden Sie ein LinkedHashSet, da die Reihenfolge beibehalten wird, in der die Elemente eingefügt wurden. Die Nachschlagzeit beträgt O(1) für beide, aber die Einfügungszeit ist bei LinkedHashSet etwas länger. Verwenden Sie eine Map nur, wenn Sie tatsächlich von einem Wert zu einem anderen Mapping sind. Wenn Sie nur eine Reihe eindeutiger Objekte haben, verwenden Sie ein Set. Wenn Sie Objekte bestellt haben, verwenden Sie eine Liste.

0
aperkins

Wenn Sie zwei ArrayLists und eine Hashmap in Betracht ziehen, ist dies unbestimmt. beide sind teilweise vollständige Datenstrukturen. Wenn Sie Vector mit Hashtable verglichen haben, ist Vector wahrscheinlich speichereffizienter, da nur der von ihm belegte Speicherplatz zugewiesen wird, während Hashtables mehr Speicherplatz zuweisen.

Wenn Sie ein Schlüssel-Wert-Paar benötigen und keine unglaublich speicherintensiven Arbeiten ausführen, verwenden Sie einfach die Hashmap.

0
Dean J