Tengo entendido que dos objetos desiguales pueden tener el mismo código hash. ¿Cómo se manejaría esto al agregar o recuperar desde un Java de HashMap?¿Qué sucede si dos objetos diferentes tienen el mismo código hash?
Se agregarán al mismo cubo y se usará equals() para distinguirlos. Cada segmento puede contener una lista de objetos con el mismo código hash.
En teoría, puede devolver el mismo número entero que un código hash para cualquier objeto de una clase determinada, pero eso significa que perderá todos los beneficios de rendimiento del mapa hash y, de hecho, almacenará objetos en una lista.
¿No se aplica un hash suplementario por defecto para un Hashmap para evitar que esto suceda y presente cierta distribución? – Ajay
Punto adicional sobre el rendimiento, en java8, cuando tenemos demasiadas claves desiguales que proporcionan el mismo código hash (índice), el número de elementos en un depósito aumenta más allá de cierto umbral (TREEIFY_THRESHOLD = 8), el contenido de ese depósito cambia de uso una lista vinculada de objetos de entrada a un árbol equilibrado. Esto teóricamente mejora el rendimiento en el peor de los casos desde O (n) hasta O (log n). –
En HashMap, las claves junto con sus valores asociativos se almacenan en un nodo de lista vinculada en el depósito y las claves se comparan esencialmente en hashmap utilizando el método equals() y no mediante hashcode.
hm.put("a","aValue"); // Suppose hashcode created for key "a" is 209
hm.put("b","bValue"); // Here hashcode created for key "b" is 209 as well.
a.equals(b) vuelve true, bValue reemplazará aValue y se devolverá bValue.a.equals(b) Si vuelve false, otro nodo se creará en la lista del cubo, por lo que cuando se llama a get("b") obtendrá bValue desde a.equals(b) es false.¿Cómo puedo recuperar el valor de a si el hashcode es el mismo? Me dará bValue, pero quiero un valor. Es eso posible ? – Sanket
En ese caso, podría usar IdentityHashMap, donde diferentes objetos con el mismo hash se consideran diferentes en función de sus identidades.
Cuando dos objetos desiguales tienen el mismo valor hash, esto provoca una colisión en la tabla hash, porque ambos objetos quieren estar en la misma ranura (a veces llamado cubo). El algoritmo hash debe resolver tales colisiones. Volviendo a los recuerdos borrosos de mi curso de algoritmos universitarios, recuerdo tres formas básicas de hacerlo:
Creo que las clases de hash de Java utilizan el tercer método, pero podrían usar un enfoque de combinación. Sin embargo, la clave del buen hashing es asegurarse de que la tabla hash tenga una capacidad lo suficientemente grande y de escribir buenas funciones hash. Una tabla hash que solo tiene tantos cubos como los objetos que contiene probablemente tenga conflictos. Por lo general, desea que la tabla hash sea aproximadamente dos veces más grande que la cantidad de objetos que almacena. El HashMap de Java crecerá según sea necesario, pero puede darle una capacidad de inicio y un factor de carga si lo desea.
La función hash depende del programador. Podrías devolver 0 para todos los objetos, pero eso significará que el hash (tanto de almacenamiento como de recuperación) se convertirá en O (n) en lugar de O (1) ... o en términos simples, será dog slow.
Referencia: http://www.coderanch.com/t/540275/java/java/objects-hashcode-HashMap-retrieve-objects
HashMap está trabajando en el concepto de hash y la indexación. Internamente, HashMap almacena valores en la matriz de nodos. Cada nodo se comporta como LinkedList.
Cada nodo de lista enlazada tienen 4 valores:
int hashK keyV valueNode<K, V> nextHashMap interna:
Al insertar el valor en HashMap, se genera el primer hashcode de la clave y, basado en algún algoritmo, calculará el índice.
Por lo tanto, nuestro valor se almacenará en un índice específico con código hash, clave, valor y dirección del siguiente elemento.
Al recuperar el valor de HashMap, primero se generará el código hash y luego se indexará (de la misma manera que en el momento de la inserción). Al obtener el valor del índice, primero se buscará el código hash, si hashcode coincidirá, solo se buscará la clave del nodo mediante el método equals. Si la clave coincidirá, solo devolverá el valor o comprobará el siguiente nodo con el mismo código hash.
BTW: Puede crear muchos valores Long con el mismo código hash fácilmente para probar esto. 'new Long (n * 0x100000001L)' todos tienen un hashCode de 0 para 'n> = 0' –