Java: iteración a través de HashMap, ¿qué es más eficiente?

Question

Dado el siguiente código, con dos formas alternativas de recorrerlo,
¿hay alguna diferencia de rendimiento entre estos dos métodos?

 Map<String, Integer> map = new HashMap<String, Integer>(); 
     //populate map 

     //alt. #1 
     for (String key : map.keySet()) 
     { 
      Integer value = map.get(key); 
      //use key and value 
     } 

     //alt. #2 
     for (Map.Entry<String, Integer> entry : map.entrySet()) 
     { 
      String key = entry.getKey(); 
      Integer value = entry.getValue(); 
      //use key and value 
     } 

me inclino a pensar que es alt. #2 los medios más eficientes de iteración a través de toda la map (pero podría estar equivocado)

Answer 1

Su segunda opción es definitivamente más eficiente ya que está haciendo una búsqueda solo una vez en comparación con n veces en la primera opción.

Pero, nada es mejor que intentarlo cuando puedas.Así que aquí va -

(No es perfecto, pero lo suficientemente bueno para verificar las hipótesis y en mi máquina de todos modos)

public static void main(String args[]) { 

    Map<String, Integer> map = new HashMap<String, Integer>(); 
    // populate map 

    int mapSize = 500000; 
    int strLength = 5; 
    for(int i=0;i<mapSize;i++) 
     map.put(RandomStringUtils.random(strLength), RandomUtils.nextInt()); 

    long start = System.currentTimeMillis(); 
    // alt. #1 
    for (String key : map.keySet()) { 
     Integer value = map.get(key); 
     // use key and value 
    } 
    System.out.println("Alt #1 took "+(System.currentTimeMillis()-start)+" ms"); 

    start = System.currentTimeMillis(); 
    // alt. #2 
    for (Map.Entry<String, Integer> entry : map.entrySet()) { 
     String key = entry.getKey(); 
     Integer value = entry.getValue(); 
     // use key and value 
    } 
    System.out.println("Alt #2 took "+(System.currentTimeMillis()-start)+" ms"); 
} 

RESULTADOS (Algunas de las más interesantes)

Con int mapSize = 5000; int strLength = 5;
Alt # 1 tomó 26 ms
Alt # 2 tomó 20 ms

Con int mapSize = 50000; int strLength = 5;
Alt # 1 tomó 32 ms
Alt # 2 tomó 20 ms

Con int mapSize = 50000; int strLength = 50;
Alt # 1 tomó 22 ms
Alt # 2 tuvo 21 ms

Con int mapSize = 50000; int strLength = 500;
Alt # 1 tomó 28 MS
Alt # 2 tardó 23 ms

Con int mapSize = 500000; int strLength = 5;
Alt # 1 tomó 92 ms
Alt # 2 tuvo 57 ms

... y así sucesivamente

Answer 2

El segundo fragmento será ligeramente más rápido, ya que no hace necesita volver a buscar las teclas.

Todos los iteradores nextEntry method, que devuelve Entry<K,V>.

Su primer fragmento descarta el valor de la entrada (en KeyIterator), luego lo busca de nuevo en el diccionario.

Su segundo fragmento utiliza la clave y el valor directamente (de EntryIterator)

(Tanto keySet() y entrySet() son llamadas baratas)

Answer 3

Este último es más eficiente que el anterior. Una herramienta como FindBugs marcará realmente la primera y le sugerirá que haga lo último.

Answer 4

bguiz,

creo (no sé) que la iteración de la entrySet (alternativa 2) es ligeramente más eficiente, simplemente porque no el hash cada tecla con el fin de obtener su valor ... Habiendo dicho eso, calcular el hash es una operación O (1) por entrada, y por lo tanto SÓLO estamos hablando O (n) sobre el total HashMap ... pero tenga en cuenta que todo esto se aplica al HashMap solamente ... otras implementaciones de Map puede tener características de rendimiento MUY diferentes.

Creo que lo "presionarás" para realmente AVISAR en la diferencia de rendimiento. Si está preocupado, ¿por qué no configurar un caso de prueba para sincronizar ambas técnicas de iteración?

Si no tiene un problema de rendimiento REAL, informado, entonces realmente se está preocupando por no mucho ... Unos pocos tics de reloj aquí y allá no afectarán la usabilidad general de su programa.

Creo que muchos, muchos otros aspectos del código son generalmente más importantes que el rendimiento absoluto. Por supuesto, algunos bloques son "críticos para el rendimiento", y esto se conoce ANTES incluso de que se haya escrito, se ha probado el rendimiento por sí solo ... pero estos casos son bastante raros. Como enfoque general, es mejor centrarse en escribir un código completo, correcto, flexible, comprobable, reutilizable, legible y mantenible ... el rendimiento PUEDE incorporarse más adelante, según sea necesario.

La versión 0 debe ser TAN SIMPLE COMO SEA POSIBLE, sin ninguna "optimización".

Answer 5

En general, la segunda sería un poco más rápido para un HashMap. Sólo realmente importa si usted tiene un montón de colisiones hash, ya que entonces la llamada get(key) se vuelve más lento que O(1) - se pone O(k) con k es el número de entradas en el mismo cubo (es decir, el número de claves con mismo código hash o una diferente código hash que aún se asigna al mismo cubo; esto depende de la capacidad, el tamaño y el factor de carga del mapa también).

La variante de iteración de entrada no tiene que hacer la búsqueda, por lo tanto, se vuelve un poco más rápida aquí.

Otra nota: si la capacidad de su mapa es mucho mayor que el tamaño real y utiliza iteraciones mucho, puede considerar el uso de LinkedHashMap en su lugar. Proporciona O(size) en su lugar O(size+capacity) complejidad para una iteración completa (así como una orden de iteración predecible). (Todavía debe medir si esto realmente da una mejora, ya que los factores pueden variar LinkedHashMap tiene una sobrecarga más grande para crear el mapa..)

Answer 6

Mapa:

Map<String, Integer> map = new HashMap<String, Integer>();

Al lado de las 2 opciones, hay es uno más.

1) conjunto de claves() - utilizarlo si es necesario utilizar única los teclas

for (String k : map.keySet()) { 
    ... 
} 

2) entrySet() - utilizarlo si necesita ambos: teclas & valores

for (Map.Entry<String, Integer> entry : map.entrySet()) { 
    String k = entry.getKey(); 
    Integer v = entry.getValue(); 
    ... 
} 

3) valores() - utilizarlo si necesita única los valores

for (Integer v : map.values()) { 
    ... 
}