Quelle est la capacité et le facteur de charge optimaux pour un HashMap de taille fixe?

Question

Je suis à essayer de comprendre la capacité optimale et le facteur de charge d'un cas précis. Je pense que j'ai compris l'essentiel, mais je serais toujours reconnaissante pour une confirmation de quelqu'un de plus informé que moi. :)

Si je sais que ma table de hachage va se remplir à contenir, disons, 100 objets, et passent la plupart du temps avoir 100 objets, je devine que les valeurs optimales sont de capacité initiale de 100 et le facteur de charge 1? Ou dois-je besoin d'une capacité de 101, ou existe-il d'autres problèmes?

EDIT: OK, j'ai mis de côté quelques heures et fait quelques tests. Voici les résultats:

• Curieusement, la capacité, la capacité de+1, capacité+2, capacité-1 et de même capacité de 10 tous rendement exactement les mêmes résultats. Je m'attends au moins de la capacité-1 et capacité de 10 à donner de moins bons résultats.
• L'aide initiale de la capacité (par opposition à l'utilisation de la valeur par défaut de 16 ans) donne de la malformation put() de l'amélioration - jusqu'à 30% plus rapide.
• En utilisant le facteur de charge de 1 donne le même rendement pour le petit nombre d'objets, et de meilleures performances pour un plus grand nombre d'objets (>100000). Cependant, ceci n'améliore pas de manière proportionnelle au nombre d'objets; je soupçonne il y a un autre facteur qui influe sur les résultats.
• get() est un peu différente pour différents nombre d'objets/de la capacité, mais si cela peut légèrement varier au cas par cas, en général, il n'est pas affecté par la capacité initiale ou le facteur de charge.

EDIT2: Ajout de quelques diagrammes de ma part. Voici l'un illustrant la différence entre le facteur de charge 0,75 et 1, dans les cas où j'initialise HashMap et de le remplir à pleine capacité. Sur l'échelle y est de temps en ms (en bas c'est mieux), et x est l'échelle de la taille (nombre d'objets). Depuis les changements de taille linéaire, le temps nécessaire croît linéairement.

Donc, nous allons voir ce que j'ai. Les deux graphiques suivants montrent la différence dans les facteurs de charge. Premier graphique montre ce qui arrive quand HashMap est rempli à pleine capacité; facteur de charge de 0,75 effectue pire en raison de redimensionnement. Cependant, il n'est pas systématiquement le pire, et il y a toutes sortes de bosses et de houblon - je suppose que la GC est l'un des principaux enjeux dans ce. Facteur de charge de 1,25 effectue le même que le 1, il n'est donc pas inclus dans le graphique.

Ce graphique prouve que de 0,75 était pire à cause de redimensionnement; si nous remplir la table de hachage à la moitié de sa capacité, de 0,75 est pas pire, juste... différent (et il devrait utiliser moins de mémoire et ont unnoticably mieux itération de la performance).

Une chose que je veux montrer. Il s'agit d'obtenir des performances pour l'ensemble des trois facteurs de charge et les différents HashMap tailles. De façon constante constante avec un peu de variation, sauf pour un pic pour le facteur de charge 1. J'avais vraiment envie de savoir ce que c'est (probablement GC, mais qui sait).

Et voici le code pour ceux que ça intéresse:

import java.util.HashMap;
import java.util.Map;

public class HashMapTest {

  // capacity - numbers high as 10000000 require -mx1536m -ms1536m JVM parameters
  public static final int CAPACITY = 10000000;
  public static final int ITERATIONS = 10000;

  // set to false to print put performance, or to true to print get performance
  boolean doIterations = false;

  private Map<Integer, String> cache;

  public void fillCache(int capacity) {
    long t = System.currentTimeMillis();
    for (int i = 0; i <= capacity; i++)
      cache.put(i, "Value number " + i);

    if (!doIterations) {
      System.out.print(System.currentTimeMillis() - t);
      System.out.print("\t");
    }
  }

  public void iterate(int capacity) {
    long t = System.currentTimeMillis();

    for (int i = 0; i <= ITERATIONS; i++) {
      long x = Math.round(Math.random() * capacity);
      String result = cache.get((int) x);
    }

    if (doIterations) {
      System.out.print(System.currentTimeMillis() - t);
      System.out.print("\t");
    }
  }

  public void test(float loadFactor, int divider) {
    for (int i = 10000; i <= CAPACITY; i+= 10000) {
      cache = new HashMap<Integer, String>(i, loadFactor);
      fillCache(i / divider);
      if (doIterations)
        iterate(i / divider);
    }
    System.out.println();
  }

  public static void main(String[] args) {
    HashMapTest test = new HashMapTest();

    // fill to capacity
    test.test(0.75f, 1);
    test.test(1, 1);
    test.test(1.25f, 1);

    // fill to half capacity
    test.test(0.75f, 2);
    test.test(1, 2);
    test.test(1.25f, 2);
  }

}

Answer 1

C'est un assez grand fil, sauf il y a une chose essentielle que vous êtes absent. Vous avez dit:

Curieusement, la capacité, la capacité de+1, capacité+2, capacité-1 et de même capacité de 10 tous rendement exactement les mêmes résultats. Je m'attends au moins de la capacité-1 et capacité de 10 à donner de moins bons résultats.

Le code source sauts capacité initiale de la prochaine puissance la plus élevée de deux de manière interne. Cela signifie que, par exemple, les premières capacités de 513, 600, 700, 800, 900, 1000, et 1024 seront tous utilisent la même capacité initiale (1024). Ce n'est pas invalider le test fait par @G_H cependant, il faut savoir que cela est fait avant d'analyser ses résultats. Et il explique le comportement étrange de certains de ces tests.

C'est le constructeur de droit pour le JDK source:

/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and load factor.
 *
 * @param  initialCapacity the initial capacity
 * @param  loadFactor      the load factor
 * @throws IllegalArgumentException if the initial capacity is negative
 *         or the load factor is nonpositive
 */
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);

    // Find a power of 2 >= initialCapacity
    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;

    this.loadFactor = loadFactor;
    threshold = (int)(capacity * loadFactor);
    table = new Entry[capacity];
    init();
}

Answer 2

Juste aller avec 101. Je ne suis pas vraiment sûr que c'est nécessaire, mais il ne pouvait pas être en vaut la chandelle jamais la peine de trouver à coup sûr.

...il suffit d'ajouter le 1.

---

EDIT: une justification à ma réponse.

D'abord, je suis en supposant que votre HashMap n'augmentera pas au-delà de l' 100; si elle le fait, vous devez laisser le facteur de charge tel qu'il est. De même, si votre préoccupation est la performance, de quitter le facteur de charge comme c'est. Si votre préoccupation est de mémoire, vous pouvez enregistrer certains par la définition de la statique de la taille. Cela pourrait peut-être être la peine de le faire si vous êtes entasser beaucoup de choses dans la mémoire; c'est à dire, de stocker un grand nombre de cartes, ou de créer des tas d'espace-soulignant la taille des cartes.

Deuxièmement, je choisis la valeur 101 car il offre une meilleure lisibilité... si je suis à la recherche de votre code par la suite et de voir que vous avez la capacité d' 100 et que vous êtes en train de charger, il avec 100 éléments, je vais lire la Javadoc pour s'assurer qu'il n'est pas redimensionné quand il atteint précisément 100. Bien sûr, je ne vais pas y trouver la réponse, donc je vais devoir chercher à la source. Ce n'est pas la peine... il suffit de laisser 101 et tout le monde est content et personne n'est à la recherche si le code-source de l' java.util.HashMap. Hoorah.

Troisièmement, la demande que la définition de la HashMap de la capacité exacte de ce que vous attendez avec un facteur de charge de l' 1 "va tuer votre recherche et d'insertion de la performance" n'est tout simplement pas vrai, même si elle est faite en caractères gras.

...si vous avez n des seaux, et vous attribuer aléatoirement n articles en n seaux, oui, vous allez finir avec les éléments dans le même seau, bien sûr... mais ce n'est pas la fin du monde... dans la pratique, il est juste un couple de plus équivaut à des comparaisons. En fait, il y a l'esp. peu de différence quand vous considérez que l'alternative est d'attribuer n articles en n/0.75 des seaux.

Pas besoin de prendre mon mot pour lui...

---

Test rapide de code:

static Random r = new Random();

public static void main(String[] args){
    int[] tests = {100, 1000, 10000};
    int runs = 5000;

    float lf_sta = 1f;
    float lf_dyn = 0.75f;

    for(int t:tests){
        System.err.println("=======Test Put "+t+"");
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        long norm_put = testInserts(map, t, runs);
        System.err.print("Norm put:"+norm_put+" ms. ");

        int cap_sta = t;
        map = new HashMap<Integer,Integer>(cap_sta, lf_sta);
        long sta_put = testInserts(map, t, runs);
        System.err.print("Static put:"+sta_put+" ms. ");

        int cap_dyn = (int)Math.ceil((float)t/lf_dyn);
        map = new HashMap<Integer,Integer>(cap_dyn, lf_dyn);
        long dyn_put = testInserts(map, t, runs);
        System.err.println("Dynamic put:"+dyn_put+" ms. ");
    }

    for(int t:tests){
        System.err.println("=======Test Get (hits) "+t+"");
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        fill(map, t);
        long norm_get_hits = testGetHits(map, t, runs);
        System.err.print("Norm get (hits):"+norm_get_hits+" ms. ");

        int cap_sta = t;
        map = new HashMap<Integer,Integer>(cap_sta, lf_sta);
        fill(map, t);
        long sta_get_hits = testGetHits(map, t, runs);
        System.err.print("Static get (hits):"+sta_get_hits+" ms. ");

        int cap_dyn = (int)Math.ceil((float)t/lf_dyn);
        map = new HashMap<Integer,Integer>(cap_dyn, lf_dyn);
        fill(map, t);
        long dyn_get_hits = testGetHits(map, t, runs);
        System.err.println("Dynamic get (hits):"+dyn_get_hits+" ms. ");
    }

    for(int t:tests){
        System.err.println("=======Test Get (Rand) "+t+"");
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        fill(map, t);
        long norm_get_rand = testGetRand(map, t, runs);
        System.err.print("Norm get (rand):"+norm_get_rand+" ms. ");

        int cap_sta = t;
        map = new HashMap<Integer,Integer>(cap_sta, lf_sta);
        fill(map, t);
        long sta_get_rand = testGetRand(map, t, runs);
        System.err.print("Static get (rand):"+sta_get_rand+" ms. ");

        int cap_dyn = (int)Math.ceil((float)t/lf_dyn);
        map = new HashMap<Integer,Integer>(cap_dyn, lf_dyn);
        fill(map, t);
        long dyn_get_rand = testGetRand(map, t, runs);
        System.err.println("Dynamic get (rand):"+dyn_get_rand+" ms. ");
    }
}

public static long testInserts(HashMap<Integer,Integer> map, int test, int runs){
    long b4 = System.currentTimeMillis();

    for(int i=0; i<runs; i++){
        fill(map, test);
        map.clear();
    }
    return System.currentTimeMillis()-b4;
}

public static void fill(HashMap<Integer,Integer> map, int test){
    for(int j=0; j<test; j++){
        if(map.put(r.nextInt(), j)!=null){
            j--;
        }
    }
}

public static long testGetHits(HashMap<Integer,Integer> map, int test, int runs){
    long b4 = System.currentTimeMillis();

    ArrayList<Integer> keys = new ArrayList<Integer>();
    keys.addAll(map.keySet());

    for(int i=0; i<runs; i++){
        for(int j=0; j<test; j++){
            keys.get(r.nextInt(keys.size()));
        }
    }
    return System.currentTimeMillis()-b4;
}

public static long testGetRand(HashMap<Integer,Integer> map, int test, int runs){
    long b4 = System.currentTimeMillis();

    for(int i=0; i<runs; i++){
        for(int j=0; j<test; j++){
            map.get(r.nextInt());
        }
    }
    return System.currentTimeMillis()-b4;
}

---

Résultats Du Test:

=======Test Put 100
Norm put:78 ms. Static put:78 ms. Dynamic put:62 ms. 
=======Test Put 1000
Norm put:764 ms. Static put:763 ms. Dynamic put:748 ms. 
=======Test Put 10000
Norm put:12921 ms. Static put:12889 ms. Dynamic put:12873 ms. 
=======Test Get (hits) 100
Norm get (hits):47 ms. Static get (hits):31 ms. Dynamic get (hits):32 ms. 
=======Test Get (hits) 1000
Norm get (hits):327 ms. Static get (hits):328 ms. Dynamic get (hits):343 ms. 
=======Test Get (hits) 10000
Norm get (hits):3304 ms. Static get (hits):3366 ms. Dynamic get (hits):3413 ms. 
=======Test Get (Rand) 100
Norm get (rand):63 ms. Static get (rand):46 ms. Dynamic get (rand):47 ms. 
=======Test Get (Rand) 1000
Norm get (rand):483 ms. Static get (rand):499 ms. Dynamic get (rand):483 ms. 
=======Test Get (Rand) 10000
Norm get (rand):5190 ms. Static get (rand):5362 ms. Dynamic get (rand):5236 ms. 

re: ↑ — il à propos de ce →||← beaucoup de différence entre les différents paramètres.

---

En ce qui concerne ma réponse originale à cette question (le bit au-dessus de la première ligne horizontale), il a été délibérément glib parce que dans la plupart des cas, ce type de micro-optimisation n'est pas bon.

Answer 3

De la HashMap JavaDoc:

En règle générale, le facteur de charge par défaut (.75) offre un bon compromis entre le temps et l'espace des coûts. Des valeurs plus élevées diminution de l'espace supplémentaire mais l'augmentation du coût de recherche (qui se traduit dans la plupart des opérations de la table de hachage de la classe, y compris les obtenir et de les mettre). Le nombre d'entrées dans la carte et de son facteur de charge doit être pris en compte lors de la définition de sa capacité initiale, de façon à minimiser le nombre de ressasser des opérations. Si la capacité initiale est plus grande que le nombre maximal d'entrées divisé par le facteur de charge, pas de ressasser les opérations se produira jamais.

Donc, si vous vous attendez à 100 entrées, peut-être un facteur de charge de 0,75 et une capacité initiale de plafond(100/0.75) serait un plus. C'est 134.

Je dois l'avouer, je ne suis pas certain pourquoi de recherche coût serait plus élevé que le facteur de charge. Tout simplement parce que la table de hachage est plus "plein" ne veut pas dire que plus les objets seront placés dans le même seau, droit? Qui ne dépend que de leur code de hachage, si je ne me trompe pas. Donc en supposant un décent code de hachage de propagation, ne devrait pas encore être O(1) quel que soit le facteur de charge?

EDIT: je devrais lire plus avant de poster... bien sûr, le code de hachage ne peut pas directement la carte à l'interne de l'index. Il doit être réduite à une valeur qui correspond à la capacité actuelle. Ce qui signifie que la plus grande de votre capacité initiale, la plus petite, vous pouvez vous attendre le nombre de collisions de hachage. Le choix d'une capacité initiale exactement la même taille (ou +1) de votre objet avec un facteur de charge de 1 va en effet, assurez-vous que votre carte n'est jamais redimensionnée. Cependant, il va tuer votre recherche et d'insertion de la performance. Un resize est encore relativement rapide et ne pourrait se produire que peut-être une fois, alors que des recherches sont faites sur quasiment tous les travaux pertinents avec la carte. En conséquence, l'optimisation rapide des recherches est vraiment ce que vous voulez ici. Vous pouvez les combiner avec de ne jamais avoir à redimensionner en faisant que la JavaDoc dit: prenez votre capacité nécessaire, diviser par un facteur de charge optimale (par exemple, 0.75) et l'utiliser comme la capacité initiale, que le facteur de charge. Ajouter 1 assurez-vous que l'arrondissement n'a pas obtenir de vous.