Diapositiva PPT
2.5.3. Funciones de dispersión.
- Dispersión abierta.
- Tenemos B cubetas, y N elementos almacenados en total.
- Cada lista tendrá de media N/B miembros.
- Inserta, Suprime y Miembro tendrán un tiempo de O(1+N/B).
- Si N ? B, entonces tendremos O(cte).
- Suponemos una buena función h: reparte los elementos en las cubetas de forma uniforme.
- Dispersión cerrada.
- La tabla nunca se puede llenar con más de B elementos.
- La probabilidad de colisión crece cuantos más elementos hayan, disminuyendo la eficiencia.
- El costo de Inserta es O(1/(1-N/B)). Cuando N ? B tiende a infinito.
Reestructuración de las tablas de dispersión
- Para evitar el problema de la pérdida de eficiencia, si el tamaño de N aumenta mucho, se puede crear una nueva tabla con más elementos B, reestructurar.
- Dispersión abierta: reestructurar si N > 2 B
- Dispersión cerrada: reestructurar si N > 0.9 B