Mémoire aérienne de Java HashMap comparée à ArrayList
je me demande Quelle est la mémoire au-dessus de java HashMap comparée à ArrayList?
mise à jour:
je voudrais améliorer la vitesse pour la recherche de valeurs spécifiques d'un grand pack (6 Millions+) d'objets identiques.
ainsi, je pense utiliser un ou plusieurs HashMap au lieu d'utiliser ArrayList. Mais je me demande ce qui est au-dessus de HashMap.
jusqu'à comme je comprends, la clé n'est pas stockée, seulement le hachage de la clé, donc il devrait être quelque chose comme Taille du hachage de l'objet + un pointeur .
mais quelle fonction de hachage est utilisée? Est-ce celui offert par L'objet ou un autre?
13 réponses
si vous comparez HashMap avec ArrayList, je présume que vous faites une sorte de recherche/indexation de L'ArrayList, comme la recherche binaire ou la table de hachage personnalisée...? Parce que une .get (key) à travers 6 millions d'entrées serait infaisable en utilisant une recherche linéaire.
en utilisant cette hypothèse, j'ai fait quelques tests empiriques et en arriver à la conclusion que "vous pouvez stocker 2,5 fois plus de petits objets dans la même quantité de RAM si vous utilisez ArrayList avec la recherche binaire ou la coutume de hachage de la carte de mise en œuvre, par rapport à table de hachage". Mon test était basé sur de petits objets contenant seulement 3 champs, dont un est la clé, et la clé est un entier. J'ai utilisé un JDK 1.6 de 32 bits. Voir ci-dessous les mises en garde sur ce chiffre de "2,5".
les points clés à noter sont:
(a) ce n'est pas l'espace requis pour les références ou le" facteur de charge " qui vous tue, mais plutôt le plafond requis pour la création d'un objet. Si la clé est un type primitif, ou un combinaison de 2 ou plus de valeurs primitives ou de référence, puis chaque clé aura besoin de son propre objet, qui porte un au-dessus de 8 bytes.
(b) D'après mon expérience, vous avez généralement besoin de la clé en tant que partie de la valeur (par exemple, pour stocker des dossiers clients, indexés par ID client, vous voulez toujours l'id client en tant que partie de l'objet client). Cela signifie QU'il est un peu gaspilleur IMO qu'un HashMap stocke séparément les références aux clés et aux valeurs.
mises en garde:
-
le type le plus courant utilisé pour les clés HashMap est String. La création d'objet au-dessus ne s'applique pas ici donc la différence serait moins.
-
j'ai obtenu un chiffre de 2,8, soit 8880502 entrées insérées dans L'ArrayList par rapport à 3148004 dans le HashMap on-Xmx256M JVM, mais mon facteur de charge ArrayList était de 80% et mes objets étaient assez petits - 12 octets plus 8 octet objet overhead.
-
ma figure, et mon implémentation, exigent que la clé soit contenue dans la valeur, sinon j'aurais le même problème avec la création d'objet overhead et ce serait juste une autre implémentation de HashMap.
mon 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);
}
}
la chose La plus simple serait de regarder la source, et la travailler de cette façon. Cependant, vous comparez vraiment des pommes et des oranges - les listes et les cartes sont conceptuellement très distinctes. Il est rare que vous choisiriez entre eux sur la base de l'utilisation de la mémoire.
Quel est le contexte derrière cette question?
Tout ce qui est stocké dans l'un ou l'autre est des pointeurs. Selon votre architecture, un pointeur devrait être 32 ou 64 bits (ou plus ou moins)
une liste de tableau de 10 tend à attribuer 10" pointeurs " à un minimum (et aussi quelque chose d'une fois au-dessus de la tête).
une carte doit allouer le double (20 points) parce qu'elle stocke deux valeurs à la fois. En plus de ça, il doit stocker le "Hash". qui devrait être plus grande que la carte, à une charge de 75%, il Devrait être autour de 13 valeurs 32 bits (hashes).
donc si vous voulez une réponse spontanée, le rapport devrait être d'environ 1:3.25, mais vous ne parlez que de stockage de pointeur--très petit à moins que vous stockiez un nombre massif d'objets--et si c'est le cas, l'utilité de pouvoir faire référence instantanément (HashMap) vs iterate (array) devrait être beaucoup plus significative que la taille de la mémoire.
oh, aussi: Les tableaux peuvent être adaptés à la taille exacte de votre collection. HashMaps peut aussi bien si vous spécifiez la taille, mais si elle "croît" au-delà de cette taille, il va réattribuer un plus grand tableau et ne pas utiliser une partie de celui-ci, de sorte qu'il peut y avoir un peu de gaspillage là aussi.
Je n'ai pas de réponse pour vous non plus, mais une recherche rapide sur google a révélé une fonction en Java qui pourrait aider.
Runtime.getRuntime ().freeMemory ();
donc je propose que vous peupliez un HashMap et un ArrayList avec les mêmes données. Enregistrer la mémoire libre, supprimer le premier objet, enregistrer la mémoire, supprimer le second objet, enregistrer la mémoire, calculer les différences,..., le profit!!!
vous devriez probablement faire ceci avec des magnitudes de données. c'est-à-dire commencer par 1000, puis 10000, 100000, 1000000.
EDIT: Corrigé, grâce à amischiefr.
EDIT: Désolé d'avoir édité votre message, mais c'est assez important si vous allez utiliser ceci (et c'est un peu trop pour un commentaire) . freeMemory ne fonctionne pas comme vous le pensez. D'abord, sa valeur est changée par la collecte des ordures. Deuxièmement, sa valeur est modifiée lorsque java alloue plus de mémoire. Le simple fait d'utiliser l'appel gratuit ne fournit pas de données utiles.
essayez ceci:
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()));
}
ou vous pouvez retourner la mémoire utilisée et la stocker, puis la comparer à une valeur ultérieure. Dans tous les cas, souvenez-vous des 2 gcs et soustrayez de totalMemory().
Encore une fois, désolé pour éditer ton post!
Hashmaps essayer de maintenir un facteur de charge (généralement 75% plein), vous pouvez penser à un hashmap comme une liste de tableaux peu remplis. Le problème dans une comparaison directe dans la taille est ce facteur de charge de la carte croît pour répondre à la taille des données. ArrayList d'autre part grandit pour répondre à son besoin en doublant sa taille de réseau interne. Pour des tailles relativement petites, Ils sont comparables, mais comme vous emballez de plus en plus de données dans la carte, il nécessite beaucoup de références vides afin de maintenir la performance de hash.
dans les deux cas, je recommande d'amortir la taille attendue des données avant de commencer à ajouter. Cela donnera aux implémentations un meilleur cadre initial et consommera probablement moins dans les deux cas.
mise à jour:
basé sur votre problème mis à jour, vérifiez les listes vitrées . C'est un petit outil soigné écrit par certains des gens de Google pour faire opérations similaires à celle que vous décrivez. Il est aussi très rapide. Permet le regroupement, le filtrage, la recherche, etc.
table de hachage maintenir une référence à la valeur et une référence à la clé.
ArrayList il suffit de tenir une référence à la valeur.
ainsi, en supposant que la clé utilise la même mémoire de la valeur, HashMap utilise 50% de mémoire en plus ( bien qu'à proprement parler , n'est pas le HashMap qui utilise cette mémoire parce qu'il garde juste une référence à elle)
dans l'autre main HashMap fournit constante-time performance for the basic operations (get and put) ainsi, bien qu'il puisse utiliser plus de mémoire, l'obtention d'un élément peut être beaucoup plus rapide en utilisant un HashMap qu'un ArrayList.
donc, la prochaine chose que vous devez faire est ne pas se soucier de qui utilise plus de mémoire mais ce qui sont-ils bon pour .
en utilisant la structure de données correcte pour votre programme sauve plus de CPU / Mémoire que la façon dont le la Bibliothèque est implémentée en dessous.
MODIFIER
après la réponse de Grant Welch j'ai décidé de mesurer pour 2.000.000 entiers.
voici le code source
C'est la sortie
$
$javac MemoryUsage.java
Note: MemoryUsage.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
$java -Xms128m -Xmx128m MemoryUsage
Using ArrayListMemoryUsage@8558d2 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
ArrayListMemoryUsage@8558d2 size: 2000000
$
$java -Xms128m -Xmx128m MemoryUsage H
Using HashMapMemoryUsage@8558d2 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
HashMapMemoryUsage@8558d2 size: 2000000
en gros, vous devriez utiliser le "bon outil pour le travail". Puisqu'il y a différentes instances où vous aurez besoin d'une paire clé/valeur (où vous pouvez utiliser un HashMap ) et différentes instances où vous aurez juste besoin d'une liste de valeurs (où vous pouvez utiliser un ArrayList ), alors la question de "lequel utilise le plus de mémoire", à mon avis, est sans objet, car ce n'est pas une considération de choisir l'un plutôt que l'autre.
mais pour répondre à la question, depuis HashMap stocke les paires clé / valeur alors que ArrayList stocke juste les valeurs, Je supposerais que l'ajout des clés seules au HashMap signifierait qu'il prend plus de mémoire, en supposant, bien sûr, que nous les comparons par la même valeur type (par exemple où les valeurs dans les deux sont des chaînes).
je pense que la mauvaise question est posée ici.
si vous souhaitez améliorer la vitesse à laquelle vous pouvez rechercher un objet dans un List contenant six millions d'entrées, alors vous devriez regarder dans Comment rapide ces opérations de récupération de type de données effectuer.
comme d'habitude, les Javadocs pour ces classes indiquent assez clairement quel type de performance ils offrent:
cette implémentation fournit une performance en temps constant pour les opérations de base (get et put), en supposant que la fonction de hachage disperse correctement les éléments entre les seaux.
cela signifie que HashMap.get(clé) est O(1) .
La taille, isEmpty, get, set, les opérations iterator et listIterator sont exécutées en temps constant. L'opération d'ajout s'exécute en temps constant amorti, qui est, l'ajout de n éléments nécessite O(n) fois. Toutes les autres opérations fonctionnent en temps linéaire (en gros).
cela signifie que la plupart des opérations de ArrayList sont O(1) , mais probablement pas ceux que vous utiliseriez pour trouver des objets qui correspondent à une certaine valeur.
si vous itérez sur chaque élément dans le ArrayList et l'essai pour l'égalité, ou en utilisant contains() , alors cela signifie que votre opération est en cours à O(n) temps (ou pire).
si vous ne connaissez pas la notation O(1) ou O(n) , il s'agit de la durée de l'opération. Dans ce cas, si vous pouvez obtenir une performance à temps constant, vous voulez la prendre. Si HashMap.get() est O(1) cela signifie que les opérations de récupération prennent à peu près le même temps malgré du nombre d'entrées sur la carte.
le fait que quelque chose comme ArrayList.contains() est O(n) signifie que le temps qu'il prend augmente avec la taille de la liste; donc itérer par un ArrayList avec six millions d'entrées ne sera pas très efficace du tout.
Je ne sais pas le nombre exact, mais les Hachmaps sont beaucoup plus lourds. En comparant les deux, la représentation interne D'ArrayList est évidente, mais les HashMaps retiennent les objets Entry (Entry) qui peuvent gonfler votre consommation de mémoire.
ce n'est pas beaucoup plus grand, mais c'est plus grand. Une excellente façon de visualiser cela serait avec un profileur dynamique tel que YourKit qui vous permet de voir toutes les allocations tas. C'est assez sympa.
si vous considérez deux ArrayLists vs un Hashmap, c'est indéterminé; les deux sont des structures de données partiellement complètes. Si vous comparez vecteur vs Hashtable, vecteur est probablement plus efficace en mémoire, car il alloue seulement l'espace qu'il utilise, alors que les Hashtables allouent plus d'espace.
si vous avez besoin d'une paire de valeurs clés et que vous ne faites pas un travail incroyablement gourmand en mémoire, utilisez simplement le Hashmap.
comme Jon Skeet l'a noté, ce sont des structures complètement différentes. Une carte (comme HashMap) est une correspondance d'une valeur à une autre - c'est-à-dire que vous avez une clé qui correspond à une valeur, dans un type de relation clé - >valeur. La clé est hachée, et est placée dans un tableau pour une recherche rapide.
une liste, d'un autre côté, est un ensemble d'éléments avec ordre - ArrayList se trouve à utiliser un tableau comme mécanisme de stockage arrière, mais cela n'est pas pertinent. Chaque élément indexé est un seul élément dans la liste.
edit: d'après votre commentaire, j'ai ajouté les informations suivantes:
la clé est stockée dans une hashmap. C'est parce qu'un hachage n'est pas garanti d'être unique pour deux éléments différents. Ainsi, la clé doit être stockée en cas de collision. Si vous voulez simplement voir si un élément existe dans un ensemble d'éléments, utilisez un ensemble (l'implémentation standard de ce HashSet). Si l'ordre des questions, mais vous avez besoin d'une recherche rapide, utilisez un LinkedHashSet, car il garde l'ordre les éléments ont été insérés. Le temps de recherche est O (1) sur les deux, mais le temps d'insertion est légèrement plus long sur un ensemble LinkedHashSet. Utilisez une carte seulement si vous faites une correspondance d'une valeur à une autre - si vous avez simplement un ensemble d'objets uniques, utilisez un ensemble, si vous avez commandé des objets, utilisez une liste.
Ce site listes de la consommation de mémoire pour plusieurs communément (et pas si souvent) ont utilisé des structures de données. De là, on peut voir que le HashMap prend environ 5 fois l'espace d'un ArrayList . La table attribuera également un objet supplémentaire par entrée.
si vous avez besoin d'un ordre d'itération prévisible et utilisez un LinkedHashMap , la consommation de mémoire sera encore plus élevée.
Vous pouvez faire votre propre mémoire mesures avec mesureur de mémoire .
il y a deux faits importants à noter cependant:
- un grand nombre de structures de données (y compris
ArrayListetHashMap) allouent de l'espace plus qu'ils n'en ont besoin actuellement, parce que sinon ils devraient fréquemment exécuter une opération de redimensionnement coûteuse. Ainsi, la consommation de mémoire par élément dépend du nombre d'éléments dans la collection. Par exemple, unArrayListavec les paramètres par défaut utilise la même mémoire pour 0 à 10 éléments. - Comme d'autres l'ont dit, les clés de la carte sont stockées, trop. Donc, si ils ne sont pas dans la mémoire de toute façon, vous devrez ajouter ce coût mémoire, aussi. Un objet supplémentaire prendra généralement 8 bytes de overhead seul, plus la mémoire pour ses champs, et peut-être un peu de rembourrage. Donc, ce sera aussi beaucoup de mémoire.