Lección 12 · 12 de 20

Una tabla hash · C

Programe en C una tabla hash con encadenamiento: la función djb2, cubetas con listas enlazadas, colisiones y búsqueda de precios de bebidas.

C · Una tabla hash en DMarlon Studio: el código del ejemplo y su salida en la terminal

Una tabla hash encuentra un dato por su clave casi al instante, sin recorrerlo todo. Es un array de cubetas (table[BUCKETS]), y una función hash convierte cada clave en el número de su cubeta.

hash usa djb2: empieza en 5381 y, por cada carácter, multiplica por 33 y suma el carácter. La misma clave da siempre el mismo número, y % BUCKETS lo lleva al rango de 0 a 4. El (unsigned char) evita sorpresas con los caracteres acentuados, que en un char con signo serían negativos.

Dos claves pueden caer en la misma cubeta: es una colisión, y aquí les pasa a tea y juice, las dos en la 1. Por eso cada cubeta es una lista enlazada (el campo next): put reserva una entrada con malloc y la pone al principio de la lista de su cubeta.

get calcula la cubeta y recorre solo esa lista comparando con strcmp. Con pocas entradas por cubeta, la búsqueda es casi inmediata aunque la tabla tenga miles de claves. Si no está, como soup, devuelve NULL.

Al final se libera cada lista, cubeta por cubeta. Las claves no se liberan porque son cadenas literales, no memoria del montón.

Código · main.c

#include <stdio.h>#include <stdlib.h>#include <string.h>#define BUCKETS 5typedef struct Entry { const char *key; double price; struct Entry *next; } Entry;  // one list per bucketunsigned long hash(const char *s) {  // djb2: the same text, always the same number    unsigned long h = 5381;    while (*s) h = h * 33 + (unsigned char)*s++;    return h % BUCKETS;               // and % turns it into a bucket}unsigned long put(Entry *table[], const char *key, double price) {    unsigned long b = hash(key);    Entry *e = malloc(sizeof *e);    if (!e) exit(EXIT_FAILURE);    e->key = key; e->price = price; e->next = table[b]; table[b] = e;    return b;}Entry *get(Entry *table[], const char *key) {  // only one bucket is searched    for (Entry *e = table[hash(key)]; e; e = e->next)        if (strcmp(e->key, key) == 0) return e;    return NULL;}int main(void) {    Entry *table[BUCKETS] = {NULL};    const char *drinks[] = {"coffee", "tea", "juice", "water", "cola", "milk"};    for (int i = 0; i < 6; i++)        printf("%-7s -> bucket %lu\n", drinks[i], put(table, drinks[i], 1.10 + i * 0.35));    Entry *cola = get(table, "cola");    printf("cola costs %.2f, soup is %s\n", cola->price, get(table, "soup") ? "found" : "missing");    for (int b = 0; b < BUCKETS; b++)  // free every list        for (Entry *e = table[b], *next; e; e = next) { next = e->next; free(e); }    return 0;}

Salida · cc main.c -o main && ./main

coffee  -> bucket 3
tea     -> bucket 1
juice   -> bucket 1
water   -> bucket 2
cola    -> bucket 4
milk    -> bucket 0
cola costs 2.50, soup is missing

Para recordar

La función hash convierte la clave en el número de cubeta.
Una colisión es cuando dos claves comparten cubeta.
Con encadenamiento, cada cubeta es una lista enlazada.
Buscar solo recorre la lista de una cubeta.

Ejercicio

Haga que put busque primero la clave con get y, si ya existe, solo actualice el precio; compruébelo poniendo tea a 1.25.