son HashMaps con capacidad predefinida más rápido

Question

me encontré con un algoritmo en la red http://www.coderanch.com/t/201836/Performance/java/Hashtable-vs-Hashmap y decidimos probarlo

public class MapTest{ 
    static int sizeOfTrial = 100000; 
    static String[] keys = new String[sizeOfTrial]; 
    static String[] vals = new String[sizeOfTrial]; 

    public static void main(String[] args) { 
     //init sizeOfTrial key/value pairs 
     for (int i=0; i < sizeOfTrial; i++){ 
      String s1 = "key"+ i; 
      String s2 = "val"+ i; 
      keys[i] = s1; 
      vals[i] = s2; 
     } 
     test(new TreeMap(), "TreeMap"); 
     test(new Hashtable(), "Hashtable"); 
     test(new HashMap(), "HashMap"); 
     test(new Hashtable(200000), "Hashtable presized"); 
     test(new HashMap(200000), "HashMap presized"); 
    } 

    public static void test(Map tm, String name){ 
    long t1 = System.currentTimeMillis(); 
    for (int i=0; i < sizeOfTrial; i++){ 
     tm.put(keys[i],vals[i]); 
    } 
    for (int i=0; i < sizeOfTrial; i++){ 
     tm.get(keys[i]); 
    } 
    long t2 = System.currentTimeMillis(); 
    System.out.println("total time for " + name + ": " + (t2-t1)); 
    } 
} 

y me dieron los siguientes resultados

total time for TreeMap: 1744 
total time for Hashtable: 446 
total time for HashMap: 234 
total time for Hashtable presized: 209 
total time for HashMap presized: 196 

¿Es esta JVM dependiente y arbitraria ¿o realmente proporciona un acceso y un tiempo de almacenamiento más rápidos?

Answer 1

La predefinición del tamaño esperado de cualquier clase de contenedor proporcionará un tiempo de almacenamiento más rápido simplemente porque el almacenamiento no tiene que reasignarse dinámicamente en el tiempo de ejecución con tanta frecuencia. Por lo general, el almacenamiento de respaldo es una especie de matriz, y cuando se supera la capacidad disponible, la matriz debe copiarse en una matriz más grande. Esta es una operación costosa que puede tener que ocurrir varias veces si almacena una gran cantidad de objetos en un contenedor que comenzó con una capacidad muy pequeña.

La interpretación de la lectura del mapa no debe verse afectada de ninguna manera. Puede demostrar esto mejor sincronizando la parte tm.put por separado de la parte tm.get.

---

Editar: Para ilustrar más este punto, I modificado el código para tiempo tm.put por separado de tm.get. Estos son los resultados en mi máquina:

total time for TreeMap tm.put: 159 
total time for TreeMap tm.get: 74 
total time for Hashtable tm.put: 20 
total time for Hashtable tm.get: 10 
total time for HashMap tm.put: 42 
total time for HashMap tm.get: 5 
total time for Hashtable presized tm.put: 11 
total time for Hashtable presized tm.get: 9 
total time for HashMap presized tm.put: 6 
total time for HashMap presized tm.get: 4 

en cuenta que la diferencia entre Hashtable regular y clasificar por tamaño de tm.put es un factor de ~ 2. De manera similar, con HashMap, la diferencia entre regular y presized es un factor de ~ 7 para el almacenamiento. Sin embargo, mirando el lado de lectura, tanto HashtableHashmap y tienen más o menos los mismos horarios para tm.get en ambos casos (10 ms vs 9 ms para Hashtable y 5 ms vs 4 ms para HashMap). También tenga en cuenta que, en el caso preestablecido, tanto la puesta como la obtención toman más o menos la misma cantidad de tiempo total.