sono HashMaps con capacità predefinita veloce

Question

mi sono imbattuto in un algoritmo in rete http://www.coderanch.com/t/201836/Performance/java/Hashtable-vs-Hashmap e abbiamo deciso di testarlo

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)); 
    } 
} 

e ho ottenuto i seguenti risultati

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 

È questo JVM dipendente e arbitraria o fornisce realmente un accesso e un tempo di archiviazione più rapidi?

Answer 1

La definizione della dimensione prevista di qualsiasi classe del tipo di contenitore fornirà tempi di archiviazione più rapidi semplicemente perché la memoria non deve essere ridistribuita dinamicamente in fase di esecuzione come spesso. Di solito l'archiviazione di backup è una sorta di array e quando si va oltre la capacità disponibile, l'array deve essere copiato in un nuovo array più grande. Si tratta di un'operazione costosa che potrebbe dover verificarsi più volte se si memorizza un numero elevato di oggetti in un contenitore che ha iniziato a una capacità molto ridotta.

Le prestazioni di lettura dalla mappa non dovrebbero essere influenzate in alcun modo. È possibile dimostrarlo meglio impostando la parte tm.put separatamente dalla parte tm.get.

---

Modifica: Per illustrare ulteriormente questo punto, ho modificato il codice per tempo tm.put separatamente dal tm.get. Ecco i risultati sulla mia macchina:

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 

Si noti che la differenza tra Hashtable regolare e predimensionate per tm.put è un fattore ~ ​​2. Analogamente, con HashMap la differenza tra normale e pre-impostato è un fattore di ~ 7 per la memorizzazione. Tuttavia, guardando il lato di lettura, sia Hashtable e Hashmap hanno all'incirca le stesse tempistiche di tm.get in entrambi i casi (10 ms vs 9 ms per Hashtable, e 5 ms vs 4 ms per HashMap). Si noti inoltre che nel caso presunto, sia la messa che l'ottenimento richiedono all'incirca la stessa quantità di tempo totale.