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 claves/valores, 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 maneras más eficientes de acceder a los valores es almacenarlos en una matriz. Por ejemplo, podríamos darnos cuenta de un diccionario que utiliza enteros para llaves y cadenas de valores, así:
String[] dictionary = new String[DICT_SIZE];
dictionary[15] = "Hello";
dictionary[121] = "world";
System.out.println(dictionary[15]); // prints "Hello"
Por desgracia, este enfoque no es muy general en absoluto: 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 manera 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 hace hashCode(). Así que ahora, podríamos tratar de poner en práctica un diccionario String> Cadena:
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 bueno, lo que si hay algún objeto que nos gustaría utilizar como una llave, pero su método hashCode devuelve un valor que es mayor que o igual a 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 ginormeous de memoria para nuestra matriz, incluso si sólo se van a almacenar algunos artículos. 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 números enteros arbitrarios al rango [0, DICT_SIZE[. Entonces podríamos simplemente aplicar h a lo que sea que devuelva el método hashCode() de un objeto clave y asegurarnos de mantenernos 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 denomina función hash. Ahora podemos adaptar nuestra aplicación de diccionario para evitar la ArrayIndexOutOfBoundsException:
// "a" -> "Hello"
dictionary[h("a".hashCode(), DICT_SIZE)] = "Hello"
// "b" -> "world"
dictionary[h("b".hashCode(), DICT_SIZE)] = "world"
Pero eso introduce otro problema: ¿y si h mapas de dos índices claves diferentes para el mismo valor? Por ejemplo:
int keyA = h("a".hashCode(), DICT_SIZE);
int keyB = h("b".hashCode(), DICT_SIZE);
pueden producir los mismos valores para keyA y keyB, y en ese caso se puede sobrescribir accidentalmente 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, usted puede decir, entonces solo tenemos que asegurarnos de implementar h de tal manera que esto nunca pueda suceder. Desafortunadamente, esto no es posible en general. Considere el siguiente código:
for (int i = 0; i <= DICT_SIZE; i++) {
dictionary[h(i, DICT_SIZE)] = "dummy";
}
tiendas de este bucle DICT_SIZE + 1 valores (siempre el mismo valor, en realidad, a saber, la cadena "de prueba") 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 ampliar 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. Así que en lugar de utilizar:
String[] dictionary = new String[DICT_SIZE];
escribimos:
List<String>[] dictionary = new List<String>[DICT_SIZE];
observación
(Side: tenga en cuenta que Java no permite la creación de matrices de tipos genéricos, por lo que la línea anterior no se compilará - - Pero se entiende la idea).
que 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 el caso de nuestros hashfunction h devuelve valores diferentes para todas nuestras llaves, esto se traducirá en listas con sólo un elemento cada una, y la recuperación de elementos es muy simple:
System.out.println(dictionary[h("a".hashCode(), DICT_SIZE)].get(0)); // "Hello"
Pero ya sabemos que, en general h se asignarán diferentes claves para el mismo entero 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. Luego la búsqueda se realizaría en dos pasos:
- Aplique la función de función para recuperar la lista correcta de la matriz.
- 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 adición y recuperación han vuelto tan complejos que no es indecente para tratar a nosotros mismos métodos distintos para estas operaciones:
List<Pair<String,String>>[] dictionary = List<Pair<String,String>>[DICT_SIZE];
public void put(String key, String value) {
int hashCode = key.hashCode();
int arrayIndex = h(hashCode, DICT_SIZE);
List<Pair<String,String>> listAtIndex = dictionary[arrayIndex];
if (listAtIndex == null) {
listAtIndex = new LinkedList<Pair<Integer,String>>();
dictionary[arrayIndex] = listAtIndex;
}
for (Pair<String,String> previouslyAdded : listAtIndex) {
if (previouslyAdded.getValue().equals(value)) {
return; // the value is already in the dictionary;
}
}
listAtIndex.add(new Pair<String,String>(key, value));
}
public String get(String key) {
int hashCode = key.hashCode();
int arrayIndex = h(hashCode, DICT_SIZE);
List<Pair<String,String>> listAtIndex = dictionary[arrayIndex];
if (listAtIndex != null) {
for (Pair<String,String> previouslyAdded : listAtIndex) {
if (previouslyAdded.getKey().equals(key)) {
return previouslyAdded.getValue(); // entry found!
}
}
}
// entry not found
return null;
}
Por lo tanto, para que esta forma de trabajo, que realmente se necesita 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 rápidos) y un método equals que necesitamos al pasar por la lista.
Ésta es la idea general de hash, y se le reconocerá el método put y get de java.util.Map. Por supuesto, la aplicación anterior es una simplificación excesiva, pero debe ilustrar la esencia de todo.
Naturalmente, este enfoque no se limita a cadenas, funciona para todo tipo de objetos, ya que los métodos hashCode() y equals son miembros de la clase de nivel superior java.lang.Object y todas las demás clases heredan de que uno.
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.
Porque, por ejemplo, el punto de HashSet en tener códigos hash únicos por elemento. Y esto suena inútil si un par de objetos puede tener el mismo código hash. – Eugene
No, el punto de un valor hash es asignar cada objeto a un número entero. Luego puede almacenarlo en una matriz debajo de ese valor (en realidad, primero aplica una función int-> int hash para asignarlo al rango de la matriz). Si hashCode() y la función hash son rápidas, obtienes acceso rápido al objeto cuando deseas recuperarlo nuevamente de la matriz, pero a menos que conozcas todos los objetos de antemano, siempre puede suceder que dos objetos se asocien a la misma valor. Eso se llama una colisión y, debido a las colisiones, no se basa únicamente en la función hash, sino que también utiliza el método "igual" para comparar. – Thomas
Gracias, fue muy claro. – Eugene