Problemas de práctica sobre hashing

En este artículo, discutiremos los tipos de preguntas basadas en hashing. Antes de comprender esto, debe tener una idea sobre el hash, la función hash, el direccionamiento abierto y las técnicas de enstringmiento (ver: Introducción , Enstringmiento separado , Direccionamiento abierto ). 

Estos son algunos puntos clave en el hashing: 
 

• El propósito del hashing es lograr buscar, insertar y borrar un elemento en complejidad O(1).
• La función hash está diseñada para distribuir claves uniformemente sobre la tabla hash.
• El factor de carga α en la tabla hash se puede definir como el número de ranuras en la tabla hash para el número de claves que se insertarán.
• Para direccionamiento abierto, el factor de carga α siempre es menor que uno.
• La complejidad de inserción, borrado y búsqueda usando direccionamiento abierto es 1/(1-α).
• La complejidad de inserción, eliminación y búsqueda mediante el método de enstringmiento es (1+α).

Estos son los tipos de preguntas que se hacen en hash. 

Tipo 1: Cálculo de valores hash para claves dadas: 
en este tipo de preguntas, los valores hash se calculan aplicando una función hash dada en claves dadas. 

Que – 1. Dada la siguiente entrada (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) y la función hash x mod 10, ¿cuáles de las siguientes afirmaciones son verdaderas? (GATE CS 2004) 
i. 9679, 1989, 4199 hash al mismo valor 
ii. 1471, 6171 hash al mismo valor 
iii. Todos los elementos tienen el mismo valor 
iv. Cada elemento tiene un valor diferente 
(A) solo i 
(B) solo ii 
(C) solo i y ii 
(D) iii o iv 

Soluciones: Usar la función hash dada h(x) = x mod 10 
 

h(9679) = 9679%10 = 9 
h(1989) = 1989%10 = 9 
h(4199) = 4199%10 = 9 
h(1471) = 1471%10 = 1 
h(6171) = 6171%10 = 1 

Como podemos ver, 9679, 1989 y 4199 tienen el mismo valor 9. Además, 1471 y 6171 tienen el mismo valor 1. Por lo tanto, las declaraciones (i) y (ii) son correctas y coinciden con la opción (C). 

Tipo 2: Inserción de claves en la tabla hash utilizando sondeo lineal como técnica de resolución de colisiones: 
en la técnica de sondeo lineal, la colisión se resuelve buscando linealmente en la tabla hash hasta que se encuentra una ubicación vacía. 

Que – 2. Las claves 12, 18, 13, 2, 3, 23, 5 y 15 se insertan en una tabla hash inicialmente vacía de longitud 10 utilizando direccionamiento abierto con función hash h(k) = k mod 10 y sondeo lineal. ¿Cuál es la tabla hash resultante? 

Solución: Las claves 12, 18, 13, 2, 3, 23, 5 y 15 se insertan en la tabla hash como: 

Para la clave 12, h(12) es 12%10 = 2. Por lo tanto, 12 se coloca en el segundo índice de la tabla hash. 
Para la clave 18, h(18) es 18%10 = 8. Por lo tanto, 18 se coloca en el octavo índice de la tabla hash. 
Para la clave 13, h(13) es 13%10 = 3. Por lo tanto, 13 se coloca en el tercer índice de la tabla hash. 
Para la clave 2, h(2) es 2%10 = 2. Sin embargo, el índice 2 ya está ocupado con 12. Por lo tanto, usando palpación lineal, 2 se colocará en el índice 4 ya que los índices 2 y 3 ya están ocupados. 
Para la tecla 3, h(3) es 3%10 = 3. Sin embargo, el índice 3 ya está ocupado con el 13. Por lo tanto, usando palpación lineal, el 3 se colocará en el índice 5 ya que los índices 3 y 4 ya están ocupados. 
Del mismo modo, 23, 5 y 15 se colocarán en el índice 6, 7, 9 respectivamente. 

Por lo tanto, la opción correcta es (C). 

Enfoque alternativo: también podemos resolver esto usando el enfoque de eliminación como: 

Las opciones (A) y (B) son incorrectas ya que no todas las claves se insertan en la tabla hash. 
La opción (D) es incorrecta ya que algunos índices en la tabla hash tienen más de una clave, lo que nunca ocurre con el sondeo lineal. 
La opción restante es (C), que es la respuesta. 

Tipo 3: dada una tabla hash con claves, verificar/encontrar la posible secuencia de claves que conducen a la tabla hash: 
para una tabla hash dada, podemos verificar qué secuencia de claves puede conducir a esa tabla hash. Sin embargo, para encontrar posibles secuencias que conduzcan a una tabla hash dada, debemos considerar todas las posibilidades. 

Que – 3. Una tabla hash de longitud 10 utiliza direccionamiento abierto con función hash h(k)=k mod 10 y sondeo lineal. Después de insertar 6 valores en una tabla hash vacía, la tabla es como se muestra a continuación. 
 

¿Cuál de las siguientes opciones da un orden posible en el que los valores clave podrían haberse insertado en la tabla? 
(A) 46, 42, 34, 52, 23, 33 
(B) 34, 42, 23, 52, 33, 46 
(C) 46, 34, 42, 23, 52, 33 
(D) 42, 46, 33 , 23, 34, 52 

Solución: Verificaremos si la secuencia dada en la opción A puede conducir a la tabla hash dada en cuestión. La opción A inserta 46, 42, 34, 52, 23, 33 como: 

Para la clave 46, h(46) es 46%10 = 6. Por lo tanto, 46 ​​se coloca en el sexto índice de la tabla hash. 
Para la clave 42, h(42) es 42%10 = 2. Por lo tanto, 42 se coloca en el segundo índice de la tabla hash. 
Para la clave 34, h(34) es 34%10 = 4. Por lo tanto, 34 se coloca en el cuarto índice de la tabla hash. 
Para la clave 52, h(52) es 52%10 = 2. Sin embargo, el índice 2 está ocupado con 42. Por lo tanto, 52 se coloca en el tercer índice de la tabla hash. Pero en la tabla hash dada, 52 se coloca en el quinto índice. Por lo tanto, la secuencia en la opción A no puede generar la tabla hash dada en cuestión. 

De manera similar, también podemos verificar otras opciones que conducen a la respuesta como (C). 

Que – 4. ¿Cuántas secuencias de inserción diferentes de valores clave usando la misma función hash y sondeo lineal resultarán en la tabla hash dada en la Pregunta 3 anterior? 
(A) 10 
(B) 20 
(C) 30 
(D) 40 

Solución: La primera clave que no está en el índice calculado por la función hash es 52. Significa que los índices 2, 3 y 4 ya estaban ocupados y, por lo tanto, la clave 52 se coloca en el índice 5. 

Las claves 42, 23 y 34 están presentes en los índices 2, 3 y 4 respectivamente. Como estas teclas están en su posición correcta, su orden de inserción no importa. ¡Estas 3 llaves se pueden insertar en 3! = 6 maneras. Por lo tanto, la secuencia será cualquier orden de (42, 23, 34) seguida de 52. 

La siguiente clave que no está en el índice calculado por la función hash es 33. Significa que los índices 3 a 6 ya estaban ocupados y la clave 33 se coloca en el índice 7. Por lo tanto, es la última clave que se inserta en la tabla hash. 

La clave 46 está presente en su posición correcta calculada por la función hash. Por lo tanto, se puede insertar en cualquier lugar de la secuencia antes de 33. La secuencia que excluye 33 tiene 4 elementos 42, 23, 34, 52 que crean 5 posiciones para 46 (3 en el medio y 2 en las esquinas). 
El número total de formas es: 6*5 =30 

Tipo 4: técnica de resolución de colisiones basada en enstringmiento: en la técnica de resolución de colisiones 
basada en enstringmiento, las claves que generan el mismo valor hash se colocan en el mismo depósito mediante punteros. Los diferentes tipos de preguntas basadas en la técnica del enstringmiento son: 

Que – 5. Considere una tabla hash con 100 ranuras. Las colisiones se resuelven mediante enstringmiento. Suponiendo un hashing uniforme simple, ¿cuál es la probabilidad de que las primeras 3 ranuras estén vacías después de las primeras 3 inserciones? (GATE-CS-2014) 
(A) (97 × 97 × 97)/100^3 
(B) (99 × 98 × 97)/100^3 
(C) (97 × 96 × 95)/100^3 
( D) (97 × 96 × 95)/(3! × 100^3) 

Solución: en el hashing uniforme, la función distribuye las claves de manera uniforme en las ranuras de la tabla hash. Además, cada llave tiene la misma probabilidad de ser colocada en una ranura, siendo independiente de los demás elementos ya colocados. 

Por lo tanto, la probabilidad de que queden vacías las primeras 3 ranuras para la primera inserción (elegir de 4 a 100 ranuras) = ​​97/100. Como las próximas inserciones son independientes de la anterior, la probabilidad de próximas inserciones también será 97/100. La probabilidad requerida será (97/100)^3. 

Que – 6. ¿Cuál de las siguientes funciones hash en números enteros distribuirá las claves de manera más uniforme en 10 cubos numerados del 0 al 9 para i que van desde 0 a 2020? (GATE-CS-2015) 
(A) h(i) =i^2 mod 10 
(B) h(i) =i^3 mod 10 
(C) h(i) = (11 ∗ i^2) mod 10 
(D) h(i) = (12 ∗ i) módulo 10 

Solución: en la distribución uniforme, la función distribuye las claves de manera uniforme en las ranuras de la tabla hash. 
Para funciones hash dadas, hemos calculado valores hash para las claves 0 a 9 como: 

Como podemos ver en la tabla, i^3 mod10 se distribuye uniformemente desde los índices 0 a 9. Otras funciones no han utilizado todos los índices.