SparseArray vs. HashMap

Lesezeit: 9 Minuten

Benutzer-Avatar
Paul Boddington

Ich kann mir mehrere Gründe dafür vorstellen HashMaps mit Integer-Schlüsseln sind viel besser als SparseArrays:

  1. Die Android-Dokumentation für a SparseArray sagt: “Es ist im Allgemeinen langsamer als ein herkömmliches HashMap“.
  2. Wenn Sie Code mit schreiben HashMaps eher als SparseArrays Ihr Code funktioniert mit anderen Map-Implementierungen und Sie können alle Java-APIs verwenden, die für Maps entwickelt wurden.
  3. Wenn Sie Code mit schreiben HashMaps eher als SparseArrays Ihr Code funktioniert in Nicht-Android-Projekten.
  4. Kartenüberschreibungen equals() und hashCode() wohingegen SparseArray nicht.

Doch wann immer ich versuche, a zu verwenden HashMap mit ganzzahligen Schlüsseln in einem Android-Projekt sagt mir IntelliJ, dass ich a verwenden soll SparseArray stattdessen. Ich finde das wirklich schwer zu verstehen. Kennt jemand zwingende Gründe für die Verwendung SparseArrays?

Benutzer-Avatar
Sarpe

SparseArray kann als Ersatz verwendet werden HashMap wenn der Schlüssel ein primitiver Typ ist. Es gibt einige Varianten für verschiedene Schlüssel/Wert-Typen, auch wenn nicht alle öffentlich verfügbar sind.

Vorteile sind:

  • Zuteilungsfrei
  • Kein Boxen

Nachteile:

  • Im Allgemeinen langsamer, nicht geeignet für große Sammlungen
  • Sie funktionieren nicht in einem Nicht-Android-Projekt

HashMap kann durch Folgendes ersetzt werden:

SparseArray          <Integer, Object>
SparseBooleanArray   <Integer, Boolean>
SparseIntArray       <Integer, Integer>
SparseLongArray      <Integer, Long>
LongSparseArray      <Long, Object>
LongSparseLongArray  <Long, Long>   //this is not a public class                                 
                                    //but can be copied from  Android source code 

In Bezug auf den Speicher ist hier ein Beispiel für SparseIntArray vs HashMap<Integer, Integer> für 1000 Elemente:

SparseIntArray:

class SparseIntArray {
    int[] keys;
    int[] values;
    int size;
}

Klasse = 12 + 3 * 4 = 24 Bytes
Array = 20 + 1000 * 4 = 4024 Bytes
Insgesamt = 8.072 Byte

HashMap:

class HashMap<K, V> {
    Entry<K, V>[] table;
    Entry<K, V> forNull;
    int size;
    int modCount;
    int threshold;
    Set<K> keys
    Set<Entry<K, V>> entries;
    Collection<V> values;
}

Klasse = 12 + 8 * 4 = 48 Bytes
Eintrag = 32 + 16 + 16 = 64 Byte
Array = 20 + 1000 * 64 = 64024 Bytes
Insgesamt = 64.136 Byte

Quelle: Android-Erinnerungen von Romain Guy ab Folie 90.

Die obigen Zahlen sind die Speichermenge (in Byte), die von JVM auf dem Heap zugewiesen wird. Sie können je nach verwendeter JVM variieren.

Das java.lang.instrument -Paket enthält einige hilfreiche Methoden für fortgeschrittene Operationen wie das Überprüfen der Größe eines Objekts mit getObjectSize(Object objectToSize).

Zusätzliche Informationen sind beim Beamten erhältlich Oracle-Dokumentation.

Klasse = 12 Bytes + (n Instanzvariablen) * 4 Bytes
Array = 20 Bytes + (n Elemente) * (Elementgröße)
Eintrag = 32 Bytes + (1. Elementgröße) + (2. Elementgröße)

  • Kann mir jemand sagen, woher diese “12 + 3 * 4” und “20 + 1000 * 4” kommen?

    – Marian Paździoch

    26. August 2015 um 12:48 Uhr

  • @MarianPaździoch, er zeigte eine Präsentation (speakerdeck.com/romainguy/android-memories), wo eine Klasse 12 Bytes + 3 Variablen von 4 Bytes belegt, ein Array (Referenz) 20 Bytes belegt (dlmalloc – 4, Objekt-Overhead – 8, width&padding – 8).

    – CoolMind

    24. November 2016 um 18:26 Uhr


  • Fürs Protokoll: Ein weiterer entscheidender Nachteil von SparseArray ist, dass es als Android-Objekt für Unit-Tests verspottet werden muss. Wo es möglich ist, verwende ich jetzt Java-eigene Objekte, um das Testen zu vereinfachen.

    – David G

    20. März 2017 um 16:29 Uhr

  • @ DavidG Sie können einfach verwenden Unmock-Plugin um Android-Abhängigkeiten zu verspotten.

    – Schneesturm

    1. April 2017 um 20:50 Uhr

  • Auch wenn Sie kein Android verwenden, ist das Kopieren der Klasse in Ihr Projekt nicht schwierig, es hängt nur von 3 anderen Klassen ab. APL-Lizenz bedeutet, dass dies in Ordnung ist, unabhängig davon, mit welcher Lizenz Sie arbeiten.

    – Yann TM

    15. März 2018 um 16:17 Uhr

Benutzer-Avatar
Suragch

Ich kam hierher, weil ich nur ein Beispiel für die Verwendung wollte SparseArray. Dies ist eine ergänzende Antwort darauf.

Erstellen Sie ein SparseArray

SparseArray<String> sparseArray = new SparseArray<>();

EIN SparseArray ordnet Ganzzahlen einigen zu Objectdamit Sie ersetzen könnten String im obigen Beispiel mit jedem anderen Object. Wenn Sie ganze Zahlen auf ganze Zahlen abbilden, dann verwenden Sie SparseIntArray.

Elemente hinzufügen oder aktualisieren

Verwenden put (oder append), um dem Array Elemente hinzuzufügen.

sparseArray.put(10, "horse");
sparseArray.put(3, "cow");
sparseArray.put(1, "camel");
sparseArray.put(99, "sheep");
sparseArray.put(30, "goat");
sparseArray.put(17, "pig");

Notiere dass der int Schlüssel müssen nicht in Ordnung sein. Dies kann auch verwendet werden, um den Wert an einem bestimmten Punkt zu ändern int Schlüssel.

Teile entfernen

Verwenden remove (oder delete), um Elemente aus dem Array zu entfernen.

sparseArray.remove(17); // "pig" removed

Das int Parameter ist der ganzzahlige Schlüssel.

Nachschlagewerte für einen int-Schlüssel

Verwenden get um den Wert für einen ganzzahligen Schlüssel zu erhalten.

String someAnimal = sparseArray.get(99);  // "sheep"
String anotherAnimal = sparseArray.get(200); // null

Sie können verwenden get(int key, E valueIfKeyNotFound) wenn du es vermeiden willst null für fehlende Schlüssel.

Iterieren Sie über die Elemente

Sie können verwenden keyAt und valueAt ein Index, um die Sammlung zu durchlaufen, weil die SparseArray unterhält einen separaten Index, der sich von der unterscheidet int Schlüssel.

int size = sparseArray.size();
for (int i = 0; i < size; i++) {

    int key = sparseArray.keyAt(i);
    String value = sparseArray.valueAt(i);

    Log.i("TAG", "key: " + key + " value: " + value);
}

// key: 1 value: camel
// key: 3 value: cow
// key: 10 value: horse
// key: 30 value: goat
// key: 99 value: sheep

Beachten Sie, dass die Schlüssel nach aufsteigendem Wert sortiert sind, nicht in der Reihenfolge, in der sie hinzugefügt wurden.

Benutzer-Avatar
Rod_Algonquin

Doch immer wenn ich versuche, eine HashMap mit Integer-Schlüsseln in einem Android-Projekt zu verwenden, sagt mir intelliJ, dass ich stattdessen ein SparseArray verwenden sollte.

Es ist nur eine Warnung davor Dokumentation davon spärliches Array:

Es soll speichereffizienter sein als die Verwendung einer HashMap zum Zuordnen von Ganzzahlen zu Objekten

Das SparseArray wird gemacht Speicher effizient als die Verwendung der regulären HashMap, das heißt, es sind nicht mehrere Lücken innerhalb des Arrays zulässig, anders als bei HashMap. Sie müssen sich keine Sorgen machen, Sie können die traditionelle HashMap verwenden, wenn Sie sich keine Gedanken über die Speicherzuweisung für das Gerät machen möchten.

  • Die Punkte zum Speichern von Speicher sind offensichtlich gültig, aber ich habe nie verstanden, warum Android SparseArray nicht dazu bringen konnte, Map zu implementieren, damit Sie eine speichereffiziente Map-Implementierung erhalten – das Beste aus beiden Welten.

    – Paul Boddington

    29. August 2014 um 2:34 Uhr

  • @PaulBoddington erinnere dich auch SparseArray verhindert, dass die Schlüssel-Ganzzahl Auto-Box ist, was eine weitere Operation und Kostenleistung ist. Anstelle von Map wird die primitive Ganzzahl automatisch in eine Box umgewandelt Integer

    – Rod_Algonquin

    29. August 2014 um 2:36 Uhr

  • Auch wahr, aber wenn sie die put-Methode überladen hätten, indem sie eine mit der Signatur put(int a, T t) eingefügt hätten, könnten Sie immer noch Schlüssel-Wert-Paare in die Map einfügen, ohne dass Schlüssel automatisch verpackt werden. Ich denke nur, dass das Collections Framework so mächtig ist (einer der besten Gründe für die Verwendung von Java), dass es Wahnsinn ist, es nicht zu nutzen.

    – Paul Boddington

    29. August 2014 um 2:46 Uhr

  • @PaulBoddington-Sammlungen basieren auf Objekten, die nicht auf primitiven Objekten basieren, sodass sie nicht innerhalb der Sammlungs-API funktionieren

    – Rod_Algonquin

    29. August 2014 um 3:00 Uhr

Nach einigem Googeln versuche ich, einige Informationen zu den bereits geposteten Antworten hinzuzufügen:

Isaak Taylor machte einen Leistungsvergleich für SparseArrays und Hashmaps. Er behauptet, dass

Hashmap und SparseArray sind für Datenstrukturgrößen unter 1.000 sehr ähnlich

und

wenn die Größe auf die 10.000er-Marke erhöht wurde […] Die Hashmap hat eine höhere Leistung beim Hinzufügen von Objekten, während das SparseArray eine höhere Leistung beim Abrufen von Objekten hat. […] Bei einer Größe von 100.000 […] Die Hashmap verliert sehr schnell an Leistung

Ein Vergleich bzgl Edgblog zeigt, dass ein SparseArray aufgrund des kleineren Schlüssels (int vs. Integer) und der Tatsache, dass

Eine HashMap.Entry-Instanz muss die Referenzen für den Schlüssel, den Wert und den nächsten Eintrag verfolgen. Außerdem muss es auch den Hash des Eintrags als int speichern.

Abschließend würde ich sagen, dass der Unterschied eine Rolle spielen könnte, wenn Sie viele Daten in Ihrer Karte speichern. Andernfalls ignorieren Sie die Warnung einfach.

Ein Sparse-Array in Java ist eine Datenstruktur, die Schlüssel auf Werte abbildet. Gleiche Idee wie eine Karte, aber andere Implementierung:

  1. Eine Map wird intern als ein Array von Listen dargestellt, wobei jedes Element in diesen Listen ein Schlüssel-Wert-Paar ist. Sowohl der Schlüssel als auch der Wert sind Objektinstanzen.

  2. Ein Array mit geringer Dichte besteht einfach aus zwei Arrays: einem Array von (Primitiven) Schlüsseln und einem Array von (Objekten) Werten. Diese Array-Indizes können Lücken aufweisen, daher der Begriff „sparse“-Array.

Das Hauptinteresse des SparseArray besteht darin, dass es Speicher spart, indem es Primitive anstelle von Objekten als Schlüssel verwendet.

Benutzer-Avatar
suitianshi

Die Android-Dokumentation für ein SparseArray sagt: “Es ist im Allgemeinen langsamer als eine herkömmliche HashMap”.

Ja, das ist richtig. Aber wenn Sie nur 10 oder 20 Artikel haben, sollte der Leistungsunterschied unbedeutend sein.

Wenn Sie Code schreiben, der HashMaps anstelle von SparseArrays verwendet, funktioniert Ihr Code mit anderen Implementierungen von Map und Sie können alle Java-APIs verwenden, die für Maps entwickelt wurden

Ich denke, meistens verwenden wir nur HashMap um einen Wert zu suchen, der mit einem Schlüssel verknüpft ist, während SparseArray ist wirklich gut darin.

Wenn Sie Code schreiben, der HashMaps anstelle von SparseArrays verwendet, funktioniert Ihr Code in Nicht-Android-Projekten.

Der Quellcode von SparseArray ist ziemlich einfach und leicht verständlich, sodass Sie ihn nur wenig auf andere Plattformen verschieben müssen (durch einfaches COPY&Paste).

Map überschreibt equals() und hashCode(), SparseArray dagegen nicht

Alles, was ich sagen kann, ist (zu den meisten Entwicklern), wen interessiert das?

Ein weiterer wichtiger Aspekt bzgl SparseArray ist, dass es nur ein Array verwendet, um alle Elemente während zu speichern HashMap Verwendet EntryAlso SparseArray kostet deutlich weniger Speicher als a HashMapsehen Dies

Benutzer-Avatar
Bruce

Schade, dass der Compiler eine Warnung ausgibt. Ich denke, HashMap wurde zum Speichern von Gegenständen viel zu oft verwendet.

SparseArrays haben ihren Platz. Da sie einen binären Suchalgorithmus verwenden, um einen Wert in einem Array zu finden, müssen Sie überlegen, was Sie tun. Die binäre Suche ist O (log n), während die Hash-Suche O (1) ist. Dies bedeutet nicht unbedingt, dass die binäre Suche für einen bestimmten Datensatz langsamer ist. Wenn jedoch die Anzahl der Einträge wächst, übernimmt die Hash-Tabelle die Macht. Daher die Kommentare, bei denen eine geringe Anzahl von Einträgen gleich und möglicherweise besser sein kann als die Verwendung einer HashMap.

Eine HashMap ist nur so gut wie der Hash und kann auch vom Lastfaktor beeinflusst werden (ich denke, in späteren Versionen ignorieren sie den Lastfaktor, damit er besser optimiert werden kann). Sie haben auch einen sekundären Hash hinzugefügt, um sicherzustellen, dass der Hash gut ist. Auch der Grund, warum SparseArray für relativ wenige Einträge (<100) wirklich gut funktioniert.

Ich würde vorschlagen, dass Sie Trove ausprobieren, wenn Sie eine Hash-Tabelle benötigen und eine bessere Speichernutzung für primitive Integer (kein Auto-Boxing) usw. wünschen. (http://trove.starlight-systems.com – LGPL-Lizenz). (Keine Zugehörigkeit zu Trove, genau wie ihre Bibliothek)

Mit dem vereinfachten Multidex-Gebäude, das wir haben, müssen Sie Trove nicht einmal für das neu verpacken, was Sie brauchen. (Trove hat viele Klassen)

1346980cookie-checkSparseArray vs. HashMap

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy