PUERTA | GATE-CS-2015 (Conjunto 2) | Pregunta 65 – Part 5

¿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 del 0 al 2020?
 

(A)

h(i) = (12 ∗ i) módulo 10
 

(B)

h(i) = (11 ∗ yo ² ) módulo 10
 

(C)

h(i) =i ³ módulo 10
 

(D)

h(i) =i ² módulo 10 
 

Respuesta: (C)
Explicación:

Dado que se usa el mod 10, el último dígito es importante. 

Si elevas al cubo todos los números del 0 al 9, obtienes lo siguiente 

Number    Cube    Last Digit in Cube
  0        0              0 
  1        1              1 
  2        8              8 
  3        27             7 
  4        64             4 
  5        125            5 
  6        216            6
  7        343            3
  8        512            2
  9        729            9  

Por lo tanto, todos los números del 0 al 2020 se dividen por igual en 10 cubos. Si hacemos una tabla por cuadrado, no obtenemos una distribución equitativa. En la siguiente tabla. 1, 4, 6 y 9 se repiten, por lo que estos cubos tendrían más entradas y los cubos 2, 3, 7 y 8 estarían vacíos. 

Number   Square     Last Digit in Square
  0        0              0 
  1        1              1 
  2        4              4 
  3        9              9 
  4        16             6
  5        25             5 
  6        36             6
  7        49             9
  8        64             4
  9        81             1  

Enfoque alternativo: 
uso del concepto de potencia del ciclo: 

(a) (0,1,4,9,6,5,6,9,4,1,0) repetido 
(b) (0,1,8,7,4,5,6,3,2,9 ) repetido 
(c) (0,1,4,9,6,5,6,9,4,1,0) repetido 
(d) (0,2,4,6,8) repetido 

Entonces, solo h(i) =i ³ mod 10 cubre todos los dígitos del 0 al 9. 
La opción (B) es correcta. 

Cuestionario de esta pregunta
Comente a continuación si encuentra algo incorrecto en la publicación anterior