¿Qué son los Hash tables o tablas hash?

Una hash table es una estructura de datos que se encarga de asignar claves a valores para una búsqueda altamente eficiente, para implementar este tipo de estructura de datos podemos hacer uso por ejemplo de un simple arreglo de listas enlazadas y una función hash, la función hash será la encargada de transformar una clave dada en un hash o numero que identifiqué fácilmente donde se ubica o almacena un valor.

En términos más simples se puede decir que un hash table es una estructura de datos que se encarga de asociar llaves o claves, con valores específicos para una fácil búsqueda.

Generalmente una buena implementación de este estructura de datos mantiene un numero de colisiones mínimo, permitiendo así un acceso directo a los valores previamente almacenados, lo que quiere decir que tiene una complejidad de acceso O(1).

En el peor de los casos si el numero de colisiones es muy alto, podemos tener casos donde la complejidad de acceso sea O(n), por lo que la búsqueda se efectuara en base al numero de elementos.