Estructuras de datos en C/C++

La tabla hash (hash table) en C y C++

En esta lección vas a contar cuántas veces aparece cada palabra con una tabla hash escrita a mano en C y con std::unordered_map en C++.

Introducción

Una tabla hash (hash table) usa una función hash (hash function) para convertir cada clave en el índice de una casilla de almacenamiento (bucket), lo que hace muy rápidas la búsqueda, la inserción y el borrado. Cuando dos claves distintas caen en la misma casilla se produce una colisión, y la tabla debe resolverla por encadenamiento (chaining) o por direccionamiento abierto (open addressing).

Puntos importantes

Define las condiciones que siempre deben cumplirse (invariantes) antes de escribir las operaciones.
Trata los casos de estructura vacía, llena y de fallo al reservar memoria.
Evalúa a la vez la complejidad y la gestión de memoria de cada operación.

Mira cómo funciona

Escribe una clave y guárdala o búscala. La clave se convierte con el hash en un número de cubeta, así que el programa va directo a la cubeta correcta.

Ejemplos de código C y C++

Ejecutar →

main.c

#include <stdio.h>
#include <string.h>

typedef struct Item {
    const char *key;
    int count;
    struct Item *next;
} Item;

unsigned hash(const char *text) {
    unsigned value = 5381;
    while (*text) {
        value = value * 33u ^ (unsigned char)*text++;
    }
    return value % 5;
}

int main(void) {
    const char *words[] = {"c", "cpp", "c"};
    Item items[2] = {{"c", 0, NULL}, {"cpp", 0, NULL}};
    Item *buckets[5] = {0};

    for (int index = 0; index < 2; ++index) {
        unsigned bucket = hash(items[index].key);
        items[index].next = buckets[bucket];
        buckets[bucket] = &items[index];
    }
    for (int index = 0; index < 3; ++index) {
        Item *item = buckets[hash(words[index])];
        for (; item; item = item->next) {
            if (strcmp(item->key, words[index]) == 0) {
                ++item->count;
                break;
            }
        }
    }
    printf("c=%d cpp=%d\n", items[0].count, items[1].count);
}

Resultado de la ejecución

c=2 cpp=1

C++

Ejecutar →

main.cpp

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

int main() {
    std::unordered_map<std::string, int> counts;
    for (const std::string word : {"c", "cpp", "c"}) {
        ++counts[word];
    }
    std::cout << "c=" << counts["c"]
              << " cpp=" << counts["cpp"] << '\n';
}

Resultado de la ejecución

c=2 cpp=1

Comparación entre C y C++

La función hash en C calcula un valor a partir de los caracteres de la cadena y luego toma el resto de dividir entre 5 para elegir uno de los 5 buckets. Cada bucket es una lista enlazada, así que las palabras que colisionan se encadenan en el mismo bucket. El ejemplo en C solo usa unas pocas palabras fijas para centrarse en el mecanismo de los buckets. En C++, std::unordered_map gestiona los nodos por sí mismo, crece cuando hace falta y acepta cualquier cadena como clave.

Los datos (struct) y las operaciones están separados, y la memoria se reserva y se libera a mano.

C++

Las clases y los contenedores protegen la coherencia de los datos y gestionan sus propios recursos.

Ejercicios de práctica

Ejecuta las dos versiones y después modifica el código para ver la diferencia de seguridad que aporta cada lenguaje.

Añade pruebas para el estado vacío y para el momento en que se alcanza la capacidad máxima.
Escribe la liberación de la memoria y comprueba que no haya fugas.
Compara la complejidad con la del contenedor equivalente de la biblioteca estándar.

Practica con un reto

Usa lo que cubre esta lección para resolver un problema real. Cada reto se ejecuta en el navegador, con pruebas al instante y una revisión de IA.

Todos los retos