Si vous êtes en comparant HashMap avec ArrayList, je présume que vous êtes en train de faire une sorte de recherche/indexation de la liste de tableaux, tels que les binaires de recherche ou de la coutume de la table de hachage...? Parce que une .get(clé) à 6 millions d'entrées serait impossible à l'aide d'une recherche linéaire.
À l'aide de cette hypothèse, j'ai fait quelques tests empiriques et arriver à la conclusion que "Vous pouvez stocker 2,5 fois plus petits objets dans la même quantité de RAM si vous utilisez ArrayList avec les binaires de recherche ou de la coutume de hachage de la carte de mise en œuvre, par rapport à table de hachage". Mon test était basé sur les petits objets ne contenant que 3 champs, dont l'une est la clé, et la clé est un nombre entier. J'ai utilisé un 32 bits jdk 1.6. Voir ci-dessous pour les mises en garde sur cette figure de la "2.5".
Les principaux éléments à noter sont:
(a) il n'est pas l'espace requis pour les références ou "facteur de charge" qui vous tue, mais plutôt les frais généraux nécessaires pour la création d'objet. Si la clé est un type primitif, ou une combinaison de 2 ou plusieurs primitives ou de valeurs de référence, puis chaque clé aura besoin de son propre objet, qui transporte une charge de 8 octets.
(b) Dans mon expérience, vous devez généralement la clé, comme une partie de la valeur, (par exemple pour stocker les enregistrements de client, indexé par le numéro de client, vous voulez toujours l'id client dans le cadre de l'objet Client). Cela signifie qu'il est de l'OMI, un peu de gaspillage qu'une HashMap séparément stocke les références de clés et de valeurs.
Mises en garde:
Le type le plus commun utilisé pour HashMap clés de la Chaîne. La création de l'objet de frais généraux ne s'applique pas ici, donc, la différence serait moindre.
J'ai obtenu un chiffre de 2,8, étant 8880502 entrées inséré dans la liste de tableaux en comparaison avec 3148004 dans la table de hachage sur -Xmx256M JVM, mais mon ArrayList facteur de charge est de 80% et mes objets étaient assez petites - 12 octets 8 octets de l'objet de frais généraux.
Ma figure et ma mise en œuvre, nécessite que la clé est contenue dans la valeur, sinon j'aurais le même problème avec la création d'un objet de frais généraux et ce serait juste une autre mise en œuvre de la table de hachage.
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);
}
}
