Introducción al hash
El hash está diseñado para resolver el problema de tener que buscar o almacenar de manera eficiente un artículo en una colección.
Por ejemplo, si tenemos una lista de 10,000 palabras en inglés y queremos verificar si una palabra determinada está en la lista, sería ineficaz comparar sucesivamente la palabra con los 10,000 elementos hasta que encontremos una coincidencia. Incluso si la lista de palabras está ordenada lexicográficamente, como en un diccionario, necesitará algo de tiempo para encontrar la palabra que está buscando.
El hash es una técnica para hacer las cosas más eficientes al reducir de manera efectiva la búsqueda desde el principio.
¿Qué es el hash?
Hashing significa usar alguna función o algoritmo para mapear datos de objeto a algún valor entero representativo.
Este llamado código hash (o simplemente hash) se puede utilizar como una forma de delimitar nuestra búsqueda al buscar el elemento en el mapa.
Generalmente, estos códigos hash se utilizan para generar un índice, en el que se almacena el valor.
Cómo funciona el hash
En las tablas hash, almacena datos en forma de pares de clave y valor. La clave, que se utiliza para identificar los datos, se proporciona como entrada a la función hash. El código hash, que es un número entero, se asigna al tamaño fijo que tenemos.
Las tablas hash deben admitir 3 funciones.
- insertar (clave, valor)
- obtener la clave)
- borrar (clave)
Simplemente como un ejemplo para ayudarnos a comprender el concepto, supongamos que queremos asignar una lista de claves de cadena a valores de cadena (por ejemplo, asignar una lista de países a sus ciudades capitales).
Entonces, digamos que queremos almacenar los datos en Table en el mapa.
Y supongamos que nuestra función hash es simplemente tomar la longitud de la cadena.
Para simplificar, tendremos dos matrices: una para nuestras claves y otra para los valores.
Entonces, para poner un elemento en la tabla hash, calculamos su código hash (en este caso, simplemente contamos el número de caracteres), luego colocamos la clave y el valor en las matrices en el índice correspondiente.
Por ejemplo, Cuba tiene un código hash (longitud) de 4. Así que almacenamos Cuba en la cuarta posición en la matriz de claves, y La Habana en el cuarto índice de la matriz de valores, etc. Y terminamos con lo siguiente:
Ahora, en este ejemplo específico, las cosas funcionan bastante bien. Nuestra matriz debe ser lo suficientemente grande para acomodar la cuerda más larga, pero en este caso son solo 11 ranuras.
Perdemos un poco de espacio porque, por ejemplo, no hay claves de 1 letra en nuestros datos, ni claves entre 8 y 10 letras.
Pero en este caso, el espacio desperdiciado tampoco es tan malo. Tomar la longitud de una cadena es agradable y rápido, al igual que el proceso de encontrar el valor asociado con una clave determinada (ciertamente más rápido que hacer hasta cinco comparaciones de cadenas).
Pero, ¿qué hacemos si nuestro conjunto de datos tiene una cadena que tiene más de 11 caracteres?
¿Qué pasa si tenemos otra palabra con 5 caracteres, "India", e intentamos asignarla a un índice usando nuestra función hash? Dado que el índice 5 ya está ocupado, tenemos que hacer una llamada sobre qué hacer con él. A esto se le llama colisión.
Si nuestro conjunto de datos tuviera una cadena con mil caracteres y creara una matriz de miles de índices para almacenar los datos, resultaría en un desperdicio de espacio. Si nuestras claves fueran palabras aleatorias del inglés, donde hay tantas palabras con la misma longitud, usar la longitud como función hash sería bastante inútil.
Manejo de colisiones
Se utilizan dos métodos básicos para manejar colisiones.
- Encadenamiento separado
- Direccionamiento abierto
Encadenamiento separado
El manejo de colisiones de hash mediante encadenamiento separado, utiliza una estructura de datos adicional, preferiblemente una lista enlazada para la asignación dinámica, en depósitos. En nuestro ejemplo, cuando agregamos India al conjunto de datos, se agrega a la lista vinculada almacenada en el índice 5, entonces nuestra tabla se vería así.
Para encontrar un artículo, primero vamos al cubo y luego comparamos las claves. Este es un método popular, y si se usa una lista de enlaces, el hash nunca se llena. El costo de get(k)es en promedio O(n)donde n es el número de claves en el depósito, el número total de claves es N.
El problema con el encadenamiento separado es que la estructura de datos puede crecer sin límites.
Direccionamiento abierto
El direccionamiento abierto no introduce ninguna estructura de datos nueva. Si ocurre una colisión, buscamos disponibilidad en el siguiente lugar generado por un algoritmo. El direccionamiento abierto se utiliza generalmente cuando el espacio de almacenamiento es restringido, es decir, procesadores integrados. El direccionamiento abierto no es necesariamente más rápido que el encadenamiento separado.
Métodos de direccionamiento abierto
- [Palpación lineal
- Palpado cuadrático
- Hash doble
Cómo usar hash en su código.
Pitón
# Few languages like Python, Ruby come with an in-built hashing support. # Declaration my_hash_table = {} my_hash_table = dict() # Insertion my_hash_table[key] = value # Look up value = my_hash_table.get(key) # returns None if the key is not present || Deferred in python 3, available in python 2 value = my_hash_table[key] # throws a ValueError exception if the key is not present # Deletion del my_hash_table[key] # throws a ValueError exception if the key is not present # Getting all keys and values stored in the dictionary keys = my_hash_table.keys() values = my_hash_table.values()
Ejecutar código
Java
// Java doesn't include hashing by default, you have to import it from java.util library // Importing hashmaps import java.util.HashMap; // Declaration HashMap myHashTable = new HashMap(); // declares an empty map. // Insertion myHashTable.put(key, value); // Deletion myHashtable.remove(key); // Look up myHashTable.get(key); // returns null if the key K is not present myHashTable.containsKey(key); // returns a boolean value, indicating the presence of a key // Number of key, value pairs in the hash table myHashTable.size();Ejecutar código
Más información sobre hash
- La guía sin código para hash y tablas hash
- Cómo implementar una tabla hash simple en JavaScript
- Explicación de las tablas hash