Introducción

Una tabla hash es una estructura de datos que permite asociar claves con valores y cuya principal ventaja es una complejidad de inserción y busqueda de O(1) (O(n) en el peor de los casos).

Cuando tenemos la necesidad de almacenar datos en memoria tenemos una serie de opciones (listas enlazadas, arrays, arboles...) cada una de las cuales tienes sus ventajas y sus inconvenientes que normalmente consisten en establecer un compromiso entre espacio en memoria y velocidad.

Una lista enlazada aprovecha completamente el espacio de memoria pero la velocidad de busqueda es lineal, para encontrar un elemento debemos ir recorriendo la lista hasta encontrarlo, en un array reservamos toda la memoria que podríamos por adelantado pero por contra obtenemos un rendimiento de busqueda constante O(1). Los arboles constituyen una variación de las listas enlazadas en las cuales se mejora el rendimiento de busqueda (O(log(n))) a cambio de empeorar el rendimiento de inserción.