typestar

Una tabla hash con encadenamiento en C

Un arreglo de buckets con nodos enlazados: hashear a un bucket y recorrer su cadena corta.

#include <stdlib.h>
#include <string.h>

#define BUCKETS 16

typedef struct Entry {
    char *key;
    int value;
    struct Entry *next;
} Entry;

static size_t hash(const char *key) {
    size_t h = 5381;
    for (const char *p = key; *p; p++) {
        h = h * 33u + (unsigned char) *p;
    }
    return h % BUCKETS;
}

static char *copy_key(const char *key) {
    size_t n = strlen(key) + 1;
    char *copy = malloc(n);
    if (copy != NULL) {
        memcpy(copy, key, n);
    }
    return copy;
}

int table_put(Entry **buckets, const char *key, int value) {
    size_t slot = hash(key);
    for (Entry *e = buckets[slot]; e != NULL; e = e->next) {
        if (strcmp(e->key, key) == 0) {
            e->value = value;
            return 1;
        }
    }
    Entry *entry = malloc(sizeof *entry);
    if (entry == NULL) {
        return 0;
    }
    entry->key = copy_key(key);
    if (entry->key == NULL) {
        free(entry);
        return 0;
    }
    entry->value = value;
    entry->next = buckets[slot];
    buckets[slot] = entry;
    return 1;
}

int table_get(Entry **buckets, const char *key, int *out) {
    for (Entry *e = buckets[hash(key)]; e != NULL; e = e->next) {
        if (strcmp(e->key, key) == 0) {
            *out = e->value;
            return 1;
        }
    }
    return 0;
}

Cómo funciona

  1. El hash se reduce módulo el número de buckets.
  2. Las colisiones conviven en una misma cadena.
  3. strdup es POSIX, así que ISO C copia la clave a mano.

Palabras clave y builtins usados aquí

El intento, en números

Líneas
60
Caracteres a escribir
1080
Tokens
367
Ritmo de tres estrellas
105 tpm

Al ritmo de tres estrellas de 105 tokens por minuto, este intento toma unos 210 segundos.

Escribe este fragmento

Paso 3 de 4 en Árboles, tablas y heaps; paso 13 de 20 en Estructuras de datos y algoritmos.

← Anterior Siguiente →