SparseArray vs HashMap

176

Ich kann mir mehrere Gründe vorstellen, warum HashMaps mit ganzzahligen Schlüsseln viel besser sind als SparseArrays:

  1. In der Android-Dokumentation für a SparseArrayheißt es: "Es ist im Allgemeinen langsamer als ein traditionelles HashMap".
  2. Wenn Sie Code mit HashMaps anstatt mit s schreiben, SparseArrayfunktioniert Ihr Code mit anderen Implementierungen von Map und Sie können alle für Maps entwickelten Java-APIs verwenden.
  3. Wenn Sie Code mit HashMaps anstatt mit s schreiben, SparseArrayfunktioniert Ihr Code in Nicht-Android-Projekten.
  4. Map überschreibt equals()und hashCode()während SparseArraynicht.

Wenn ich jedoch versuche, a HashMapmit Ganzzahlschlüsseln in einem Android-Projekt zu verwenden, sagt mir IntelliJ, ich sollte a verwendenSparseArray stattdessen verwenden soll. Ich finde das wirklich schwer zu verstehen. Kennt jemand zwingende Gründe für die Verwendung von SparseArrays?

Paul Boddington
quelle

Antworten:

234

SparseArray kann verwendet werden, um zu ersetzen HashMap wenn der Schlüssel ein primitiver Typ ist. Es gibt einige Varianten für verschiedene Schlüssel- / Werttypen, obwohl nicht alle öffentlich verfügbar sind.

Vorteile sind:

  • Zuteilungsfrei
  • Kein Boxen

Nachteile:

  • Im Allgemeinen langsamer, für große Sammlungen nicht angegeben
  • 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 SparseIntArrayvs 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
Gesamt = 8.072 Bytes

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 Bytes
Array = 20 + 1000 * 64 = 64024 Bytes
Gesamt = 64.136 Bytes

Quelle: Android Memories von Romain Guy aus Folie 90.

Die obigen Zahlen geben die von JVM auf dem Heap zugewiesene Speichermenge (in Byte) an. Sie können je nach verwendeter JVM variieren.

Das java.lang.instrumentPaket enthält einige hilfreiche Methoden für erweiterte Vorgänge wie das Überprüfen der Größe eines Objekts mit getObjectSize(Object objectToSize).

Zusätzliche Informationen finden Sie in der offiziellen 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)

Sarpe
quelle
15
Kann mich jemand führen, woher diese "12 + 3 * 4" und "20 + 1000 * 4" kommen?
Marian Paździoch
5
@ MarianPaździoch zeigte er eine Präsentation ( Speakerdeck.com/romainguy/android-memories ), in der eine Klasse 12 Bytes + 3 Variablen mit 4 Bytes belegt, ein Array (Referenz) 20 Bytes (dlmalloc - 4, Objekt-Overhead - 8, Breite und Abstand) - 8).
CoolMind
1
Ein weiterer wesentlicher Nachteil von SparseArray ist, dass es als Android-Objekt für Unit-Tests verspottet werden muss. Wo möglich verwende ich jetzt Javas eigene Objekte, um das Testen zu vereinfachen.
David G
@DavidG Sie können einfach das Unlock-Plugin verwenden , um Android-Abhängigkeiten zu verspotten.
Schneesturm
1
Selbst wenn Sie kein Android-Gerät verwenden, ist das Kopieren der Klasse in Ihr Projekt nicht schwierig, sondern hängt nur von drei anderen Klassen ab. APL-Lizenz bedeutet, dass dies in Ordnung ist, unabhängig davon, mit welcher Lizenz Sie arbeiten.
Yann TM
35

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

Erstellen Sie ein SparseArray

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

A SparseArrayordnet einige Ganzzahlen zu Object, sodass Sie sie Stringim obigen Beispiel durch andere ersetzen können Object. Wenn Sie Ganzzahlen Ganzzahlen zuordnen, verwenden SieSparseIntArray .

Elemente hinzufügen oder aktualisieren

Verwenden Sie 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");

Beachten Sie, dass die intSchlüssel nicht in Ordnung sein müssen. Dies kann auch verwendet werden, um den Wert an einem bestimmten intSchlüssel zu ändern .

Teile entfernen

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

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

Der intParameter ist der Ganzzahlschlüssel.

Suchwerte für einen int-Schlüssel

Verwenden Sie getdiese Option , um den Wert für einen Ganzzahlschlüssel abzurufen.

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

Sie können verwenden, get(int key, E valueIfKeyNotFound)wenn Sie vermeiden möchten, nullnach fehlenden Schlüsseln zu suchen.

Iterieren Sie über die Elemente

Sie können keyAtund valueAteinige Indizes verwenden, um die Sammlung zu durchlaufen, da die SparseArrayeinen separaten Index verwaltet, der sich von den intSchlüsseln unterscheidet.

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 in aufsteigender Reihenfolge sortiert sind und nicht in der Reihenfolge, in der sie hinzugefügt wurden.

Suragch
quelle
17

Wenn ich jedoch versuche, eine HashMap mit Ganzzahlschlüsseln in einem Android-Projekt zu verwenden, sagt mir IntelliJ, dass ich stattdessen ein SparseArray verwenden soll.

Es ist nur eine Warnung aus dieser Dokumentation des spärlichen Arrays:

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

Das SparseArrayist speichereffizient als die Verwendung der regulären HashMap, dh es werden nicht mehrere Lücken innerhalb des Arrays zugelassen, die HashMap nicht ähneln. Sie müssen sich keine Sorgen machen. Sie können die herkömmliche HashMap verwenden, wenn Sie sich keine Gedanken über die Speicherzuordnung zum Gerät machen möchten.

Rod_Algonquin
quelle
5
Die Punkte zum Speichern von Speicher sind offensichtlich gültig, aber ich habe nie verstanden, warum Android SparseArray <T> nicht dazu gebracht haben könnte, Map <Integer, T> zu implementieren, damit Sie eine speichereffiziente Map-Implementierung erhalten - das Beste aus beiden Welten.
Paul Boddington
3
@PaulBoddington Denken Sie auch daran, SparseArraydass verhindert wird , dass die Schlüssel-Ganzzahl Auto-Box ist, was eine weitere Operation und Kostenleistung darstellt . anstatt Karte wird es die primitiven integer AutoBoxInteger
Rod_Algonquin
Auch wahr, aber wenn sie die Put-Methode durch Einfügen einer mit Signatur-Put (int a, T t) überladen hätten, könnten Sie immer noch Schlüssel-Wert-Paare in die Karte einfügen, ohne dass die Schlüssel automatisch verpackt werden. Ich denke nur, dass das Collections Framework so leistungsfähig ist (einer der besten Gründe für die Verwendung von Java), dass es Wahnsinn ist, es nicht auszunutzen.
Paul Boddington
6
@PaulBoddington Sammlungen basieren auf Objekten, die nicht primitiv sind, so dass sie nicht in der Sammlungs-API
funktionieren
10

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

  1. Eine Karte wird intern als 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 spärliches Array besteht einfach aus zwei Arrays: einem Array aus (primitiven) Schlüsseln und einem Array aus (Objekten) Werten. Es kann Lücken in diesen Array-Indizes geben, daher der Begriff "spärliches" Array.

Das Hauptinteresse des SparseArray besteht darin, dass Speicherplatz gespart wird, indem Primitive anstelle von Objekten als Schlüssel verwendet werden.

Ganesh Katikar
quelle
10

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

Isaac Taylor führte einen Leistungsvergleich für SparseArrays und Hashmaps durch. Er behauptet, dass

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

und

Wenn die Größe auf [...] 10.000 erhöht wurde, bietet die Hashmap beim Hinzufügen von Objekten eine höhere Leistung, während das SparseArray beim Abrufen von Objekten eine höhere Leistung aufweist. [...] Bei einer Größe von 100.000 [...] verliert die Hashmap sehr schnell an Leistung

Ein Vergleich in Edgblog zeigt, dass ein SparseArray aufgrund des kleineren Schlüssels (int vs Integer) und der Tatsache, dass ein SparseArray viel weniger Speicher benötigt als eine HashMap

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

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

Sebastian
quelle
4

In der Android-Dokumentation für ein SparseArray heißt es: "Es ist im Allgemeinen langsamer als eine herkömmliche HashMap."

Ja, das ist richtig. Wenn Sie jedoch nur 10 oder 20 Elemente haben, sollte der Leistungsunterschied unbedeutend sein.

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

Ich denke, meistens verwenden wir nur HashMap, um einen Wert zu suchen, der einem Schlüssel zugeordnet ist, während dies SparseArraywirklich gut ist.

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

Der Quellcode von SparseArray ist ziemlich einfach und leicht zu verstehen, so dass Sie nur wenig Aufwand betreiben, um ihn auf andere Plattformen zu verschieben (durch einfaches Kopieren und Einfügen).

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

Alles was ich sagen kann ist (für die meisten Entwickler), wen interessiert das?

Ein weiterer wichtiger Aspekt SparseArrayist , dass es nur ein Array verwendet , um alle Elemente zu speichern , während HashMapAnwendungen Entry, so SparseArraysignifikant weniger Speicher als eine kosten HashMap, sehen diese

Suitianshi
quelle
1

Es ist bedauerlich, dass der Compiler eine Warnung ausgibt. Ich denke, HashMap wurde viel zu oft zum Speichern von Gegenständen 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. Mit zunehmender Anzahl von Einträgen übernimmt jedoch die Leistung der Hash-Tabelle. 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 durch den Auslastungsfaktor beeinflusst werden (ich denke, in späteren Versionen wird der Auslastungsfaktor ignoriert, 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) sehr gut funktioniert.

Ich würde vorschlagen, wenn Sie eine Hash-Tabelle benötigen und eine bessere Speichernutzung für primitive Ganzzahlen (kein automatisches Boxen) usw. wünschen, probieren Sie trove aus. ( http://trove.starlight-systems.com - LGPL-Lizenz). (Keine Zugehörigkeit zur Fundgrube, genau wie ihre Bibliothek)

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

Bruce
quelle