SparseArray vs HashMap

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

  1. La documentation Android pour un SparseArray dit “Il est généralement plus lent qu’un HashMap traditionnel”.
  2. Si vous écrivez du code à l’aide de HashMap plutôt que de SparseArray 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 HashMap plutôt que SparseArray votre code fonctionnera dans des projets non Android.
  4. La carte remplace equals() et hashCode() contrairement à SparseArray .

Pourtant, chaque fois que j’essaye d’utiliser un HashMap avec des clés entières dans un projet Android, IntelliJ me dit que je devrais plutôt utiliser un SparseArray . Je trouve cela vraiment difficile à comprendre. Est-ce que quelqu’un connaît des raisons impérieuses d’utiliser SparseArray s?

SparseArray peut être utilisé pour remplacer HashMap lorsque la clé est un type primitif. Il existe certaines variantes pour différents types de clé / valeur, même si tous ne sont pas accessibles au public.

Les avantages sont les suivants:

  • Sans allocation
  • Pas de boxe

Désavantages:

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

HashMap peut être remplacé par ce qui suit:

 SparseArray  SparseBooleanArray  SparseIntArray  SparseLongArray  LongSparseArray  LongSparseLongArray  //this is not a public class //but can be copied from Android source code 

En termes de mémoire, voici un exemple de SparseIntArray vs HashMap 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 = 8 072 octets

HashMap :

 class HashMap { Entry[] table; Entry forNull; int size; int modCount; int threshold; Set keys Set> ensortinges; Collection values; } 

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

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

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

Le package java.lang.instrument contient des méthodes utiles pour les opérations avancées, telles que la vérification de la taille d’un object avec getObjectSize(Object objectToSize) .

Des informations supplémentaires sont disponibles dans la documentation officielle 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 premier élément) + (taille du deuxième élément)

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 plutôt utiliser un SparseArray.

Ce n’est qu’un avertissement à partir de cette documentation de ce tableau fragmenté:

Il est destiné à être plus efficace en termes de mémoire que l’utilisation d’un HashMap pour mapper des entiers vers des objects.

Le SparseArray est conçu pour être efficace en SparseArray de mémoire que l’utilisation du HashMap standard, c’est-à-dire qu’il ne permet 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.

Je suis venu ici juste pour avoir un exemple d’utilisation de SparseArray . Ceci est une réponse supplémentaire pour cela.

Créer un SparseArray

 SparseArray sparseArray = new SparseArray<>(); 

Un SparseArray mappe des nombres entiers à un Object , vous pouvez donc remplacer la Ssortingng dans l’exemple ci-dessus par un autre Object . Si vous mappez des entiers sur des entiers, utilisez SparseIntArray .

Ajouter ou mettre à jour des éléments

Utilisez put (ou append ) pour append 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 clés int n’ont pas besoin d’être dans l’ordre. Cela peut également être utilisé pour modifier la valeur d’une clé int particulière.

Supprimer des éléments

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

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

Le paramètre int est la clé entière.

Valeurs de recherche pour une clé int

Utilisez get pour obtenir la valeur d’une clé entière.

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

Vous pouvez utiliser get(int key, E valueIfKeyNotFound) si vous voulez éviter d’être null pour les clés manquantes.

Itérer sur les objects

Vous pouvez utiliser keyAt et valueAt pour indexer la collection car SparseArray conserve un index distinct des clés int .

 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 en valeur croissante, pas dans l'ordre dans lequel elles ont été ajoutées.

Un tableau fragmenté en Java est une structure de données qui associe 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, chaque élément de ces listes étant une paire clé / valeur. La clé et la valeur sont toutes deux des instances d’object.

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

Le principal intérêt de SparseArray est qu’il permet d’économiser de la mémoire en utilisant des primitives au lieu d’objects comme clé.

Après quelques recherches sur Google, j’essaie d’append des informations aux personnes déjà postées:

Isaac Taylor a fait une comparaison de performance pour SparseArrays et Hashmaps. Il affirme que

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

et

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

Une comparaison sur Edgblog montre qu’un SparseArray a besoin de beaucoup moins de mémoire qu’un HashMap à cause de la plus petite clé (int vs Integer) et du fait que

une instance HashMap.Entry doit conserver la 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 sous la forme d’un int.

En conclusion, je dirais que la différence pourrait avoir son importance si vous stockez beaucoup de données dans votre carte. Sinon, ignorez simplement l’avertissement.

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 doit être négligeable.

Si vous écrivez du code à l’aide de HashMaps plutôt que de 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 HashMap pour rechercher une valeur associée à une clé alors que SparseArray est vraiment efficace.

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 () alors que SparseArray ne le fait pas

Tout ce que je peux dire, c’est que (pour la plupart des développeurs)

Un autre aspect important de SparseArray est qu’il n’utilise qu’un tableau pour stocker tous les éléments alors que HashMap utilise Entry , SparseArray coûte donc beaucoup moins de mémoire qu’un HashMap , voir ceci

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

SparseArrays ont leur place. Étant donné qu’ils utilisent un algorithme de recherche binary pour trouver une valeur dans un tableau, vous devez tenir compte de ce que vous faites. La recherche binary est O (log n) alors que la recherche de hachage est O (1). Cela ne signifie pas nécessairement que la recherche binary est plus lente pour un dataset donné. Cependant, à mesure que le nombre d’entrées augmente, la puissance de la table de hachage prend le relais. D’où les commentaires où le faible nombre d’entrées peut être égal et peut-être meilleur qu’avec un HashMap.

Un HashMap est seulement 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 pour être mieux optimisé). Ils ont également ajouté un hachage secondaire pour s’assurer que le hachage est bon. La raison pour laquelle SparseArray fonctionne très bien pour relativement peu d’entrées (<100).

Je suggère que si vous avez besoin d’une table de hachage et que vous souhaitiez une meilleure utilisation de la mémoire pour les nombres entiers primitifs (pas de boxe 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é, vous n’avez même pas besoin de reconditionner les troves pour vos besoins. (trove a beaucoup de cours)