¿Por qué hashCode () puede devolver el mismo valor para diferentes objetos en Java?

Una cita del libro que estoy leyendo Head First Java :

El punto es que los hashCode() hash pueden ser los mismos sin necesariamente garantizar que los objetos sean iguales, porque el “algoritmo hashing” usado en el método hashCode() podría devolver el mismo valor para múltiples objetos.

¿Por qué el método hashCode() devuelve el mismo valor para diferentes objetos? ¿Eso no causa problemas?

hash de un objeto significa ” encontrar un buen valor descriptivo (número) que puede ser reproducido por la misma instancia una y otra vez “. Debido a que los códigos hash de Object.hashCode() de Java son de tipo int , solo puede tener 2^32 valores diferentes. Es por eso que tendrá las llamadas “colisiones” según el algoritmo hash, cuando dos objetos distintos producen el mismo hashCode.

Normalmente, esto no produce ningún problema, porque hashCode() se usa principalmente junto con equals() . Por ejemplo, un HashMap llamará a hashCode() sobre sus claves, para saber si las claves ya pueden estar contenidas en HashMap. Si HashMap no encuentra el código hash, es obvio que la clave aún no está contenida en el HashMap. Pero si lo hace, tendrá que verificar dos veces todas las claves que tienen ese mismo código hash usando equals() .

Es decir

 A.hashCode() == B.hashCode() // does not necessarily mean A.equals(B) 

Pero

 A.equals(B) // means A.hashCode() == B.hashCode() 

Si equals() y hashCode() se implementan correctamente.

Para una descripción más precisa del contrato general de hashCode , vea el Javadoc .

Hay solo un poco más de 4 mil millones de hashcodes posibles (el rango de una int ), pero la cantidad de objetos que puede elegir crear es mucho mayor. Por lo tanto, algunos objetos deben compartir el mismo código hash, según el principio del casillero .

Por ejemplo, el número de posibles cadenas que contienen 10 letras de AZ es 26 ** 10 que es 141167095653376. Es imposible asignar todas estas cadenas un código hash único. Tampoco es importante: el código hash no necesita ser único. Simplemente no necesita tener demasiadas colisiones para datos reales.

La idea de una tabla hash es que desee poder realizar una estructura de datos llamada diccionario de una manera eficiente. Un diccionario es un almacén de clave / valor, es decir, desea poder almacenar ciertos objetos bajo una determinada clave y más tarde poder recuperarlos nuevamente utilizando la misma clave.

Una de las formas más eficientes de acceder a los valores es almacenarlos en una matriz. Por ejemplo, podríamos realizar un diccionario que usa números enteros para claves y cadenas para valores como ese:

 String[] dictionary = new String[DICT_SIZE]; dictionary[15] = "Hello"; dictionary[121] = "world"; System.out.println(dictionary[15]); // prints "Hello" 

Desafortunadamente, este enfoque no es para nada general: el índice de una matriz tiene que ser un valor entero, pero idealmente nos gustaría poder utilizar tipos arbitrarios de objetos para nuestras claves, no solo enteros.

Ahora, la forma de resolver este punto es tener una forma de asignar objetos arbitrarios a valores enteros que luego podríamos usar como claves para nuestra matriz. En Java, eso es lo que hashCode() hace. Entonces, podríamos intentar implementar un diccionario String-> String:

 String[] dictionary = new String[DICT_SIZE]; // "a" -> "Hello" dictionary["a".hashCode()] = "Hello"; // "b" -> "world" dictionary["b".hashCode()] = "world"; System.out.println(dictionary["b".hashCode()]); // prints world 

Pero, ¿y si hay algún objeto que nos gustaría utilizar como clave, pero su método hashCode un valor que es mayor o igual que DICT_SIZE ? Entonces obtendríamos una ArrayIndexOutOfBoundsException y eso sería indeseable. Entonces, hagámoslo tan grande como podamos, ¿verdad?

 public static final int DICT_SIZE = Integer.MAX_VALUE // Ooops! 

Pero eso significaría que tendríamos que asignar cantidades gigantescas de memoria para nuestra matriz, incluso si solo tenemos la intención de almacenar algunos elementos. Entonces esa no puede ser la mejor solución, y de hecho podemos hacerlo mejor. Supongamos que tenemos una función h que para cualquier DICT_SIZE asigna un número DICT_SIZE arbitrario dentro del rango [0, DICT_SIZE[ . Entonces podríamos simplemente aplicar h a lo que hashCode() método hashCode() de un objeto clave y estar seguros de que permaneceremos dentro de los límites de la matriz subyacente.

 public static int h(int value, int DICT_SIZE) { // returns an integer >= 0 and < DICT_SIZE for every value. } 

Esa función se llama función hash. Ahora podemos adaptar nuestra implementación del diccionario para evitar ArrayIndexOutOfBoundsException:

 // "a" -> "Hello" dictionary[h("a".hashCode(), DICT_SIZE)] = "Hello" // "b" -> "world" dictionary[h("b".hashCode(), DICT_SIZE)] = "world" 

Pero eso introduce otro problema: ¿qué h si h asigna dos índices clave diferentes al mismo valor? Por ejemplo:

 int keyA = h("a".hashCode(), DICT_SIZE); int keyB = h("b".hashCode(), DICT_SIZE); 

puede dar los mismos valores para keyA y keyB , y en ese caso accidentalmente sobrescribiríamos un valor en nuestra matriz:

 // "a" -> "Hello" dictionary[keyA] = "Hello"; // "b" -> "world" dictionary[keyB] = "world"; // DAMN! This overwrites "Hello"!! System.out.println(dictionary[keyA]); // prints "world" 

Bueno, puedes decir, entonces solo tenemos que asegurarnos de implementar h de tal manera que esto nunca pueda suceder. Desafortunadamente, esto no es posible en general. Considera el siguiente código:

 for (int i = 0; i <= DICT_SIZE; i++) { dictionary[h(i, DICT_SIZE)] = "dummy"; } 

Este bucle almacena DICT_SIZE + 1 valores (siempre el mismo valor, en realidad, es decir, el "dummy" String) en el diccionario. Mhh, pero la matriz solo puede almacenar DICT_SIZE entradas diferentes! Eso significa que cuando usemos h , sobrescribiríamos (al menos) una entrada. O, en otras palabras, h asignará dos claves diferentes al mismo valor. Estas "colisiones" no se pueden evitar: si las n palomas intentan entrar en n-1 agujeros de paloma, al menos dos de ellas deben entrar en el mismo hoyo.

Pero lo que podemos hacer es extender nuestra implementación para que la matriz pueda almacenar múltiples valores bajo el mismo índice. Esto puede hacerse fácilmente mediante el uso de listas. Entonces, en lugar de usar:

 String[] dictionary = new String[DICT_SIZE]; 

nosotros escribimos:

 List[] dictionary = new List[DICT_SIZE]; 

(Comentario al margen: tenga en cuenta que Java no permite la creación de matrices de tipos generics, por lo que la línea anterior no se comstackría, pero se entiende la idea).

Eso cambiará el acceso al diccionario de la siguiente manera:

 // "a" -> "Hello" dictionary[h("a".hashCode(), DICT_SIZE)].add("Hello"); // "b" -> "world" dictionary[h("b".hashCode(), DICT_SIZE)].add("world"); 

En caso de que nuestra función h devuelva diferentes valores para todas nuestras claves, esto dará como resultado listas con solo un elemento cada una, y recuperar elementos es realmente simple:

 System.out.println(dictionary[h("a".hashCode(), DICT_SIZE)].get(0)); // "Hello" 

Pero ya sabemos que, en general, h correlacionará diferentes claves con el mismo entero algunas veces. En estos casos, las listas contendrán más de un valor. Para la recuperación, tenemos que revisar toda la lista para encontrar el valor "correcto", pero ¿cómo lo reconoceríamos?

Bueno, en lugar de almacenar el valor solo, siempre podríamos almacenar el par completo (clave, valor) en las listas. Entonces la búsqueda se realizaría en dos pasos:

  1. Aplica la función de hash para recuperar la lista correcta de la matriz.
  2. Itere a través de todos los pares almacenados en la lista recuperada: si se encuentra el par con la clave deseada, devuelva el valor del par.

Ahora, agregar y recuperar se han vuelto tan complejos que no es indecente tratar nuestros métodos por separado para estas operaciones:

 List>[] dictionary = List>[DICT_SIZE]; public void put(String key, String value) { int hashCode = key.hashCode(); int arrayIndex = h(hashCode, DICT_SIZE); List> listAtIndex = dictionary[arrayIndex]; if (listAtIndex == null) { listAtIndex = new LinkedList>(); dictionary[arrayIndex] = listAtIndex; } for (Pair previouslyAdded : listAtIndex) { if (previouslyAdded.getValue().equals(value)) { return; // the value is already in the dictionary; } } listAtIndex.add(new Pair(key, value)); } public String get(String key) { int hashCode = key.hashCode(); int arrayIndex = h(hashCode, DICT_SIZE); List> listAtIndex = dictionary[arrayIndex]; if (listAtIndex != null) { for (Pair previouslyAdded : listAtIndex) { if (previouslyAdded.getKey().equals(key)) { return previouslyAdded.getValue(); // entry found! } } } // entry not found return null; } 

Entonces, para que este enfoque funcione, realmente necesitamos dos operaciones de comparación: el método hashCode para encontrar la lista en la matriz (esto funciona rápido si hashCode() y h son ambas rápidas) y un método equals que necesitamos cuando vamos a través de la lista.

Esta es la idea general de hashing, y reconocerá el método put y get de java.util.Map. Por supuesto, la implementación anterior es una simplificación excesiva, pero debería ilustrar la esencia de todo.

Naturalmente, este enfoque no está limitado a cadenas, funciona para todo tipo de objetos, ya que los métodos hashCode() e equals son miembros de la clase de nivel superior java.lang.Object y todas las otras clases heredan de esa.

Como puede ver, realmente no importa si dos objetos distintos devuelven el mismo valor en su método hashCode() : ¡el enfoque anterior siempre funcionará! Pero aún así es deseable que devuelvan valores diferentes para reducir las posibilidades de colisiones hash producidas por h . Hemos visto que estos no se pueden evitar al 100% en general, pero cuanto menos colisiones tengamos, más eficiente se volverá nuestra tabla hash. En el peor de los casos, todas las claves se asignan al mismo índice de matriz: en ese caso, todos los pares se almacenan en una sola lista y encontrar un valor se convertirá en una operación con costos lineales en el tamaño de la tabla hash.

El valor hashCode () se puede usar para buscar rápidamente un objeto utilizando el código hash como una dirección en un cubo de la tabla hash donde está almacenado.

Si varios objetos devuelven el mismo valor de hashCode (), significa que se almacenarán en el mismo contenedor. Si se almacenan muchos objetos en el mismo cubo, significa que, en promedio, se requieren más operaciones de comparación para buscar un objeto determinado.

En su lugar, use equals () para comparar dos objetos para ver si son semánticamente iguales.

Según tengo entendido, el trabajo del método de código hash es crear divisiones para mezclar los elementos, para que la recuperación sea más rápida. Si cada objeto devolverá el mismo valor, no hay ningún uso de hacer hash.

Tengo que pensar que es un algoritmo de hash bastante ineficiente para que 2 objetos tengan el mismo código hash.