Diapositiva PPT
2.5.3. Funciones de dispersión.
- Propiedades de una buena función de dispersión
- La función debe minimizar el número de sinónimos: debe ser lo más aleatoria posible y repartir los elementos en la tabla de manera uniforme.
- La función debe ser fácil de calcular (buscamos eficiencia).
- Ojo: h(x) es función de x, devuelve siempre el mismo valor para un mismo valor de x.
Algunas funciones de dispersión
- Método de la multiplicación. Dada una clave x entera:
h(x) = (x * C) mod B; para algún C, con C y B primos entre sí
- Método de tomar los dígitos centrales:
h(x) = ?x2 / 100? mod B
Escoger un C, tal que BC2 ? K2, para x en el intervalo (0, ..., K).
h(x)= (x2 / C) mod B Ej.: K= 1000; B= 8; C=354; h(456)= 3
- Otro posible método:
h(x) = (?C1*x2 / C2? + x*C3) mod B