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




collision hashcode (4)

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.


¿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.


  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.

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.


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?







hashcode