from - hashmap java example
Resolución de colisión en Java HashMap (7)
Java HashMap usa el método put para insertar el par K / V en HashMap . Digamos que he usado el método put y ahora HashMap<Integer, Integer> tiene una entrada con la key como 10 y el value como 17.
Si inserto 10,20 en este HashMap , simplemente reemplaza la entrada anterior con esta entrada debido a una colisión debido a la misma clave 10.
Si la tecla colisiona, HashMap reemplaza el antiguo par K / V con el nuevo par K / V.
Entonces, mi pregunta es cuándo usa HashMap técnica de resolución de colisión de encadenamiento.
¿Por qué no formó una lista de linkedlist con la clave como 10 y el valor como 17,20?
Cuando inserta el par (10, 17) y luego (10, 20) , técnicamente no hay colisión involucrada. Simplemente está reemplazando el valor anterior por el nuevo valor para una clave dada 10 (ya que en ambos casos, 10 es igual a 10 y también el código hash para 10 es siempre 10).
La colisión ocurre cuando hay varias teclas hash en el mismo cubo. En ese caso, debe asegurarse de que puede distinguir entre esas claves. La resolución de colisión de encadenamiento es una de esas técnicas que se utiliza para esto.
Como ejemplo, supongamos que dos cadenas "abra ka dabra" y "wave my wand" producen los códigos hash 100 y 200 respectivamente. Suponiendo que el tamaño total de la matriz es 10, ambos terminan en el mismo cubo ( 100 % 10 y 200 % 10 ). Encadenamiento asegura que cada vez que hagas map.get( "abra ka dabra" ); , terminas con el valor correcto asociado con la tecla. En el caso del mapa hash en Java, esto se hace usando el método equals .
En primer lugar, tiene el concepto de hashing un poco mal y fue corregido por el Sr. Sanjay.
Y sí, Java implementa una técnica de resolución de colisión. Cuando dos teclas obtienen hash a un mismo valor (ya que el conjunto interno utilizado es de tamaño finito y en algún punto el método hashcode () devolverá el mismo valor hash para dos claves diferentes) en este momento, se forma una lista vinculada en el cubo ubicación donde se ingresan todas las informaciones como un objeto Map.Entry que contiene un par clave-valor. El acceso a un objeto a través de una tecla requerirá, en el peor de los casos, O (n) si la entrada está presente en dicha lista. La comparación entre la clave que pasó con cada tecla en dicha lista se realizará mediante el método equals ().
Aunque, desde Java 8, las listas vinculadas se reemplazan por árboles (O (log n))
En un HashMap la clave es un objeto que contiene los hashCode() y hashCode() equals(Object) .
Cuando inserta una nueva entrada en el Mapa, verifica si hashCode ya es conocido. Luego, recorrerá todos los objetos con este .equals() y probará su igualdad con .equals() . Si se encuentra un objeto igual , el nuevo valor reemplaza al anterior. Si no, creará una nueva entrada en el mapa.
Usualmente, hablando de mapas, usas colisión cuando dos objetos tienen el mismo hashCode pero son diferentes. Están almacenados internamente en una lista.
Hay diferencia entre colisión y duplicación. Colisión significa que el hashcode y el cubo son los mismos, pero por duplicado, será el mismo código hash, el mismo cubo, pero aquí equivale al método que aparece en la imagen.
Colisión detectada y puede agregar elemento en la clave existente. pero en caso de duplicación, reemplazará el nuevo valor.
No está definido para hacerlo. Para lograr esta funcionalidad, necesita crear un mapa que asigne claves a listas de valores:
Map<Foo, List<Bar>> myMap;
O bien, podría usar el Multimap de google collections / guava libraries
No hay colisión en tu ejemplo. Utiliza la misma clave, por lo que el valor anterior se reemplaza por el nuevo. Ahora, si utilizó dos claves que se correlacionan con el mismo código hash, entonces tendría una colisión. ¡Pero incluso en ese caso, HashMap reemplazará tu valor! Si desea encadenar los valores en caso de colisión, debe hacerlo usted mismo, por ejemplo, utilizando una lista como valor.
Podría haber formado una lista vinculada, de hecho. Es solo que el contrato de Map requiere que reemplace la entrada:
V put(K key, V value)Asocia el valor especificado con la clave especificada en este mapa (operación opcional). Si el mapa contenía previamente una asignación para la clave, el valor anterior se reemplaza por el valor especificado. (Se dice que un mapa m contiene una asignación para una clave k si y solo si m.containsKey (k) devuelve verdadero).
http://docs.oracle.com/javase/6/docs/api/java/util/Map.html
Para un mapa para almacenar listas de valores, debe ser un Multimap . Aquí está Google: http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Multimap.html
Una colección similar a un Mapa, pero que puede asociar valores múltiples con una sola clave. Si llama put (K, V) dos veces, con la misma clave pero diferentes valores, el multimap contiene asignaciones de la clave para ambos valores.
Editar: resolución de colisión
Eso es un poco diferente. Una colisión ocurre cuando dos teclas diferentes tienen el mismo código hash, o dos teclas con diferentes códigos hash pasan a mapearse en el mismo cubo en la matriz subyacente.
Considere la fuente de HashMap (bits y piezas eliminados):
public V put(K key, V value) {
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
// i is the index where we want to insert the new element
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
// take the entry that''s already in that bucket
Entry<K,V> e = table[bucketIndex];
// and create a new one that points to the old one = linked list
table[bucketIndex] = new Entry<>(hash, key, value, e);
}
Para aquellos que sienten curiosidad por cómo la clase Entry en HashMap se comporta como una lista, resulta que HashMap define su propia clase de Entry estática que implementa Map.Entry . Puede verlo usted mismo viendo el código fuente: