PUERTA | PUERTA CS 2020 | Pregunta 33

Considere un esquema de hash doble en el que la función hash primaria es h ₁ (k) = k mod 23, y la función hash secundaria es h ₂ (k) = 1+(k mod 19). Suponga que el tamaño de la tabla es 23. Luego, la dirección devuelta por la sonda 1 en la secuencia de sonda (suponga que la secuencia de sonda comienza en la sonda 0) para el valor clave k = 90 es ________.

Nota: esta pregunta era de tipo numérico.
(A) 13
(B) 15
(C) 21
(D) 23

Respuesta: (A)
Explicación: Dado, 
 

Table size = 23,
key value k = 90,
And, probe i = 1 (probe 1 in the probe sequence) 

De acuerdo con el doble hashing , usamos la fórmula como, 
 

(h1(k) + i*h2(k)) mod (table size) 

donde ‘i’ denota el valor de la sonda. 

Ahora, 
 

h1(k) = k mod 23 = 90 mod 23 = 21

And,
h2(k) = 1+(k mod 19) = 1+(90 mod 19) = 15 

Usando doble hashing, 
 

= (h1(k) + i*h2(k)) mod (table size)
= (21 + 15) mod 23
= 36 mod 23
= 13 

La opción (A) es correcta.

Cuestionario de esta pregunta