¿Cuál es el coste de búsqueda medio y en el peor caso en una hash table?

Opciones

1. O(1) de media, O(n) en el peor caso (Opción correcta)
2. O(log n) tanto de media como en el peor caso
3. O(1) tanto de media como en el peor caso
4. O(n) de media, O(n²) en el peor caso

Respuesta

O(1) de media, O(n) en el peor caso

Por qué

Una hash table (dict o set de Python) calcula un hash de la clave para saltar directamente a la posición correcta, así que una búsqueda tarda casi lo mismo sea cual sea su tamaño: O(1) de media.

Si muchas claves caen en la misma posición (colisiones), debe revisarlas una a una; en el peor caso eso es O(n). Las buenas funciones hash hacen que esto sea muy raro.

Recuerda

Búsqueda en dict/set ≈ O(1).

Términos clave

• Tabla hash
• Notación Big-O
• Colisión de hash
• Función hash
• Tabla