Diapositiva PPT
2.5. La tabla de dispersión (tabla hash).
- La representación de conjuntos o diccionarios con listas o arrays tiene un tiempo de O(n), para Inserta, Suprime y Miembro.
- Con vectores de bits el tiempo es O(cte), pero tiene muchas limitaciones.
- ¿Cómo aprovechar lo mejor de uno y otro tipo?
- Idea:
- Usar un array con B posiciones (0, ..., B-1).
- Dada una clave x (sea del tipo que sea) calcular una posición mediante una función:
h(x) = posición en (0..B-1) h: Función de dispersión
- El elemento (x, v) se inserta en esa posición.