Autor Tema: problema de tablas hash  (Leído 2499 veces)

Desconectado luciagc

  • Newbie
  • *
  • Mensajes: 1
problema de tablas hash
« 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

Desconectado BuHo

  • Pro Member
  • ****
  • Mensajes: 733
    • La Estancia Azul
problema de tablas hash
« Respuesta #1 en: 07 de Mayo de 2005, 12:00:17 am »
Esto es un reto, los deberes de mañana, una duda...¿?
Wake up BuHo...
Daboweb has you[/color]
Mi blog: La Estancia Azul

 

Aviso Legal | Política de Privacidad | Política de Cookies

el contenido de la web se rige bajo licencia
Creative Commons License