Hash Table: encontrar sin buscar

Lic. Carlos Enrique Loria Beeche.

Quinto artículo técnico de la saga “Estructuras de datos: cuando la memoria se convierte en inteligencia”

Este artículo forma parte de la saga que inicié con Estructuras de datos: cuando la memoria se convierte en inteligencia, donde presenté las ocho estructuras de datos fundamentales que iremos recorriendo paso a paso.

En las entregas anteriores estudiamos el array, el estacionamiento numerado de la memoria, la linked list, la búsqueda del tesoro en la memoria, la stack, la pila y el recuerdo del último paso, y la queue, la cola y la justicia del turno.

Ahora entramos en una estructura especialmente importante para el software moderno: la hash table, o tabla hash.

La tabla hash aparece detrás de diccionarios, mapas, objetos, índices, cachés, conteos, búsquedas rápidas y muchas estructuras internas de los lenguajes de programación. Su promesa es muy atractiva: encontrar un dato sin tener que recorrer toda la colección.

Una tabla hash nos enseña que, cuando existe una buena clave y una buena función para interpretarla, buscar puede dejar de ser un recorrido y convertirse casi en un salto directo.

¿Qué es una hash table?

Una hash table, o tabla hash, es una estructura de datos que guarda información usando pares de clave y valor.

La clave es lo que usamos para buscar. El valor es la información que queremos recuperar.

Por ejemplo:

Clave: "Carlos"
Valor: "carlos@example.com"

Clave: "Ana"
Valor: "ana@example.com"

Clave: "Luis"
Valor: "luis@example.com"

La idea es que, si conocemos la clave "Carlos", podamos encontrar rápidamente su valor asociado, sin revisar todos los registros uno por uno.

La analogía del diccionario

Podemos imaginar una tabla hash como un diccionario muy eficiente.

Si buscamos una palabra en un diccionario de papel, no empezamos desde la primera página y avanzamos palabra por palabra hasta encontrarla. Usamos el orden alfabético para ir directamente a una zona aproximada.

Una tabla hash hace algo parecido, pero de forma más directa. Usa una función para transformar una clave en una posición dentro de una tabla.

La pregunta ya no es simplemente:

¿Dónde está este dato?

La pregunta se convierte en:

¿A qué posición me lleva esta clave?

Clave, valor y función hash

El corazón de una tabla hash está en la función hash.

Una función hash recibe una clave y produce un número. Ese número se usa para decidir en qué posición de la tabla debe guardarse el valor.

clave -> función hash -> posición

Por ejemplo:

"Ana"    -> hash("Ana")    -> posición 3
"Luis"   -> hash("Luis")   -> posición 1
"Carlos" -> hash("Carlos") -> posición 5

Entonces la tabla podría guardar los datos así:

Posición 0: vacío
Posición 1: Luis   -> luis@example.com
Posición 2: vacío
Posición 3: Ana    -> ana@example.com
Posición 4: vacío
Posición 5: Carlos -> carlos@example.com

Cuando queremos buscar a Carlos, no recorremos toda la tabla. Calculamos nuevamente hash("Carlos"), obtenemos la posición 5 y vamos directamente allí.

La función hash convierte una clave en una ruta rápida hacia el dato.

¿Qué es un bucket?

En muchas explicaciones se usa la palabra bucket, que podríamos traducir como casilla, cubeta o compartimento.

Un bucket es una posición de la tabla donde puede guardarse uno o más elementos.

La tabla hash no guarda los datos simplemente en una lista larga. Los distribuye entre buckets usando la función hash.

Bucket 0: vacío
Bucket 1: Luis
Bucket 2: vacío
Bucket 3: Ana
Bucket 4: vacío
Bucket 5: Carlos

La eficiencia de la tabla hash depende mucho de que los datos queden bien distribuidos. Si todos cayeran en el mismo bucket, perderíamos gran parte de la ventaja.

Colisiones: cuando dos claves llegan al mismo lugar

Una tabla hash tiene un problema inevitable: las colisiones.

Una colisión ocurre cuando dos claves distintas producen la misma posición.

hash("Carlos") -> posición 2
hash("Celia")  -> posición 2

En este caso, ambas claves quieren ocupar el mismo bucket.

Esto no significa que la tabla hash haya fallado. Significa que debe tener una estrategia para manejar colisiones.

Formas comunes de resolver colisiones

Hay varias formas de resolver colisiones. Dos de las más conocidas son:

Encadenamiento

En el encadenamiento, cada bucket puede contener una pequeña lista de elementos.

Bucket 2: Carlos -> Celia

Si dos claves llegan al mismo bucket, se guardan en una lista dentro de esa posición. Luego, al buscar, primero vamos al bucket correcto y después revisamos los elementos de esa pequeña lista.

Direccionamiento abierto

En el direccionamiento abierto, si una posición está ocupada, la tabla busca otra posición disponible siguiendo una regla determinada.

Por ejemplo, puede probar la siguiente casilla, o saltar usando otro cálculo.

Posición 2 ocupada
Probar posición 3
Probar posición 4
...

El objetivo es encontrar un espacio libre sin salir de la propia tabla.

Una buena tabla hash no evita todas las colisiones; más bien sabe manejarlas correctamente.

Ventaja principal: búsqueda rápida

La gran ventaja de una tabla hash es la velocidad promedio.

En condiciones normales, buscar, insertar o eliminar un elemento puede ser muy rápido:

Búsqueda promedio:   O(1)
Inserción promedio:  O(1)
Eliminación promedio: O(1)

Esto significa que, en promedio, la operación puede tomar un tiempo casi constante, incluso si la tabla tiene muchos elementos.

Pero es importante decirlo con precisión: ese rendimiento depende de una buena función hash, una tabla con tamaño adecuado y una estrategia correcta para manejar colisiones.

El peor caso

En el peor caso, una tabla hash puede degradarse.

Si muchas claves caen en el mismo bucket, podríamos terminar revisando muchos elementos dentro de una lista interna.

Peor caso: O(n)

Por eso, aunque solemos decir que las tablas hash son muy rápidas, no debemos olvidar que esa rapidez depende de una buena implementación.

Factor de carga

Otro concepto importante es el factor de carga.

El factor de carga indica qué tan llena está la tabla.

factor de carga = cantidad de elementos / cantidad de buckets

Si una tabla tiene 100 buckets y 50 elementos, su factor de carga es:

50 / 100 = 0.5

Si la tabla se llena demasiado, aumentan las probabilidades de colisiones. Por eso muchas implementaciones hacen crecer la tabla automáticamente cuando el factor de carga supera cierto límite.

Ese proceso suele llamarse rehashing: se crea una tabla más grande y se redistribuyen los elementos usando nuevamente la función hash.

Operaciones básicas de una hash table

Operación	Descripción	Costo promedio
insertar	Guardar un valor asociado a una clave	O(1)
buscar	Obtener un valor usando su clave	O(1)
eliminar	Quitar un par clave-valor	O(1)
actualizar	Cambiar el valor asociado a una clave existente	O(1)
recorrer	Visitar todos los pares clave-valor	O(n)

La tabla hash es especialmente fuerte cuando buscamos por clave. No es una estructura pensada para mantener los datos ordenados, sino para encontrarlos rápido.

Ejemplo en C++

En C++, una forma común de usar una tabla hash es mediante unordered_map.

#include &lt;iostream&gt;
#include &lt;unordered_map&gt;
#include &lt;string&gt;
using namespace std;

int main() {
    unordered_map&lt;string, string&gt; correos;

    correos["Carlos"] = "carlos@example.com";
    correos["Ana"] = "ana@example.com";
    correos["Luis"] = "luis@example.com";

    cout &lt;&lt; "Correo de Carlos: " &lt;&lt; correos["Carlos"] &lt;&lt; endl;

    correos["Carlos"] = "carlos.loria@example.com";

    cout &lt;&lt; "Correo actualizado de Carlos: "
         &lt;&lt; correos["Carlos"] &lt;&lt; endl;

    if (correos.find("Ana") != correos.end()) {
        cout &lt;&lt; "Ana existe en la tabla." &lt;&lt; endl;
    }

    correos.erase("Luis");

    for (const auto& par : correos) {
        cout &lt;&lt; par.first &lt;&lt; " -> " &lt;&lt; par.second &lt;&lt; endl;
    }

    return 0;
}

En este ejemplo, el nombre funciona como clave y el correo como valor. La estructura permite buscar, insertar, actualizar y eliminar elementos usando la clave.

Ejemplo en C#

En C#, podemos usar Dictionary<TKey, TValue>, una de las estructuras más utilizadas para trabajar con pares clave-valor.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary&lt;string, string&gt; correos = new Dictionary&lt;string, string&gt;();

        correos["Carlos"] = "carlos@example.com";
        correos["Ana"] = "ana@example.com";
        correos["Luis"] = "luis@example.com";

        Console.WriteLine("Correo de Carlos: " + correos["Carlos"]);

        correos["Carlos"] = "carlos.loria@example.com";

        Console.WriteLine("Correo actualizado de Carlos: " + correos["Carlos"]);

        if (correos.ContainsKey("Ana"))
        {
            Console.WriteLine("Ana existe en el diccionario.");
        }

        correos.Remove("Luis");

        foreach (KeyValuePair&lt;string, string&gt; par in correos)
        {
            Console.WriteLine(par.Key + " -> " + par.Value);
        }
    }
}

En C#, el diccionario permite asociar una clave con un valor y recuperar ese valor de forma muy eficiente.

Ejemplo en Python

En Python, el tipo dict es una implementación de tabla hash para pares clave-valor.

correos = {}

correos["Carlos"] = "carlos@example.com"
correos["Ana"] = "ana@example.com"
correos["Luis"] = "luis@example.com"

print("Correo de Carlos:", correos["Carlos"])

correos["Carlos"] = "carlos.loria@example.com"

print("Correo actualizado de Carlos:", correos["Carlos"])

if "Ana" in correos:
    print("Ana existe en el diccionario.")

del correos["Luis"]

for clave, valor in correos.items():
    print(clave, "->", valor)

Los diccionarios de Python son una herramienta fundamental. Se usan constantemente para representar objetos, configuraciones, índices, conteos y asociaciones entre claves y valores.

Ejemplo práctico: contar palabras

Una aplicación clásica de una tabla hash es contar frecuencias.

Supongamos que tenemos una lista de palabras:

["sol", "luna", "sol", "mar", "luna", "sol"]

Queremos saber cuántas veces aparece cada palabra.

Una tabla hash permite usar cada palabra como clave y su cantidad como valor.

sol  -> 3
luna -> 2
mar  -> 1

En Python, por ejemplo, podríamos escribir:

palabras = ["sol", "luna", "sol", "mar", "luna", "sol"]

conteo = {}

for palabra in palabras:
    if palabra in conteo:
        conteo[palabra] += 1
    else:
        conteo[palabra] = 1

print(conteo)

Esta idea aparece en buscadores, análisis de texto, estadísticas, procesamiento de logs, conteos de inventario y muchas otras aplicaciones.

¿Cuándo conviene usar una hash table?

Una tabla hash conviene cuando necesitamos asociar claves con valores y buscar rápidamente por clave.

Algunos casos típicos son:

Diccionarios de palabras.
Mapas de identificadores a objetos.
Índices de búsqueda.
Cachés.
Conteo de frecuencias.
Validación de existencia de elementos.
Asociar usuarios con perfiles.
Guardar configuraciones por nombre.
Representar objetos simples mediante pares clave-valor.

En cambio, si necesitamos mantener los datos ordenados, recorrerlos en orden o buscar rangos, una tabla hash no siempre es la mejor opción. Para eso pueden convenir otras estructuras, como árboles balanceados.

Aplicaciones reales

Las tablas hash están en muchísimas partes del software moderno.

Los diccionarios de Python.
Los Dictionary de C#.
Los unordered_map de C++.
Índices internos en sistemas de búsqueda.
Cachés de memoria.
Tablas de símbolos en compiladores.
Validación rápida de duplicados.
Conteo de visitas, palabras o eventos.
Asociaciones entre identificadores y registros.

Cuando un programa necesita responder rápido a la pregunta “¿existe esta clave?” o “¿cuál es el valor asociado a esta clave?”, probablemente una tabla hash sea una buena candidata.

La lección de la tabla hash

La tabla hash enseña una idea muy poderosa: buscar no siempre tiene que significar recorrer.

El array nos enseñó el poder del índice. La lista enlazada nos enseñó el valor del enlace. La pila nos enseñó el valor del retorno. La cola nos enseñó el valor del turno. La tabla hash nos enseña el poder de la clave.

Cuando tenemos una buena clave, una buena función hash y una estrategia adecuada para manejar colisiones, podemos encontrar datos con enorme rapidez.

Pero también aprendemos una lección importante: la velocidad no aparece por arte de magia. Depende del diseño.

La tabla hash nos recuerda que una buena forma de preguntar puede ser tan importante como la respuesta que buscamos.

Próxima entrega

En el próximo artículo de esta saga estudiaremos el binary search tree, o árbol binario de búsqueda. Allí veremos una estructura que organiza los datos de forma jerárquica para buscar comparando, descartando caminos y tomando decisiones.

Pasaremos de encontrar por clave a encontrar por orden.