Diapositiva PPT
2.5. La tabla de dispersión (tabla hash).
- El tipo de x no está restringido. Si es un registro, podemos tomar uno de sus campos como clave, y aplicar la función sobre él.
- Función de dispersión: h: Clave ? [0, ..., B-1]
- Tamaño de la tabla B: aproximadamente sobre el número de elementos de los conjuntos (normalmente, B << rango de claves).
- ¿Qué ocurre si para dos elementos distintos x, y, ocurre que h(x) = h(y)?
- Definición: Si (x ? y) ? (h(x) = h(y)) entonces se dice que x, y son sinónimos.
- Los distintos métodos de dispersión difieren en el tratamiento de los sinónimos. Tipos de dispersión:
- Dispersión abierta.
- Dispersión cerrada.