Hash Tables: std::unordered_map y std::unordered_set en C++

Cuando necesitas asociar una clave a un valor o simplemente verificar la existencia de un elemento con la máxima velocidad posible, te encuentras con las tablas hash. En C++, estas se implementan mediante std::unordered_map y std::unordered_set. A diferencia de std::map, que utiliza árboles de búsqueda binaria (generalmente árboles rojo-negro) para mantener los elementos ordenados, estas versiones “unordered” utilizan una estructura de buckets (cubos) basada en una función de dispersión o hash.

El funcionamiento es directo: una función de hash toma tu clave y la transforma en un size_t, el cual se mapea a un índice en un arreglo interno. Si dos claves distintas resultan en el mismo índice, ocurre una colisión. Para resolver esto, la implementación estándar suele usar encadenamiento, donde cada bucket contiene una lista de elementos que colisionaron. En términos de complejidad, esto nos da un $O(1)$ amortizado para inserción, búsqueda y borrado, lo que significa que, en promedio, el tiempo es constante. Sin embargo, si la función de hash es deficiente y provoca demasiadas colisiones, el rendimiento se degrada hasta un $O(n)$ en el peor de los casos, convirtiendo tu tabla hash en una simple lista enlazada.

Debes usar estas estructuras cuando el orden de los elementos no sea relevante y cuando el volumen de operaciones de búsqueda sea masivo. Si tus claves son, por ejemplo, enteros o strings cortos, una buena función de hash las hará volar. Sin embargo, si necesitas iterar los elementos de forma ordenada o si el costo de calcular el hash es prohibitivamente alto comparado con una simple comparación de claves, std::map suele ser una opción más predecible. Si te equivocas con la función de hash o no proporcionas una forma de comparar la igualdad de las claves, podrías terminar con una estructura que no encuentra elementos existentes o, peor aún, con un rendimiento desastroso que el compilador no podrá detectar.

#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>

// Representamos un recurso en un sistema de gestión
struct Recurso {
    uint64_t id;
    std::string etiqueta;

    // Para usar un objeto personalizado como clave en un contenedor 'unordered',
    // es MANDATORIO implementar el operador de igualdad. 
    // El contenedor lo usará para resolver colisiones: si dos hashes coinciden,
    // el contenedor usará '==' para saber si son el mismo objeto o solo una colisión.
    bool operator==(const Recurso& other) const noexcept {
        return id == other.id && etiqueta == other.etiqueta;
    }
};

// Implementamos un functor de hash personalizado para nuestro struct 'Recurso'.
// Esto es necesario porque std::hash no sabe cómo procesar un tipo arbitrario.
struct RecursoHasher {
    std::size_t operator()(const Recurso& r) const noexcept {
        // Combinamos los hashes de los miembros de la estructura.
        // Una técnica común es usar XOR y desplazamientos para evitar colisiones 
        // entre campos con valores similares.
        std::size_t h1 = std::hash<uint64_t>{}(r.id);
        std::size_t h2 = std::hash<std::string>{}(r.etiqueta);
        return h1 ^ (h2 << 1); 
    }
};

int main() {
    // std::unordered_map<Key, Value, Hasher, KeyEqual>
    std::unordered_map<Recurso, std::string, RecursoHasher> inventario;

    // Inserción de elementos
    inventario[{101, "Servidor_Principal"}] = "Activo";
    inventario[{102, "Base_Datos"}] = "Mantenimiento";
    inventario[{103, "Firewall"}] = "Activo";

    // Consulta rápida O(1)
    Recurso busca = {102, "Base_Datos"};
    if (auto it = inventario.find(busca); it != inventario.end()) {
        std::cout << "Estado de " << busca.etiqueta << ": " << it->second << "\n";
    }

    // Control de la densidad de la tabla
    // load_factor() = bucket_count() / size()
    // Si este valor sube demasiado, la probabilidad de colisiones aumenta.
    std::cout << "\n--- Diagnóstico de la tabla ---\n";
    std::cout << "Carga actual (load_factor): " << inventario.load_factor() << "\n";
    std::cout << "Número de buckets: " << inventario.bucket_count() << "\n";

    // Rehash: Forzamos el redimensionamiento para mejorar el rendimiento 
    // si sabemos que vamos a insertar miles de elementos más.
    inventario.rehash(100); 
    std::cout << "Buckets tras rehash(100): " << inventario.bucket_count() << "\n";

    // std::unordered_set para verificar existencia de recursos únicos
    std::unordered_set<Recurso, RecursoHasher> recursos_activos;
    recursos_activos.insert({101, "Servidor_Principal"});
    recursos_activos.insert({103, "Firewall"});

    return 0;
}

Análisis del código

En el ejemplo, la clave es un struct Recurso. Al no ser un tipo primitivo, el compilador no sabe cómo calcular su hash ni cómo compararlo. Por eso, definimos RecursoHasher y sobrecargamos operator==. Sin operator==, el contenedor no podría distinguir entre dos objetos distintos que accidentalmente produzcan el mismo valor de hash (una colisión), lo que rompería la lógica de la tabla.

La función operator() dentro de RecursoHasher es el núcleo del proceso. Utilizamos std::hash<T> para los miembros individuales y luego combinamos los resultados. Es vital que esta función sea determinista: si dos objetos son iguales según operator==, la función de hash debe devolver el mismo valor.

En cuanto al rendimiento, observa load_factor(). Este valor representa la densidad de elementos por bucket. Si el load_factor supera el max_load_factor() (que suele ser 1.0), el contenedor realizará automáticamente un rehash, aumentando el número de buckets para mantener las operaciones cerca de $O(1)$. En el ejemplo, llamamos a rehash(100) manualmente; esto es una optimización de producción común cuando conoces de antemano el tamaño aproximado de tus datos, evitando múltiples realocaciones costosas y reorganizaciones de la tabla mientras insertas elementos.

Finalmente, nota que std::unordered_map es extremadamente rápido para búsquedas, pero su estructura de buckets con listas enlazadas implica que los elementos no están contiguos en memoria. Esto puede causar cache misses en comparación con un std::vector o incluso con un std::map si la clave es muy pequeña y el árbol es muy profundo, debido a la naturaleza de seguir punteros para navegar por las colisiones.

El error frecuente

Un error crítico y silencioso ocurre cuando defines un Hasher personalizado para un tipo pero olvidas implementar (o implementas incorrectamente) el operator==.

struct MalaClave {
    int id;
    // Falta operator==
};

struct MalaHasher {
    size_t operator()(const MalaClave& k) const { return std::hash<int>{}(k.id); }
};

// ... en el main ...
std::unordered_map<MalaClave, std::string, MalaHasher> mapa;
mapa[{1}] = "Error";

// Esto podría fallar o dar resultados inesperados:
if (mapa.find({1}) != mapa.end()) { 
    // ¡Podría no entrar aquí aunque la clave existe!
}

Si operator== no está presente, el código puede compilar si usas un std::function o si el compilador es permisivo, pero en la práctica, el contenedor no podrá verificar si una colisión es realmente un duplicado o un objeto distinto. Esto resulta en un comportamiento indefinido o, más comúnmente, en la imposibilidad de encontrar elementos que claramente han sido insertados. Si activas con -Werror y usas herramientas como AddressSanitizer, podrías detectar inconsistencias, pero el error de lógica de “no encontrar la clave” es un bug clásico que solo se detecta mediante pruebas exhaustivas.

N° 86