¿Qué significa hashing? La tecnología cambia la vida futura

Hashing: la idea es usar la función hash que convierte un número de teléfono dado o cualquier otra tecla a un número más pequeño y usa el número pequeño como índice en una tabla llamada tabla hash.

Función hash: una función hash asigna un gran número o cadena a un entero pequeño que se puede usar como índice en la tabla hash. Una buena función Hash debería ser eficientemente computable y debería distribuir uniformemente las claves.

Manejo de colisiones: dado que una función hash nos da un número pequeño para una clave grande, existe la posibilidad de que dos claves den como resultado el mismo valor. La situación en la que una clave recién insertada se asigna a una ranura ya ocupada en la tabla hash se llama colisión y debe manejarse utilizando alguna técnica de manejo de colisión.

Las siguientes son las formas de manejar las colisiones:

Encadenamiento: la idea es hacer que cada celda de la tabla hash apunte a una lista vinculada de registros que tengan el mismo valor de función hash. El encadenamiento es simple, pero requiere memoria adicional fuera de la tabla.
Direccionamiento abierto: en el direccionamiento abierto, todos los elementos se almacenan en la propia tabla hash. Entonces, en cualquier punto, el tamaño de la tabla debe ser mayor o igual que el número total de claves. Logrado por el sondeo lineal, el sondeo cuadrático o el hash.

Encadenamiento separado: fácil de implementar y la tabla hash nunca se llena. Se usa principalmente cuando se desconoce cuántas y con qué frecuencia se pueden insertar o eliminar claves.

Evaluación del rendimiento del encadenamiento: el rendimiento del hashing se puede evaluar bajo el supuesto de que cada clave tiene la misma probabilidad de ser hash en cualquier ranura de la tabla (hashing uniforme).
m = Número de ranuras en la tabla hash
n = El número de claves a insertar en la tabla tiene
Factor de carga α = n / m
Tiempo esperado de búsqueda = O (1 + α)
Tiempo esperado para insertar / eliminar = O (1 + α)
La complejidad temporal de la inserción y eliminación de búsqueda es O (1) si α es O (1)
Desventaja: el rendimiento del encadenamiento de la memoria caché no es bueno, ya que las claves se almacenan mediante una lista vinculada. El desperdicio de espacio como enlaces se utilizan y algunas partes hash nunca se utilizan. Si la cadena se alarga, el tiempo de búsqueda puede convertirse en O (n) en el peor de los casos.

Direccionamiento abierto :

Insertar (k): siga sondeando hasta encontrar una ranura vacía. Una vez que se encuentre una ranura vacía, inserte k.

Búsqueda (k): siga sondeando hasta que la clave del espacio no sea igual a k o se alcance un espacio vacío.

Eliminar (k): la operación de eliminación es interesante. Si simplemente eliminamos una clave, entonces la búsqueda puede fallar. Por lo tanto, las ranuras de las teclas eliminadas se marcan especialmente como “eliminadas”. Insertar puede insertar un elemento en una ranura eliminada, pero la búsqueda no se detiene en una ranura eliminada.

Sondeo lineal : en el sondeo lineal, realizamos sondeos lineales para la siguiente ranura. Deje que hash (x) sea el índice de ranura calculado utilizando la función hash y S sea el tamaño de la tabla.

Si el hash de ranura (x)% S está lleno, entonces intentamos (hash (x) + 1)% S
Si (hash (x) + 1)% S también está lleno, entonces intentamos (hash (x) + 2)% S
Si (hash (x) + 2)% S también está lleno, entonces intentamos (hash (x) + 3)% S
………………………………………… ..

2. Agrupación: el principal problema con el sondeo lineal es la agrupación, muchos elementos consecutivos forman grupos y comienza a tomar tiempo para encontrar un espacio libre o buscar un elemento.

3. Sondeo cuadrático: buscamos la ranura número 2 en la iteración. El hash (x) sea el índice de ranura calculado utilizando la función hash.

Si el hash de ranura (x)% S está lleno, entonces intentamos (hash (x) + 1 * 1)% S
Si (hash (x) + 1 * 1)% S también está lleno, entonces intentamos (hash (x) + 2 * 2)% S
Si (hash (x) + 2 * 2)% S también está lleno, entonces intentamos (hash (x) + 3 * 3)% S
………………………………………… ..

4. Doble Hash : utilizamos otra función de hash hash2 (x) y buscamos la ranura i * hash2 (x) en la i-ésima rotación.

deje que hash (x) sea el índice de ranura calculado usando la función hash.
Si el hash de ranura (x)% S está lleno, entonces intentamos (hash (x) + 1 * hash2 (x))% S
Si (hash (x) + 1 * hash2 (x))% S también está lleno, entonces intentamos (hash (x) + 2 * hash2 (x))% S
Si (hash (x) + 2 * hash2 (x))% S también está lleno, entonces intentamos (hash (x) + 3 * hash2 (x))% S
………………………………………… ..

El sondeo lineal tiene el mejor rendimiento de caché, pero sufre de agrupamiento. Una ventaja más del sondeo lineal es fácil de calcular. El sondeo cuadrático se encuentra entre los dos en términos de rendimiento de caché y agrupación. El doble hashing tiene un rendimiento de caché deficiente pero no agrupa. El doble hashing requiere más tiempo de cálculo ya que se deben calcular dos funciones hash.

Evaluación del rendimiento de direccionamiento abierto : al igual que el encadenamiento, el rendimiento del hash se puede evaluar bajo el supuesto de que cada clave tiene la misma probabilidad de ser hash en cualquier ranura de la tabla (hashing uniforme simple) m = Número de ranuras en la tabla hash
n = El número de claves a insertar en la tabla tiene
Factor de carga α = n / m (<1)
Tiempo esperado para buscar / insertar / eliminar <1 / (1 – α)
Entonces Buscar, Insertar y Eliminar toma tiempo (1 / (1 – α))
El direccionamiento abierto requiere un cuidado especial para evitar la agrupación y el factor de carga.

AlgoritmosHashing