java - tabla - ¿Qué sucede si dos objetos diferentes tienen el mismo código hash?

implementar hash en java

Question

Tengo entendido que dos objetos desiguales pueden tener el mismo código hash. ¿Cómo se manejaría esto al agregar o recuperar un java de HashMap?

Answer 1

Cuando dos objetos desiguales tienen el mismo valor de hash, esto causa una colisión en la tabla de hash, porque ambos objetos quieren estar en la misma ranura (a veces llamado un cubo). El algoritmo hash debe resolver tales colisiones. Volviendo a los recuerdos de mi curso de algoritmos universitarios, recuerdo tres formas básicas de hacer esto:

1. Busque la siguiente ranura vacía en la tabla hash y coloque el objeto allí. Ventajas: fáciles de implementar, desventajas: pueden llevar a la agrupación de objetos y degradar el rendimiento, se puede exceder la capacidad
2. Tenga una función de hash secundaria para usar cuando haya un conflicto: Pros: generalmente rápido, contras: debe escribir una segunda función de hash y es posible que aún se produzcan colisiones, y se puede exceder la capacidad
3. Haga una lista de objetos vinculados desde la ranura conflictiva de la tabla hash. Pros / contras: generalmente rápidos para la función de hash decente y factores de carga, pero pueden degradarse a búsqueda lineal en el peor de los casos

Creo que las clases de hash de Java usan el tercer método, pero podrían usar un enfoque de combinación. Sin embargo, la clave para un buen hash es asegurarse de que la tabla de hash tenga una capacidad suficiente y escribir buenas funciones de hash. Una tabla hash que solo tiene tantos depósitos como objetos que contiene probablemente tendrá conflictos. Por lo general, desea que la tabla hash sea aproximadamente el doble de 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. Puede devolver 0 para todos los objetos, pero eso significará que el hash (tanto el almacenamiento como la recuperación) se convertirá en O (n) en lugar de O (1) ... o en términos legos, será lento.

Referencia: http://www.coderanch.com/t/540275/java/java/objects-hashcode-HashMap-retrieve-objects

Answer 2

En HashMap, las claves junto con sus valores asociativos se almacenan en un nodo de lista enlazada en el depósito y las claves se comparan esencialmente en el hashmap utilizando el método equals () no por 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.

• Si a.equals(b) devuelve true , bValue reemplazará aValue y bValue será devuelto.
• Si a.equals(b) devuelve false , se creará otro nodo en la lista de depósitos, de modo que cuando llame a get("b") obtendrá bValue ya que a.equals(b) es false .

Answer 3

En ese caso, podría usar IdentityHashMap, donde diferentes objetos con el mismo hash se consideran diferentes según sus identidades.

Answer 4

HashMap está trabajando en el concepto de hash e indexación. Internamente, HashMap almacena los valores en Array of Nodes. Cada nodo se comporta como LinkedList.

Cada nodo de lista enlazada tiene 4 valores:

1. int hash
2. K key
3. V value
4. Node<K, V> next

HashMap Estructura interna:

Mientras se inserta el valor en HashMap, se genera el primer código hash de la clave y, según un algoritmo, calculará el índice.

Por lo tanto, nuestro valor se almacenará en un índice específico con código de clave, clave, valor y dirección del siguiente elemento.

Mientras se recupera el valor de HashMap, primero se generará el código hash y luego se indexará (de la misma forma que en el momento de la inserción). Al obtener el valor del índice, primero verificará el código de hash, si el código de hash coincidirá, solo verificará la clave del nodo utilizando el método equals. Si la clave coincidirá, solo devolverá el valor o, de lo contrario, buscará el siguiente nodo con el mismo código hash.

Answer 5

Solo se agregarán al mismo grupo y se utilizará equals() para distinguirlos. Cada grupo puede contener una lista de objetos con el mismo código hash.

En teoría, puede devolver el mismo número entero como código hash para cualquier objeto de una clase determinada, pero eso significaría que pierde todos los beneficios de rendimiento del mapa hash y, en efecto, almacenará los objetos en una lista.