SparseArray vs HashMap

177

Je peux penser à plusieurs raisons pour lesquelles HashMaps avec des clés entières sont bien meilleures que SparseArrays:

  1. La documentation Android pour un SparseArraydit "Il est généralement plus lent qu'un traditionnel HashMap".
  2. Si vous écrivez du code en utilisant HashMaps plutôt que SparseArrays, votre code fonctionnera avec d'autres implémentations de Map et vous pourrez utiliser toutes les API Java conçues pour Maps.
  3. Si vous écrivez du code en utilisant HashMaps plutôt que SparseArrays, votre code fonctionnera dans des projets non Android.
  4. Carte overrides equals()et hashCode()alors SparseArrayne fonctionne pas.

Pourtant, chaque fois que j'essaie d'utiliser un HashMapavec des clés entières dans un projet Android, IntelliJ me dit que je devrais utiliser un à la SparseArrayplace. Je trouve cela vraiment difficile à comprendre. Quelqu'un connaît-il des raisons impérieuses d'utiliser SparseArrays?

Paul Boddington
la source

Réponses:

235

SparseArraypeut être utilisé pour remplacer HashMaplorsque la clé est de type primitif. Il existe quelques variantes pour différents types de clé / valeur, même si elles ne sont pas toutes disponibles publiquement.

Les avantages sont:

  • Sans allocation
  • Pas de boxe

Désavantages:

  • Généralement plus lent, non indiqué pour les grandes collections
  • Ils ne fonctionneront pas dans un projet non Android

HashMap peut être remplacé par le texte suivant:

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 

En termes de mémoire, voici un exemple de SparseIntArrayvs HashMap<Integer, Integer>pour 1000 éléments:

SparseIntArray:

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

Classe = 12 + 3 * 4 = 24 octets
Tableau = 20 + 1000 * 4 = 4024 octets
Total = 8072 octets

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;
}

Classe = 12 + 8 * 4 = 48 octets
Entrée = 32 + 16 + 16 = 64 octets
Tableau = 20 + 1000 * 64 = 64024 octets
Total = 64136 octets

Source: Android Memories par Romain Guy à partir de la diapositive 90.

Les nombres ci-dessus correspondent à la quantité de mémoire (en octets) allouée sur le tas par JVM. Ils peuvent varier en fonction de la JVM spécifique utilisée.

Le java.lang.instrumentpackage contient des méthodes utiles pour les opérations avancées telles que la vérification de la taille d'un objet avec getObjectSize(Object objectToSize).

Des informations supplémentaires sont disponibles dans la documentation officielle d' Oracle .

Classe = 12 octets + (n variables d'instance) * 4 octets
Tableau = 20 octets + (n éléments) * (taille de l'élément)
Entrée = 32 octets + (taille du 1er élément) + (taille du 2ème élément)

Sarpe
la source
15
Quelqu'un peut-il me guider d'où viennent ces "12 + 3 * 4" et "20 + 1000 * 4"?
Marian Paździoch
5
@ MarianPaździoch, il a montré une présentation ( speakerdeck.com/romainguy/android-memories ) où une classe occupe 12 octets + 3 variables de 4 octets, un tableau (référence) occupe 20 octets (dlmalloc - 4, surcharge de l'objet - 8, largeur et remplissage - 8).
CoolMind
1
Pour mémoire, un autre inconvénient clé de SparseArray est qu'en tant qu'objet Android, il doit être simulé pour les tests unitaires. Dans la mesure du possible, j'utilise maintenant les propres objets de Java pour simplifier les tests.
David G
@DavidG Vous pouvez simplement utiliser unmock plugin pour simuler les dépendances Android.
blizzard le
1
Même si vous n'utilisez pas Android, copier la classe dans votre projet n'est pas difficile, cela ne dépend que de 3 autres classes. La licence APL signifie qu'il est autorisé à le faire, quelle que soit la licence avec laquelle vous travaillez.
Yann TM
35

Je suis venu ici en voulant juste un exemple d'utilisation SparseArray. Ceci est une réponse supplémentaire à cela.

Créer un SparseArray

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

A SparseArraymappe des entiers à certains Object, vous pouvez donc remplacer Stringdans l'exemple ci-dessus par n'importe quel autre Object. Si vous mappez des entiers à des entiers, utilisez SparseIntArray.

Ajouter ou mettre à jour des éléments

Utilisez put(ou append) pour ajouter des éléments au tableau.

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

Notez que les intclés n'ont pas besoin d'être en ordre. Cela peut également être utilisé pour modifier la valeur d'une intclé particulière .

Supprimer des éléments

Utilisez remove(ou delete) pour supprimer des éléments du tableau.

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

Le intparamètre est la clé entière.

Rechercher des valeurs pour une clé int

Utilisez getpour obtenir la valeur d'une clé entière.

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

Vous pouvez utiliser get(int key, E valueIfKeyNotFound)si vous souhaitez éviter d'obtenir nulldes clés manquantes.

Itérer sur les éléments

Vous pouvez utiliser keyAtet valueAtcertains index pour parcourir la collection car le SparseArraymaintient un index distinct distinct des intclés.

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

Notez que les clés sont classées par valeur croissante, et non dans l'ordre dans lequel elles ont été ajoutées.

Suragch
la source
18

Pourtant, chaque fois que j'essaie d'utiliser un HashMap avec des clés entières dans un projet Android, intelliJ me dit que je devrais utiliser un SparseArray à la place.

Ce n'est qu'un avertissement de cette documentation de ce tableau fragmenté:

Il est conçu pour être plus efficace en mémoire que l'utilisation d'un HashMap pour mapper des entiers à des objets

Le SparseArrayest fait pour être efficace en mémoire que l'utilisation du HashMap normal, c'est-à-dire qu'il n'autorise pas plusieurs espaces dans le tableau, contrairement à HashMap. Il n'y a rien à craindre, vous pouvez utiliser le HashMap traditionnel si vous ne souhaitez pas vous soucier de l'allocation de mémoire à l'appareil.

Rod_Algonquin
la source
5
Les points concernant la sauvegarde de la mémoire sont évidemment valides, mais je n'ai jamais compris pourquoi Android n'aurait pas pu faire en sorte que SparseArray <T> implémente Map <Integer, T> afin que vous obteniez une implémentation de carte efficace en mémoire - le meilleur des deux mondes.
Paul Boddington
3
@PaulBoddington se souvient également SparseArrayempêche l'entier clé d'être une boîte automatique, ce qui est une autre opération et des performances de coût. plutôt que de mapper, il renverra automatiquement l'entier primitif àInteger
Rod_Algonquin
C'est également vrai, mais s'ils avaient surchargé la méthode put en en incluant une avec signature put (int a, T t), vous seriez toujours en mesure de mettre des paires clé-valeur dans la carte sans que les clés soient automatiquement encadrées. Je pense juste que le Framework de collections est si puissant (l'une des meilleures raisons d'utiliser Java) qu'il est insensé de ne pas en profiter.
Paul Boddington
6
@PaulBoddington Les collections sont basées sur des objets non primitifs, donc cela ne fonctionnera pas dans l'API Collections
Rod_Algonquin
10

Un tableau épars en Java est une structure de données qui mappe des clés à des valeurs. Même idée qu'une carte, mais implémentation différente:

  1. Une carte est représentée en interne sous la forme d'un tableau de listes, où chaque élément de ces listes est une paire clé / valeur. La clé et la valeur sont toutes deux des instances d'objet.

  2. Un tableau fragmenté est simplement constitué de deux tableaux: un tableau de clés (primitives) et un tableau de valeurs (objets). Il peut y avoir des lacunes dans ces indices de tableaux, d'où le terme tableau «clairsemé».

L'intérêt principal du SparseArray est qu'il économise de la mémoire en utilisant des primitives au lieu d'objets comme clé.

Ganesh Katikar
la source
10

Après quelques recherches sur Google, j'essaye d'ajouter des informations aux réponses déjà publiées:

Isaac Taylor a fait une comparaison des performances pour SparseArrays et Hashmaps. Il affirme que

le Hashmap et le SparseArray sont très similaires pour les tailles de structure de données inférieures à 1000

et

lorsque la taille a été augmentée à la marque [...] 10 000, le Hashmap a de meilleures performances avec l'ajout d'objets, tandis que le SparseArray a de meilleures performances lors de la récupération d'objets. [...] À une taille de 100 000 [...] le Hashmap perd très rapidement ses performances

Une comparaison sur Edgblog montre qu'un SparseArray nécessite beaucoup moins de mémoire qu'un HashMap en raison de la plus petite clé (int vs Integer) et du fait que

une instance HashMap.Entry doit garder une trace des références pour la clé, la valeur et l'entrée suivante. De plus, il doit également stocker le hachage de l'entrée en tant qu'int.

En conclusion, je dirais que la différence pourrait être importante si vous allez stocker beaucoup de données dans votre carte. Sinon, ignorez simplement l'avertissement.

Sébastien
la source
4

La documentation android pour un SparseArray dit "Il est généralement plus lent qu'un HashMap traditionnel".

Oui c'est vrai. Mais lorsque vous n'avez que 10 ou 20 éléments, la différence de performance devrait être insignifiante.

Si vous écrivez du code en utilisant HashMaps plutôt que SparseArrays, votre code fonctionnera avec d'autres implémentations de Map et vous pourrez utiliser toutes les API Java conçues pour Maps.

Je pense que le plus souvent, nous utilisons uniquement HashMappour rechercher une valeur associée à une clé alors que SparseArrayc'est vraiment bon pour cela.

Si vous écrivez du code à l'aide de HashMaps plutôt que de SparseArrays, votre code fonctionnera dans des projets non Android.

Le code source de SparseArray est assez simple et facile à comprendre, de sorte que vous ne payez que peu d'efforts pour le déplacer vers d'autres plates-formes (via un simple COPY & Paste).

La carte remplace equals () et hashCode () contrairement à SparseArray

Tout ce que je peux dire, c'est (à la plupart des développeurs) qui s'en soucient?

Un autre aspect important de SparseArrayest qu'il utilise uniquement un tableau pour stocker tous les éléments pendant l' HashMaputilisation Entry, donc SparseArraycoûte beaucoup moins de mémoire qu'un HashMap, voir ceci

Suitianshi
la source
1

Il est malheureux que le compilateur émette un avertissement. Je suppose que HashMap a été largement utilisé pour stocker des éléments.

Les SparseArrays ont leur place. Étant donné qu'ils utilisent un algorithme de recherche binaire pour trouver une valeur dans un tableau, vous devez considérer ce que vous faites. La recherche binaire est O (log n) tandis que la recherche de hachage est O (1). Cela ne signifie pas nécessairement que la recherche binaire est plus lente pour un ensemble de données donné. Cependant, à mesure que le nombre d'entrées augmente, la puissance de la table de hachage prend le dessus. D'où les commentaires où un faible nombre d'entrées peut être égal et peut-être mieux que d'utiliser un HashMap.

Un HashMap n'est aussi bon que le hachage et peut également être affecté par le facteur de charge (je pense que dans les versions ultérieures, ils ignorent le facteur de charge afin qu'il puisse être mieux optimisé). Ils ont également ajouté un hachage secondaire pour s'assurer que le hachage est bon. Aussi la raison pour laquelle SparseArray fonctionne très bien pour relativement peu d'entrées (<100).

Je suggérerais que si vous avez besoin d'une table de hachage et que vous voulez une meilleure utilisation de la mémoire pour les entiers primitifs (pas de boxing automatique), etc., essayez trove. ( http://trove.starlight-systems.com - licence LGPL). (Aucune affiliation avec trove, tout comme leur bibliothèque)

Avec le bâtiment multi-dex simplifié que nous avons, vous n'avez même pas besoin de reconditionner pour ce dont vous avez besoin. (trove a beaucoup de classes)

Bruce
la source