java - Explicación sobre el algoritmo hash HashMap en este ejemplo

collision hashcode

Question

Estaba tratando de resolver esta pregunta:

Dado un conjunto de enteros con solo 3 números únicos, imprima los números en orden ascendente (con sus respectivas frecuencias) en el tiempo O (n).

Quería resolverlo sin usar el algoritmo de counting sort , así que lo que pensé es que podría hacer un for loop e insertar los números en un HashMap y luego recorrer el conjunto de entrada HashMap entrySet e imprimir la información requerida.

Aquí está la función:

public static void printOut(int[] arr){
        Map<Integer,Integer> hm=new HashMap<Integer,Integer>();
        for(int num : arr){
            if(hm.containsKey(num)){
                hm.put(num,hm.get(num)+1);
            }else{hm.put(num,1);}
        }
        for(Map.Entry<Integer,Integer> entry : hm.entrySet()){
            System.out.println("Key= "+entry.getKey()+" Value= "+entry.getValue());
        }
}

que hizo el truco cuando mi matriz fue: [3, 3, 2, 1, 3, 2, 1]

Sin embargo, la matriz anterior no debería provocar ninguna colisión, así que intenté usar una matriz que debería provocar colisiones, una de las matrices con las que probé mi función fue: [6,6,9,9,6,3,9] todavía mi función todavía imprimía las Keys en orden ascendente, lo que me confundió, porque pensé que cuando la Key del HashMap es un Entero, el código hash debería ser hashIndex = key % noOfBuckets así que cuando tengo los números 6, 9 and 3 como mi HashMap keys Pensé que habría colisiones y mi función debería imprimirse (según la matriz utilizada anteriormente):

Key= 6 Value= 3
Key= 9 Value= 3
Key= 3 Value= 1 

Pero en cambio se imprimió:

Key= 3 Value= 1
Key= 6 Value= 3
Key= 9 Value= 3

¿Podría alguien explicarme por qué obtuve la solución correcta a la pregunta que estaba tratando de resolver en lugar de la respuesta que esperaba?

Gracias.

Answer 1

¿Podría alguien explicarme por qué obtuve la solución correcta a la pregunta que estaba tratando de resolver en lugar de la respuesta que esperaba?

Es una coincidencia

ACTUALIZAR

Como ya mencionaron otros, un HashMap no garantiza ningún orden mientras itera su contenido, a diferencia de TreeMap que está ordenado o LinkHashMap que conserva el orden de entrada. Entonces sí, si sus elementos están ordenados, es solo una coincidencia.

Answer 2

1. El término "colisión" en el mapa hash / tabla hash es una situación en la que dos claves diferentes tienen el mismo código hash. La implementación de Java de HashMap usa List / RB-tree para resolver colisiones, pero cuando tiene literalmente 3 teclas enteras, este definitivamente no es su caso.
2. HashMap no garantiza el orden de inserción (o cualquier otro) de los elementos. Existen otras estructuras diferentes como LinkedHashMap o TreeMap que pueden garantizar cierto orden. Pero el uso de estas estructuras para su caso supone una pequeña sobrecarga, ya que puede ordenar su colección de 3 elementos en el tiempo constante. Incluso puede usar una matriz de Map.Entry en lugar de HashMap para su tarea.

Answer 3

Como ya se mencionó en la respuesta anterior de @Serge Harnyk

HashMap no garantiza el orden de inserción (o cualquier otro) de los elementos.

Ejecuté el código anterior que había compartido en la pregunta con la matriz [66,66,69,69,66,63,63,69] y el resultado fue

Key= 66 Value= 3
Key= 69 Value= 3
Key= 63 Value= 2

Aquí, puede ver que la salida no está ordenada. Otra matriz para la que entrySet () no devolvió los elementos en orden ordenado fue [10,5,5,10,10,5,10000000]

Key= 5 Value= 3
Key= 10000000 Value= 1
Key= 10 Value= 3

Por lo tanto, como la documentación de HashMap especifica el orden de los elementos devueltos por entrySet () o keySet () de HashMap, no se garantiza que estén en orden de inserción / clasificación.

El índice de hash contra el que se va a codificar una clave se decide en función del código hash de esa clave particular generada por la función hashCode () implementada en HashMap. Puede encontrar el código hash de una clave utilizando la función .hashCode ()

for(Map.Entry<Integer,Integer> entry : hm.entrySet()) {
    System.out.println("key= "+entry.getKey()+" has Hash Code= "+entry.getKey().hashCode()); 
}

La matriz [66,66,69,69,66,63,63,69] tenía la salida

key= 66 has Hash Code= 66
key= 69 has Hash Code= 69
key= 63 has Hash Code= 63

La matriz [10,5,5,10,10,5,10000000] tenía la salida

key= 5 has Hash Code= 5
key= 10000000 has Hash Code= 10000000
key= 10 has Hash Code= 10

A partir de estos, puede ver que para las claves Integer, el código hash no es hashIndex = key % noOfBuckets . Además, puede definir su propia implementación del método hashCode () y usarlo contra HashMap. Puede encontrar una explicación detallada implementando su función hashCode () personalizada aquí.

referir. https://www.geeksforgeeks.org/internal-working-of-hashmap-java/

Answer 4

Esto es mera coincidencia y el pedido de EntrySet y KeySet no está garantizado. De hecho, el hashmap en sí mismo no garantiza el orden de inserción y este orden también puede cambiar durante la repetición.

Ahora está intentando insertar int primitivo en hashmap como clave, lo que internamente hace autoboxing y el objeto Integer se insertará como clave.

La función de código hash entero es

public static int hashCode(int value) {
    return value;
} 

Significa que solo devuelve directamente el valor, en su caso 6,9 y 3

Entonces este hashcode es usado internamente por el hashmap para computar para obtener la posición del índice

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Como puede ver, el operador bit a bit con los valores dados devolverá 0 y exponencial en esos valores conducirá a la misma posición de índice de 3 que conduce a la colisión. Entonces, hashmap lo almacenará usando LinkedList (anterior java8) y en árbol (java8 y su versión posterior).

Al iterar a través de keySet o entrySet, el pedido no estará garantizado y, por lo tanto, el pedido que está recibiendo es mera coincidencia.

Answer 5

Extracto de las notas de implementación de HashMap :

Los contenedores de árbol (es decir, los contenedores cuyos elementos son todos TreeNodes) son
ordenado principalmente por hashCode, pero en el caso de empates, si dos
los elementos son de los mismos "implementos de clase C comparables",
escriba entonces su método compareTo se utiliza para ordenar.

El último es el caso de la clase Integer: implements Comparable<Integer> .

El código hash de un entero siempre es su valor entero. Y debido a que solo ocurre una colisión, cuando dos entradas diferentes obtienen el mismo código hash, no habrá colisiones para números enteros.
El orden de los nodos en la tabla depende del código hash. ¿Podría ser que las teclas de entero se clasifiquen?

Answer 6

No estoy seguro de qué quiere decir exactamente con "colisiones", pero como ya se señaló si lee la documentación de HashMap ( https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html ) no hay declaración sobre el pedido:

"Esta clase no garantiza el orden del mapa; en particular, no garantiza que el orden se mantendrá constante en el tiempo".

Y más adelante "Para mejorar el impacto, cuando las claves son Comparables, esta clase puede usar el orden de comparación entre claves para ayudar a romper los lazos".

Por fin, utiliza números enteros como claves, que implementan la interfaz Comparable, lo que significa que la implementación de HashMap puede ordenar sus claves, lo que de hecho hace.

También podría usar una implementación de Hash donde el orden de las claves esté predefinido y, por lo tanto, predecible, como un SortedMap.