Rendimiento de la declaración HashMap vs Switch

Un HashMap esencialmente tiene un rendimiento O (1), mientras que un estado de cambio puede tener O (1) u O (registro (n)) dependiendo de si el compilador usa un interruptor de tabla o un interruptor de búsqueda.

Comprensiblemente, si una declaración de cambio se escribe como tal,

switch (int) {
    case 1:
    case 2:
    case 3:
    case 4:
    default:
}

entonces usaría un interruptor de mesa y claramente tendría una ventaja de rendimiento sobre un HashMap estándar. Pero, ¿qué pasa si la declaración de cambio es escasa? Estos serían dos ejemplos que estaría comparando:

HashMap<Integer, String> example = new HashMap<Integer, String>() {{
        put(1, "a");
        put(10, "b");
        put(100, "c");
        put(1000, "d");
}};

.

switch (int) {
    case 1:
        return "a";
    case 10:
        return "b";
    case 100:
        return "c";
    case 1000:
        return "d";
    default:
        return null;
}

¿Qué proporcionaría más rendimiento, un conmutador de búsqueda o HashMap? ¿La sobrecarga de HashMap le da al cambio de búsqueda una ventaja temprana, pero eventualmente disminuye a medida que aumenta el número de casos/entradas?

Editar: Probé algunos puntos de referencia usando JMH, aquí están mis resultados y el código usado. https://gist.github.com/mooman219/bebbdc047889c7cfe612
Como mencionaron, la instrucción lookupswitch superó a HashTable. Aunque todavía me pregunto por qué.

La respuesta aceptada es incorrecta aquí.

http://java-performance.info/string-switch-implementation/

Los cambios siempre serán tan rápidos como si no más rápidos que los mapas hash. Las declaraciones de cambio se transforman en tablas de búsqueda directa. En el caso de valores enteros (ints, enums, shorts, longs) es una búsqueda directa/jmp a la declaración. No hay hash adicional que deba suceder. En el caso de una cadena, calcula previamente el hash de la cadena para las declaraciones del caso y utiliza el código hash de la cadena de entrada para determinar dónde saltar. En caso de colisión, hace una cadena if/else. Ahora podrías pensar “Esto es lo mismo que HashMap, ¿verdad?” Pero eso no es cierto. El código hash para la búsqueda se calcula en tiempo de compilación y no se reduce según la cantidad de elementos (menor probabilidad de colisión).

Los interruptores tienen búsqueda O(1), no O(n). (Ok, en verdad, para una pequeña cantidad de elementos, los interruptores se convierten en declaraciones if/else. Esto proporciona una mejor localidad de código y evita búsquedas de memoria adicionales. Sin embargo, para muchos elementos, los interruptores se cambian a la tabla de búsqueda que mencioné anteriormente).

Puede leer más sobre esto aquí. ¿Cómo funciona el interruptor de Java bajo el capó?

Eso depende:

1. Si hay algunos artículos | artículos fijos. Usando el interruptor si puedes (en el peor de los casos O(n))

2. Si hay muchos elementos O desea agregar elementos futuros sin modificar mucho el código —> Usar hash-map (el tiempo de acceso se considera un tiempo constante)

3. NO debe intentar mejorar el rendimiento del caso, porque la diferencia en el tiempo de ejecución es de nanosegundos. Solo concéntrese en la legibilidad/mantenibilidad de su código. ¿Merece la pena optimizar un caso sencillo para mejorar unos nanosegundos?

TL/DR

Basarlo en la legibilidad y mantenibilidad del código. Ambos tienen un costo de O(1) y casi no proporcionan diferencia (aunque los cambios generalmente serán un poco más rápidos).

En este caso particular, un mapa sería más rápido, ya que un interruptor devuelve una dirección y luego debe ir a esa dirección para identificar el valor de retorno. (Un ejemplo de caso raro). Si su interruptor solo está llamando funciones de todos modos, un Mapa también sería más rápido.

Para acelerar las cosas, me aseguraría de usar casos numéricos y evitaría usar cadenas a través de constantes o enumeradores (mecanografiado).

(editado) Confirmé por expectativa: ¿Cómo funciona el interruptor de Java debajo del capó? con interruptores

respuesta mas detallada

En las malas hierbas:

Una declaración de cambio generalmente será de mayor rendimiento. Crea una tabla de búsqueda y va a la referencia y comienza en ese punto. Sin embargo, hay excepciones.

Cuando utiliza un interruptor simple como return map.get(x) vs. switch(1=>’a’, 2=>’b’, etc.). Esto se debe a que el mapa puede devolver directamente el valor deseado donde el interruptor detendrá el mapa de las direcciones y continuará hasta que se alcance el descanso o el final.

En cualquier caso, deberían ser extremadamente similares en costo de ejecución.

Piense en la mantenibilidad y la legibilidad del código.

El uso de un mapa desacopla los datos, lo que puede obtener el beneficio de crear casos de “cambio” de forma dinámica. Más detallado a continuación.

Si hay varias funciones/procesos complejos que necesita manejar, puede ser más fácil leer/escribir si utiliza un mapa en su lugar. Especialmente si la declaración de cambio comienza a exceder las 20 o 30 opciones.

Ejemplo de caso de uso personal para mapas:

He estado utilizando el siguiente patrón para flux (Redux/useReducer) en aplicaciones React durante algún tiempo.

Creo un mapa central donde mapeo el disparador como clave, y el valor es una referencia funcional. Luego puedo cargar casos donde y cuando tenga sentido.

Inicialmente, usé esto para poder dividir los casos de uso para reducir el tamaño del archivo y agrupar los casos de función similar de una manera más organizada. Aunque luego lo evolucioné para cargarlo en dominios y configuré los eventos y datos en un gancho de dominio, como useUser, useFeedback, useProfile, etc…

Hacerlo me permitió crear el estado predeterminado, las funciones de inicialización, los eventos, etc. en una estructura de archivos lógicos, y también me permitió mantener el espacio bajo hasta que fuera necesario.

Una nota a tener en cuenta

El uso de un mapa no permite pasar, aunque la mayoría de la gente considera que este código huele de todos modos. Al mismo tiempo protege de caídas accidentales.

En su caso, ya que está utilizando un Integer clave para su HashMap y un llano’int‘ para tu switch declaración, la implementación con mejor rendimiento será la switch declaración a menos que el número de pasos a través de esta sección de código sea muy alto (decenas o cientos de miles).

Si tengo ese tipo de ejemplo, uso Guava ImmutableMaps (seguro que también puedes usar Java 9 Builder).

private static final Map<String, String> EXAMPLE = ImmutableMaps.<String, String>>builder()
    .put("a", "100")
    .put("b", "200")
    .build(); 

De esa forma son inmutables y se inician una sola vez.

A veces uso el patrón de estrategia de esa manera:

private static final Map<String, Command> EXAMPLE = ImmutableMaps.<String, String>>builder()
    .put("a", new SomethingCool())
    .put("b", new BCool())
    .build(); 

private static final Command DEFAULT= new DefCommand();

Usar:

EXAMPLE.getOrDefault("a", DEFAULT).execute(); //java 8

Sobre el rendimiento, simplemente elija la legibilidad. Me lo agradecerás más tarde (1 año después) :D.