En la estructura de datos conocida como tabla hash, ¿qué consecuencias tiene que se produzca una "colisión de claves" al intentar añadir un nuevo elemento?
- A.En una tabla hash nunca pueden darse colisiones, ya que en eso consiste la principal ventaja de usar una función hash sobre las tablas habituales.
- B.En una tabla hash las colisiones son un fenómeno normal, que se resuelve encadenando los valores en una lista o usando direccionamiento abierto.Respuesta correcta
- C.En una tabla hash podrán darse colisiones, pero matemáticamente es tan improbable que no se hacen previsiones especiales para el caso.
- D.En una tabla hash siempre ocurren colisiones, ya que la colisión es un requisito del algoritmo de inserción en la tabla.
Explicación
En una tabla hash, una COLISIÓN se produce cuando la función hash calcula e intenta asignar a dos claves distintas la misma posición del array de almacenamiento. Este es un fenómeno completamente NORMAL e inevitable en la práctica cuando el espacio total de claves posibles es mayor que el número de posiciones disponibles en la tabla (principio del palomar en teoría matemática). Los diseñadores de tablas hash han desarrollado técnicas estándar comprobadas para resolver colisiones: encadenamiento (mediante listas enlazadas en cada posición) o direccionamiento abierto (probing lineal, probing cuadrático, o hashing doble). El rendimiento de la tabla depende en parte de la calidad de manejo de colisiones.