En un hashing cerrado, las funciones hash mejoran la resolucion de colisiones
utilizando \"aleatoriedad\" en la busqueda de alternativas cuando se produce una
colision. Imaginemos la siguiente situacion:
1.- Usamos una funcion hash h(k) = k % M como funcion base para introducir las
claves en una Tabla Hash cerrada.
2.- Cuando se produce una colision usamos el siguiente esquema de hashing doble
para la busqueda de una localizacion vacia en la que insertar la clave:
h_i(k) = [ h(k) + d_i] mod M i=1,2,....
para alguna secuencia d_1, d_2,..., d_(M-1) que no cicle antes de tiempo, es
decir que pueda acceder a todas las posibles localizaciones de la tabla hash
antes de repetir ninguna. Dicho de otra forma, genera una secuencia de valores
que incluye a los enteros entre 0 y M-1 y los genera aleatoriamente todos antes
de alguno se repita.
3.-Supongamos que elegimos los valores d_i como:
d_i = [(a*d_(i-1) + c) % M] i=1,2,...
con a, c numeros reales.
Se pide:
Encontrar unos valores de a y c adecuados para que la sucesion no cicle antes de
tiempo y en consecuencia el esquema de hashing sea valido, en 2 casos distintos:
a) cuando M sea primo. P.ej. M=17
b) cuando M no sea primo. P.ej. M=16
