Programacion · conceptos · estructuras de datos

Que es una hash table?

Una hash table (tambien llamada hash map) es una estructura de datos que almacena pares clave-valor y te permite encontrar cualquier valor por su clave en, de media, tiempo constante, sin importar cuantos datos contenga. Es una de las estructuras mas utiles de toda la programacion, y es lo que impulsa los diccionarios y mapas incorporados en casi todos los lenguajes. Una vez que ves como funciona, muchos momentos de "como puede ser esto tan rapido?" cobran sentido.

El problema que resuelve

Imagina almacenar una guia telefonica como una simple lista. Para encontrar a una persona, podrias tener que recorrer cada entrada: un trabajo lento que se vuelve mas lento a medida que la guia crece, una operacion O(n). La promesa de una hash table es distinta: le das la clave y salta mas o menos directamente al valor, sin recorrer nada. Esa es la diferencia entre revisar cada entrada y saber exactamente donde mirar.

Como funciona: la hash function y los buckets

Por debajo, una hash table se apoya en un array de ranuras llamadas buckets. El ingrediente magico es la hash function: toma tu clave y la convierte en un numero, que se mapea a un indice en ese array.

index = hash(key) % number_of_buckets

Para almacenar un valor, aplicas el hash a la clave para obtener un indice y colocas el valor en ese bucket. Para leerlo de nuevo, aplicas el hash a la misma clave otra vez, caes en el mismo indice y recoges el valor. Como calcular el hash e indexar un array son pasos rapidos de coste fijo, las busquedas no se vuelven mas lentas a medida que la tabla crece. Ese es todo el truco.

Collisions y como se gestionan

Dos claves diferentes pueden producir el mismo bucket. Eso se llama collision, y toda hash table real tiene que afrontarlo. Hay dos estrategias comunes:

• Chaining: cada bucket contiene una lista pequena, y las entradas en collision se almacenan juntas en esa lista. Las busquedas revisan entonces la lista (normalmente muy corta) del bucket correcto.
• Open addressing: si un bucket esta ocupado, la tabla sondea la siguiente ranura libre segun una regla fija, y las busquedas siguen la misma regla.

Con una buena hash function y suficientes buckets, las collisions siguen siendo raras y esas listas siguen siendo diminutas, asi que las busquedas siguen siendo rapidas.

Que pasa con el rendimiento?

Aqui es donde brillan las hash tables, y donde vive la advertencia honesta. De media, insertar, buscar y eliminar son todas O(1): tiempo constante. En el peor caso, si una mala hash function o una entrada hostil vuelca todas las claves en un solo bucket, esas operaciones degradan a O(n), porque vuelves a recorrer una unica lista larga. Las buenas implementaciones evitan esto usando hash functions solidas y haciendo resizing (rehashing hacia un array mas grande) cuando la tabla se llena demasiado, lo que mantiene el rendimiento en O(1) amortizado. Si quieres un repaso de esta notacion, consulta nuestra guia sobre Big O notation.

Donde ya la usas

Usas hash tables constantemente, a menudo sin nombrarlas. Los tipos diccionario y mapa de la mayoria de lenguajes son hash tables por debajo: Python dict, Java HashMap, JavaScript Map y object, Ruby Hash, Go map. Tambien son la herramienta preferida para caches, deduplicar elementos y contar ocurrencias. La clasica optimizacion de convertir una busqueda lenta con bucles anidados en una rapida, bajando de O(n²) a O(n), casi siempre se hace reemplazando recorridos repetidos por una busqueda en hash table.

Los compromisos

• Rapida, pero desordenada. Una hash table basica no mantiene las claves en ningun orden ordenado o de insercion (aunque algunas versiones de lenguajes anaden ordenacion encima).
• Usa memoria extra. Mantener raras las collisions implica mantener buckets de sobra, asi que una hash table intercambia algo de memoria por su velocidad.
• El peor caso es real. El O(1) es una media; una entrada adversaria puede forzar el camino lento, lo que importa en codigo sensible a la seguridad.

FAQ

Es una hash table lo mismo que un diccionario? En terminos cotidianos, si: un diccionario o mapa es la idea general (clave a valor), y una hash table es la forma mas comun de implementarlo. Cuando alguien dice Python "dict" o Java "HashMap", esta usando una hash table.

Por que la busqueda es O(1) de media? Porque calculas el hash de la clave e indexas directamente en un array, en lugar de recorrer entradas. Ambos pasos toman tiempo constante sin importar cuantos elementos se almacenen, asi que el coste medio no crece con los datos.

Que es una collision? Cuando dos claves diferentes producen el mismo bucket. Es normal y esperado; las hash tables lo gestionan con chaining u open addressing, y lo mantienen raro con una buena hash function y resizing.

Cuando no deberia usar una hash table? Cuando necesitas mantener las claves en orden ordenado, o consultas por rango ordenado: una estructura basada en arboles encaja mejor. Tambien cuando la memoria es extremadamente ajustada, ya que las hash tables mantienen espacio de sobra para seguir siendo rapidas.

Guias relacionadas: Big O notation, que es un algoritmo.