example - metodos de hashmap java

Consideraciones de rendimiento para keySet() y entrySet() de Map

Question

Todas,

¿Puede alguien decirme cuáles son los problemas de rendimiento entre los 2? El sitio: CodeRanch proporciona una breve descripción general de las llamadas internas que se necesitarían al usar keySet () y get (). Pero sería genial si alguien puede proporcionar detalles exactos sobre el flujo cuando se usan los métodos keySet () y get (). Esto me ayudaría a entender mejor los problemas de rendimiento.

Answer 1

El caso más común en el que se usa entrySet es preferible a keySet cuando se itera a través de todos los pares clave / valor en un mapa.

Esto es más eficiente:

for (Map.Entry entry : map.entrySet()) {
    Object key = entry.getKey();
    Object value = entry.getValue();
}

que:

for (Object key : map.keySet()) {
    Object value = map.get(key);
}

Porque en el segundo caso, para cada clave en keySet se llama al método map.get() , que - en el caso de un HashMap - requiere que los hashCode() y equals() del objeto clave se evalúen en orden para encontrar el valor asociado *. En el primer caso, se elimina el trabajo adicional.

Editar: Esto es aún peor si considera un TreeMap, donde una llamada es O (log2 (n)), es decir, el comparador de voluntad puede necesitar ejecutar log2 (n) veces (n = tamaño del Mapa) antes de encontrar el valor asociado.

* Algunas implementaciones de Map tienen optimizaciones internas que verifican la identidad de los objetos antes de hashCode() y equals() .

Answer 2

En primer lugar, esto depende completamente del tipo de mapa que estés utilizando. Pero como el hilo de JavaRanch habla sobre HashMap, asumiré que esa es la implementación a la que se refiere. Y supongamos también que está hablando de la implementación API estándar de Sun / Oracle.

En segundo lugar, si le preocupa el rendimiento cuando itera a través de su mapa hash, le sugiero que eche un vistazo a LinkedHashMap . De los documentos:

La iteración sobre las vistas de colección de un LinkedHashMap requiere un tiempo proporcional al tamaño del mapa, independientemente de su capacidad. La iteración sobre un HashMap probablemente sea más costosa, requiriendo tiempo proporcional a su capacidad.

HashMap.entrySet ()

El código fuente para esta implementación está disponible. La implementación básicamente solo devuelve un nuevo HashMap.EntrySet . Una clase que se ve así:

private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    public Iterator<Map.Entry<K,V>> iterator() {
        return newEntryIterator(); // returns a HashIterator...
    }
    // ...
}

y se ve un HashIterator

private abstract class HashIterator<E> implements Iterator<E> {
    Entry<K,V> next;    // next entry to return
    int expectedModCount;   // For fast-fail
    int index;      // current slot
    Entry<K,V> current; // current entry

    HashIterator() {
        expectedModCount = modCount;
        if (size > 0) { // advance to first entry
            Entry[] t = table;
            while (index < t.length && (next = t[index++]) == null)
                ;
        }
    }

    final Entry<K,V> nextEntry() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        Entry<K,V> e = next;
        if (e == null)
            throw new NoSuchElementException();

        if ((next = e.next) == null) {
            Entry[] t = table;
            while (index < t.length && (next = t[index++]) == null)
                ;
        }
    current = e;
        return e;
    }

    // ...
}

Así que ahí lo tienes ... Ese es el código que dicta que sucederá cuando iteres a través de un entrySet. Recorre toda la matriz, que es tan larga como la capacidad de los mapas.

HashMap.keySet () y .get ()

Aquí primero necesita obtener el conjunto de claves. Esto lleva tiempo proporcional a la capacidad del mapa (a diferencia del tamaño de LinkedHashMap). Una vez hecho esto, llame a get() una vez para cada clave. Claro, en el caso promedio, con una buena implementación de hashCode, esto lleva tiempo constante. Sin embargo, inevitablemente requerirá muchas llamadas .hashCode y .equals , lo que obviamente tomará más tiempo que simplemente hacer una entry.value() a entry.value() .

Answer 3

Aquí está el enlace a un artículo que compara el rendimiento de entrySet() , keySet() y values() , y consejos sobre cuándo usar cada enfoque.

Aparentemente, el uso de keySet() es más rápido (además de ser más conveniente) que entrySet() siempre que no necesite Map.get() los valores.