Foros de daboweb

MULTIMEDIA, Video digital, Grabación, Diseño gráfico, Diseño web, Programación => Webmasters - Diseño Web - Programación - Diseño gráfico => Mensaje iniciado por: luciagc en 05 de Mayo de 2005, 09:41:09 pm

Título: problema de tablas hash
Publicado por: luciagc en 05 de Mayo de 2005, 09:41:09 pm
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
Título: problema de tablas hash
Publicado por: BuHo en 07 de Mayo de 2005, 12:00:17 am
Esto es un reto, los deberes de mañana, una duda...¿?