how - colisión de HashMap de java

how to use hashmap java

Question

Estaba leyendo sobre cómo funciona hashmap. Estaba leyendo "¿Qué pasará si dos objetos diferentes tienen el mismo código hash" ?

De acuerdo con esto, si dos objetos tienen el mismo hashcode, ambos se almacenarán en LinkedList pero por lo que sé si hay dos hashcode, el anterior será sobrescrito con uno nuevo (corríjanme si me equivoco).

¿Puede alguien aclarar por qué hashmap usa el objeto como clave internamente y qué sucederá si dos objetos tienen el mismo código hash y cómo ambos objetos se get() con get() ?

Answer 1

En el hashmap de Java, podrían usar varias formas de hacerlo. De mi antigua clase CS 201 Data Structures en las edades oscuras:

1) Cada segmento en el mapa hash puede convertirse en el encabezado de una lista vinculada que contiene todas las entradas agregadas que tienen el mismo valor hash. Una colisión en la adición significa que agrega la nueva entrada al final de la lista vinculada. La búsqueda significa que tienes que verificar linealmente todas las que están en una lista vinculada una vez que hash en el cubo para ello.

2) Si ocurre una colisión y la tienda es conceptualmente una matriz, puede iterar comenzando en ese punto hasta que encuentre un lugar vacío y agregue la nueva entrada allí. Para la búsqueda, esto significa que si encuentra que el cubo hash está ocupado, entonces tiene que comparar linealmente desde ese punto hasta el siguiente punto vacío en el conjunto que respalda el mapa hash.

En ambos casos, el rendimiento se degrada si hay varias entradas con el mismo hash. En el caso general, esto significa que una función hash (utilizada para generar el código hash) devuelve una pequeña cantidad de valores posibles, el rendimiento se degradará a medida que el mapa se llene. El Java HashMap ha aprovechado 50 años de investigación en tales cosas para ajustarse bien al caso general de datos generales que entran en un mapa hash.

Tenga en cuenta que @dystroy hizo un comentario sobre la regla de que no puede tener dos entradas en el mapa con esa coincidencia de acuerdo con el método equals ().

Answer 2

No, el primero no se reemplaza solo porque el segundo tiene el mismo hashCode .

Solo se anulará si también es igual (como lo dicen los equals ). De lo contrario, ambos valores se mantendrán en la lista vinculada.

Cuando se busca una clave, todos los nodos con el mismo hashCode se compararán con la clave proporcionada hasta que uno sea igual, entonces se devolverá su valor (usando el método equals ).

Si ninguna clave en el mapa es igual, obtendrá null .

El único problema que tiene si muchos objetos tienen el mismo hashCode (o más precisamente el mismo módulo hashCode del tamaño de la Entry[] table interna) es que la lista enlazada siempre será leída, que es más lenta (y anula el propósito de cualquier tabla de picadillo). Es por eso que es importante cuando se diseña un método de hashcode para garantizar que los enteros generados estén bien distribuidos.

Answer 3

Permítanme explicar el funcionamiento de hashmap.

Trabajo del método put:

HashMap funciona según el principio de hashing, tenemos put() y get() método para almacenar y recuperar objetos de HashMap. Cuando pasamos un método de ambas claves y de valor a put() para almacenar en HashMap, utiliza el método key hashcode() para calcular hashcode y aplicando hash en ese hashcode identifica la ubicación del depósito para almacenar el objeto de valor. Al recuperarlo, utiliza el método de igualar objeto clave para encontrar el par de valor de clave correcto y el objeto de valor de retorno asociado con esa clave. HashMap utiliza la lista vinculada en caso de colisión y el objeto se almacenará en el siguiente nodo de la lista vinculada. Además, HashMap almacena ambos clave + valor tuple en cada nodo de la lista vinculada

Trabajo del método get:

Cuando pasamos el método Key y Value al método put() en Java HashMap, la implementación HashMap llama al método hashCode en el objeto Key y aplica el hashcode devuelto en su propia función hash para encontrar una ubicación de depósito para almacenar el objeto Entry, punto importante para mencionar es que HashMap en Java almacena tanto la clave como el objeto de valor como Map.Entry in bucket. Si se encuentra más de un objeto Entry en el contenedor, se llamará al método ke.equals de cada nodo en el mismo contenedor.

Answer 4

Suponiendo que sigue las reglas para definir hashCode y equals , el escenario que describió no dará como resultado la pérdida de datos. Como máximo, el rendimiento se degradará con el tiempo.