C Tabela Hash

A lojinha da Ana tem centenas de produtos, e o caixa precisa achar o preço de "leite" na hora. Procurar um por um numa lista é lento; uma árvore de busca já ajuda. A tabela hash vai além: ela transforma o nome do produto num número, e esse número diz em que gaveta o produto está. Em vez de procurar, o programa vai direto. É a estrutura por trás dos "dicionários" do Python, dos objetos do JavaScript e de quase todo cache. Em C, você monta a sua com um array e listas ligadas.

Esta aula usa listas ligadas, funções de string (strcmp), malloc e free e inteiros de tamanho fixo. Todos os programas foram compilados com o gcc 15.2 na máquina fictícia da Ana (usuária ana, computador notebook), na pasta ~/c, com o comando padrão do guia: gcc -std=c23 -Wall -Wextra arquivo.c -o programa.

A ideia: o armário de escaninhos

No depósito da lojinha há um armário com 13 escaninhos, numerados de 0 a 12. A Ana combinou uma regra: para saber em que escaninho fica um produto, ela faz uma conta com as letras do nome, e o resultado (de 0 a 12) é o número do escaninho. Para guardar o arroz, faz a conta e põe no escaninho que deu. Para achar o arroz depois, faz a mesma conta e vai direto ao mesmo escaninho. Ela nunca precisa olhar os outros doze.

"Hash" quer dizer "picadinho" em inglês (como em hash brown, a batata ralada): a função "pica" a chave e mistura os pedaços até sair um número. A regra de ouro: a mesma chave sempre dá o mesmo número. Se a conta mudasse de um dia para outro, a Ana nunca mais acharia o arroz.

1. A primeira função hash: somar as letras

Cada letra é um número para o computador (o código dela; veja Caracteres): 'a' é 97, 'b' é 98. A conta mais simples é somar os códigos e pegar o resto da divisão pelo número de baldes, que dá sempre um número de 0 a 12:

#include <stdio.h>

#define BALDES 13

unsigned int hash(const char *s) {
    unsigned int soma = 0;
    for (int i = 0; s[i] != '\0'; i++) {
        soma += (unsigned char)s[i];
    }
    return soma;
}

int main(void) {
    const char *produtos[] = {"arroz", "cafe", "leite", "pao", "ovos", "sal", "amor", "roma"};
    for (int i = 0; i < 8; i++) {
        unsigned int h = hash(produtos[i]);
        printf("%-6s soma %3u -> balde %u\n", produtos[i], h, h % BALDES);
    }
    return 0;
}

$ gcc -std=c23 -Wall -Wextra soma_letras.c -o soma_letras
$ ./soma_letras
arroz  soma 558 -> balde 12
cafe   soma 399 -> balde 9
leite  soma 531 -> balde 11
pao    soma 320 -> balde 8
ovos   soma 455 -> balde 0
sal    soma 320 -> balde 8
amor   soma 431 -> balde 2
roma   soma 431 -> balde 2

#define BALDES 13

Quantos baldes a tabela tem. A conta final sempre cai entre 0 e BALDES - 1.

unsigned int soma = 0;

Um inteiro sem sinal: nunca fica negativo. Isso vai importar (veja Quando dá errado).

(unsigned char)s[i]

Lê o caractere como um número de 0 a 255. Sem essa conversão, letras acentuadas viram números negativos no Linux (o char lá tem sinal).

h % BALDES

O resto da divisão por 13: de 0 a 12. É o número do balde.

%-6s e %3u

Alinham a saída: o nome à esquerda em 6 colunas, o número à direita em 3 (veja Formatos do printf). O %u é o formato do unsigned int.

Funciona, mas tem dois problemas visíveis. "pao" e "sal" deram a mesma soma (320) por coincidência. E "amor" e "roma" têm as mesmas letras em outra ordem: a soma não liga para a ordem, então palavras com as mesmas letras sempre caem juntas. Um bom hash precisa misturar a posição de cada letra também.

2. Um hash de verdade: o djb2

O djb2, criado pelo programador Daniel J. Bernstein, é uma das funções hash mais simples que funcionam bem para textos. Antes de somar cada letra, ele multiplica o que já tem por 33. Assim, a mesma letra vale diferente em cada posição:

#include <stdio.h>
#include <stdint.h>

#define BALDES 13

uint32_t hash(const char *s) {
    uint32_t h = 5381;
    for (int i = 0; s[i] != '\0'; i++) {
        h = h * 33 + (unsigned char)s[i];
    }
    return h;
}

int main(void) {
    const char *produtos[] = {"arroz", "cafe", "leite", "pao", "ovos", "sal", "amor", "roma"};
    for (int i = 0; i < 8; i++) {
        uint32_t h = hash(produtos[i]);
        printf("%-6s hash %10u -> balde %u\n", produtos[i], h, h % BALDES);
    }
    return 0;
}

$ gcc -std=c23 -Wall -Wextra djb2.c -o djb2
$ ./djb2
arroz  hash  253411315 -> balde 1
cafe   hash 2090140468 -> balde 0
leite  hash  265979608 -> balde 11
pao    hash  193502277 -> balde 7
ovos   hash 2090594892 -> balde 9
sal    hash  193505541 -> balde 8
amor   hash 2090081972 -> balde 4
roma   hash 2090694996 -> balde 0

uint32_t h = 5381;

Um inteiro sem sinal de exatamente 32 bits (aula stdint.h). O 5381 é o valor inicial escolhido pelo autor; qualquer número serviria, mas este foi testado com muitos textos.

h = h * 33 + (unsigned char)s[i];

Multiplica o que já tem por 33 e soma a letra. Com "ab", fica (5381 × 33 + 97) × 33 + 98; com "ba", (5381 × 33 + 98) × 33 + 97: números diferentes.

(e quando passa de 4 bilhões?)

Com palavras de 5 ou 6 letras, o número já passa do máximo de 32 bits. Num tipo sem sinal, isso não é erro: a conta "dá a volta" e continua do zero, como um odômetro (é o comportamento definido pelo C). Num int com sinal, seria comportamento indefinido.

Agora "amor" e "roma" se separaram, e também "pao" e "sal". Mas "cafe" e "roma" caíram juntos no balde 0. Isso não é defeito do djb2: com 8 palavras e 13 baldes, a chance de nenhuma cair junto de outra é pequena (é o "paradoxo do aniversário": numa sala com só 23 pessoas, a chance de duas fazerem aniversário no mesmo dia já passa de 50%). Colisões vão acontecer; a tabela precisa saber lidar com elas.

3. Colisões: cada balde é uma lista

A solução mais comum para colisões se chama encadeamento (separate chaining): cada balde não guarda um item, mas uma lista ligada de itens. Quando dois produtos caem no mesmo balde, os dois entram na lista daquele balde. Para achar um produto, você calcula o balde e procura só naquela lista, que é curta.

4. A tabela completa: guardar, achar e liberar

Cada item é um nó de lista: a chave (o nome), o valor (o preço em centavos, para não ter problemas com float) e o ponteiro para o próximo do mesmo balde. A tabela é um array de ponteiros para o primeiro item de cada balde:

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

#define BALDES 13

typedef struct Item {
    char *chave;
    int preco;
    struct Item *prox;
} Item;

typedef struct {
    Item *baldes[BALDES];
} Tabela;

uint32_t hash(const char *s) {
    uint32_t h = 5381;
    for (int i = 0; s[i] != '\0'; i++) {
        h = h * 33 + (unsigned char)s[i];
    }
    return h;
}

Item *achar(const Tabela *t, const char *chave) {
    Item *it = t->baldes[hash(chave) % BALDES];
    while (it != NULL) {
        if (strcmp(it->chave, chave) == 0) {
            return it;
        }
        it = it->prox;
    }
    return NULL;
}

bool guardar(Tabela *t, const char *chave, int preco) {
    Item *it = achar(t, chave);
    if (it != NULL) {
        it->preco = preco;
        return true;
    }
    it = malloc(sizeof *it);
    if (it == NULL) {
        return false;
    }
    it->chave = strdup(chave);
    if (it->chave == NULL) {
        free(it);
        return false;
    }
    it->preco = preco;
    uint32_t b = hash(chave) % BALDES;
    it->prox = t->baldes[b];
    t->baldes[b] = it;
    return true;
}

void liberar(Tabela *t) {
    for (int b = 0; b < BALDES; b++) {
        Item *it = t->baldes[b];
        while (it != NULL) {
            Item *prox = it->prox;
            free(it->chave);
            free(it);
            it = prox;
        }
        t->baldes[b] = NULL;
    }
}

void mostrar(const Tabela *t) {
    for (int b = 0; b < BALDES; b++) {
        printf("balde %2d:", b);
        for (const Item *it = t->baldes[b]; it != NULL; it = it->prox) {
            printf(" %s=%d", it->chave, it->preco);
        }
        printf("\n");
    }
}

int main(void) {
    Tabela loja = {0};
    const char *nomes[] = {"arroz", "cafe", "leite", "pao", "ovos", "sal", "feijao", "queijo"};
    int precos[] = {2590, 1890, 549, 75, 1399, 350, 899, 4290};
    for (int i = 0; i < 8; i++) {
        if (!guardar(&loja, nomes[i], precos[i])) {
            fprintf(stderr, "Sem memória\n");
            liberar(&loja);
            return 1;
        }
    }
    guardar(&loja, "leite", 599);
    mostrar(&loja);

    const char *procurar[] = {"leite", "queijo", "acucar"};
    for (int i = 0; i < 3; i++) {
        Item *it = achar(&loja, procurar[i]);
        if (it != NULL) {
            printf("%s custa R$ %d,%02d\n", procurar[i], it->preco / 100, it->preco % 100);
        } else {
            printf("%s: não temos\n", procurar[i]);
        }
    }
    liberar(&loja);
    return 0;
}

$ gcc -std=c23 -Wall -Wextra -g tabela.c -o tabela
$ ./tabela
balde  0: cafe=1890
balde  1: queijo=4290 arroz=2590
balde  2:
balde  3:
balde  4:
balde  5:
balde  6:
balde  7: pao=75
balde  8: sal=350
balde  9: ovos=1399
balde 10:
balde 11: feijao=899 leite=599
balde 12:
leite custa R$ 5,99
queijo custa R$ 42,90
acucar: não temos
$ valgrind --leak-check=full ./tabela 2>&1 | grep -E 'total heap|All heap|ERROR SUM'
==429526==   total heap usage: 17 allocs, 17 frees, 4,332 bytes allocated
==429526== All heap blocks were freed -- no leaks are possible
==429526== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Quanto custa achar um produto? Calcular o hash (umas poucas contas por letra) e andar por uma lista de um ou dois itens. Com 8 produtos ou com 8 milhões, se a tabela tiver baldes suficientes, o trabalho é praticamente o mesmo. Essa é a grande vantagem sobre a lista (que olha tudo) e a árvore (que olha a altura).

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

#define BALDES 13

typedef struct Item {
    char *chave;
    int preco;
    struct Item *prox;
} Item;

typedef struct {
    Item *baldes[BALDES];
} Tabela;

uint32_t hash(const char *s) {
    uint32_t h = 5381;
    for (int i = 0; s[i] != '\0'; i++) {
        h = h * 33 + (unsigned char)s[i];
    }
    return h;
}

Item *achar(const Tabela *t, const char *chave) {
    Item *it = t->baldes[hash(chave) % BALDES];
    while (it != NULL) {
        if (strcmp(it->chave, chave) == 0) {
            return it;
        }
        it = it->prox;
    }
    return NULL;
}

bool guardar(Tabela *t, const char *chave, int preco) {
    Item *it = achar(t, chave);
    if (it != NULL) {
        it->preco = preco;
        return true;
    }
    it = malloc(sizeof *it);
    if (it == NULL) {
        return false;
    }
    it->chave = strdup(chave);
    if (it->chave == NULL) {
        free(it);
        return false;
    }
    it->preco = preco;
    uint32_t b = hash(chave) % BALDES;
    it->prox = t->baldes[b];
    t->baldes[b] = it;
    return true;
}

void liberar(Tabela *t) {
    for (int b = 0; b < BALDES; b++) {
        Item *it = t->baldes[b];
        while (it != NULL) {
            Item *prox = it->prox;
            free(it->chave);
            free(it);
            it = prox;
        }
        t->baldes[b] = NULL;
    }
}

void mostrar(const Tabela *t) {
    for (int b = 0; b < BALDES; b++) {
        printf("balde %2d:", b);
        for (const Item *it = t->baldes[b]; it != NULL; it = it->prox) {
            printf(" %s=%d", it->chave, it->preco);
        }
        printf("\n");
    }
}

int main(void) {
    Tabela loja = {0};
    const char *nomes[] = {"arroz", "cafe", "leite", "pao", "ovos", "sal", "feijao", "queijo"};
    int precos[] = {2590, 1890, 549, 75, 1399, 350, 899, 4290};
    for (int i = 0; i < 8; i++) {
        if (!guardar(&loja, nomes[i], precos[i])) {
            fprintf(stderr, "Sem memória\n");
            liberar(&loja);
            return 1;
        }
    }
    guardar(&loja, "leite", 599);
    mostrar(&loja);

    const char *procurar[] = {"leite", "queijo", "acucar"};
    for (int i = 0; i < 3; i++) {
        Item *it = achar(&loja, procurar[i]);
        if (it != NULL) {
            printf("%s custa R$ %d,%02d\n", procurar[i], it->preco / 100, it->preco % 100);
        } else {
            printf("%s: não temos\n", procurar[i]);
        }
    }
    liberar(&loja);
    return 0;
}

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

#define BALDES 13

typedef struct Item {
    char *chave;
    int preco;
    struct Item *prox;
} Item;

typedef struct {
    Item *baldes[BALDES];
} Tabela;

uint32_t hash(const char *s) {
    uint32_t h = 5381;
    for (int i = 0; s[i] != '\0'; i++) {
        h = h * 33 + (unsigned char)s[i];
    }
    return h;
}

Item *achar(const Tabela *t, const char *chave) {
    Item *it = t->baldes[hash(chave) % BALDES];
    while (it != NULL) {
        if (strcmp(it->chave, chave) == 0) {
            return it;
        }
        it = it->prox;
    }
    return NULL;
}

bool guardar(Tabela *t, const char *chave, int preco) {
    Item *it = achar(t, chave);
    if (it != NULL) {
        it->preco = preco;
        return true;
    }
    it = malloc(sizeof *it);
    if (it == NULL) {
        return false;
    }
    it->chave = strdup(chave);
    if (it->chave == NULL) {
        free(it);
        return false;
    }
    it->preco = preco;
    uint32_t b = hash(chave) % BALDES;
    it->prox = t->baldes[b];
    t->baldes[b] = it;
    return true;
}

void liberar(Tabela *t) {
    for (int b = 0; b < BALDES; b++) {
        Item *it = t->baldes[b];
        while (it != NULL) {
            Item *prox = it->prox;
            free(it->chave);
            free(it);
            it = prox;
        }
        t->baldes[b] = NULL;
    }
}

void mostrar(const Tabela *t) {
    for (int b = 0; b < BALDES; b++) {
        printf("balde %2d:", b);
        for (const Item *it = t->baldes[b]; it != NULL; it = it->prox) {
            printf(" %s=%d", it->chave, it->preco);
        }
        printf("\n");
    }
}

int main(void) {
    Tabela loja = {0};
    const char *nomes[] = {"arroz", "cafe", "leite", "pao", "ovos", "sal", "feijao", "queijo"};
    int precos[] = {2590, 1890, 549, 75, 1399, 350, 899, 4290};
    for (int i = 0; i < 8; i++) {
        if (!guardar(&loja, nomes[i], precos[i])) {
            fprintf(stderr, "Sem memória\n");
            liberar(&loja);
            return 1;
        }
    }
    guardar(&loja, "leite", 599);
    guardar(&loja, "acucar", 489);
    mostrar(&loja);

    const char *procurar[] = {"leite", "queijo", "acucar"};
    for (int i = 0; i < 3; i++) {
        Item *it = achar(&loja, procurar[i]);
        if (it != NULL) {
            printf("%s custa R$ %d,%02d\n", procurar[i], it->preco / 100, it->preco % 100);
        } else {
            printf("%s: não temos\n", procurar[i]);
        }
    }
    liberar(&loja);
    return 0;
}

5. Fator de carga: quando a tabela lota

A conta "quantos itens por balde, em média" tem nome: fator de carga (load factor) = itens ÷ baldes. Se ele cresce, as listas crescem, e a tabela vira um monte de listas ligadas lentas. Este programa coloca 1000 chaves (produto0, produto1…) em tabelas de tamanhos diferentes e mede o resultado:

#include <stdio.h>
#include <stdint.h>

uint32_t hash(const char *s) {
    uint32_t h = 5381;
    for (int i = 0; s[i] != '\0'; i++) {
        h = h * 33 + (unsigned char)s[i];
    }
    return h;
}

int main(void) {
    const int itens = 1000;
    const int tamanhos[] = {13, 101, 1009, 2003};
    for (int k = 0; k < 4; k++) {
        int nb = tamanhos[k];
        int contagem[2003] = {0};
        char chave[20];
        for (int i = 0; i < itens; i++) {
            snprintf(chave, sizeof chave, "produto%d", i);
            contagem[hash(chave) % (uint32_t)nb]++;
        }
        int maior = 0, vazios = 0;
        for (int b = 0; b < nb; b++) {
            if (contagem[b] > maior) {
                maior = contagem[b];
            }
            if (contagem[b] == 0) {
                vazios++;
            }
        }
        printf("%4d baldes: carga %5.2f, maior balde %3d, baldes vazios %4d\n",
               nb, (double)itens / nb, maior, vazios);
    }
    return 0;
}

$ gcc -std=c23 -Wall -Wextra carga.c -o carga
$ ./carga
  13 baldes: carga 76.92, maior balde  79, baldes vazios    0
 101 baldes: carga  9.90, maior balde  15, baldes vazios    0
1009 baldes: carga  0.99, maior balde   3, baldes vazios  254
2003 baldes: carga  0.50, maior balde   2, baldes vazios 1069

Com 13 baldes, há quase 77 itens por balde, e o pior balde tem 79: achar um produto ali é quase tão lento quanto numa lista. Com cerca de um balde por item (1009), o pior balde tem só 3 itens. Mais baldes ainda (2003) gastam memória com baldes vazios e quase não melhoram. A regra prática: mantenha o fator de carga perto de 1 ou abaixo. (O (uint32_t)nb converte o número de baldes para o mesmo tipo do hash antes do %, para a conta ser feita sem sinal.)

Crescer: dobrar os baldes e redistribuir

Quando você não sabe quantos itens vão chegar, a tabela começa pequena e cresce: quando o fator de carga passa de um limite, ela reserva o dobro de baldes e passa cada item para o balde novo dele (em inglês, rehash). Os itens precisam mudar de balde porque o % nb mudou:

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

typedef struct Item {
    char chave[20];
    struct Item *prox;
} Item;

typedef struct {
    Item **baldes;
    size_t nb;
    size_t qtd;
} Tabela;

uint32_t hash(const char *s) {
    uint32_t h = 5381;
    for (int i = 0; s[i] != '\0'; i++) {
        h = h * 33 + (unsigned char)s[i];
    }
    return h;
}

bool crescer(Tabela *t) {
    size_t novo_nb = t->nb * 2;
    Item **novos = calloc(novo_nb, sizeof *novos);
    if (novos == NULL) {
        return false;
    }
    for (size_t b = 0; b < t->nb; b++) {
        Item *it = t->baldes[b];
        while (it != NULL) {
            Item *prox = it->prox;
            size_t destino = hash(it->chave) % novo_nb;
            it->prox = novos[destino];
            novos[destino] = it;
            it = prox;
        }
    }
    free(t->baldes);
    t->baldes = novos;
    t->nb = novo_nb;
    return true;
}

bool guardar(Tabela *t, const char *chave) {
    if (t->qtd + 1 > t->nb) {
        printf("  %zu itens em %zu baldes: crescendo para %zu\n", t->qtd, t->nb, t->nb * 2);
        if (!crescer(t)) {
            return false;
        }
    }
    Item *it = malloc(sizeof *it);
    if (it == NULL) {
        return false;
    }
    snprintf(it->chave, sizeof it->chave, "%s", chave);
    size_t b = hash(chave) % t->nb;
    it->prox = t->baldes[b];
    t->baldes[b] = it;
    t->qtd++;
    return true;
}

void liberar(Tabela *t) {
    for (size_t b = 0; b < t->nb; b++) {
        Item *it = t->baldes[b];
        while (it != NULL) {
            Item *prox = it->prox;
            free(it);
            it = prox;
        }
    }
    free(t->baldes);
}

int main(void) {
    Tabela t = {calloc(4, sizeof(Item *)), 4, 0};
    if (t.baldes == NULL) {
        return 1;
    }
    char chave[20];
    for (int i = 0; i < 20; i++) {
        snprintf(chave, sizeof chave, "produto%d", i);
        if (!guardar(&t, chave)) {
            fprintf(stderr, "Sem memória\n");
            liberar(&t);
            return 1;
        }
    }
    printf("Final: %zu itens em %zu baldes\n", t.qtd, t.nb);
    liberar(&t);
    return 0;
}

$ gcc -std=c23 -Wall -Wextra crescer.c -o crescer
$ ./crescer
  4 itens em 4 baldes: crescendo para 8
  8 itens em 8 baldes: crescendo para 16
  16 itens em 16 baldes: crescendo para 32
Final: 20 itens em 32 baldes

Item **baldes; size_t nb;

Agora o array de baldes mora no heap e tem tamanho variável, como o array que cresce. nb é o número de baldes; qtd, o de itens.

calloc(novo_nb, sizeof *novos)

Reserva o array novo já zerado: todos os baldes começam NULL (aula calloc e realloc).

size_t destino = hash(it->chave) % novo_nb;

O balde de cada item na tabela nova. Repare que o hash é o mesmo; só o resto da divisão muda.

it->prox = novos[destino]; novos[destino] = it;

Os nós não são copiados: os mesmos nós são pendurados nas listas novas. Só os ponteiros mudam.

free(t->baldes);

Libera o array velho de baldes (não os itens, que agora estão no novo).

if (t->qtd + 1 > t->nb)

O limite escolhido aqui: crescer quando o item novo deixaria a carga acima de 1. Bibliotecas de verdade usam limites como 0,75.

Crescer dá trabalho (passar por todos os itens), mas, como a tabela dobra, isso acontece cada vez mais raramente: para chegar a um milhão de itens, começando com 4 baldes, ela cresce só 18 vezes.

Formas diferentes

Sondagem linear: sem listas, procurando a próxima vaga

Outra forma de lidar com colisões é o endereçamento aberto (open addressing): cada vaga do array guarda um item, e, se a vaga calculada estiver ocupada, o item vai para a próxima livre. A versão mais simples se chama sondagem linear (linear probing): tenta a vaga seguinte, depois a outra, dando a volta no fim do array com o %, como na fila circular.

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

#define VAGAS 13

typedef struct {
    const char *chave;
    int preco;
} Vaga;

uint32_t hash(const char *s) {
    uint32_t h = 5381;
    for (int i = 0; s[i] != '\0'; i++) {
        h = h * 33 + (unsigned char)s[i];
    }
    return h;
}

bool guardar(Vaga t[], const char *chave, int preco) {
    uint32_t i = hash(chave) % VAGAS;
    for (int tentativas = 0; tentativas < VAGAS; tentativas++) {
        if (t[i].chave == NULL || strcmp(t[i].chave, chave) == 0) {
            t[i].chave = chave;
            t[i].preco = preco;
            printf("%-6s queria a vaga %2u, ficou na %2u\n", chave, hash(chave) % VAGAS, i);
            return true;
        }
        i = (i + 1) % VAGAS;
    }
    return false;
}

const Vaga *achar(const Vaga t[], const char *chave) {
    uint32_t i = hash(chave) % VAGAS;
    for (int tentativas = 0; tentativas < VAGAS; tentativas++) {
        if (t[i].chave == NULL) {
            return NULL;
        }
        if (strcmp(t[i].chave, chave) == 0) {
            return &t[i];
        }
        i = (i + 1) % VAGAS;
    }
    return NULL;
}

int main(void) {
    Vaga loja[VAGAS] = {0};
    const char *nomes[] = {"arroz", "cafe", "leite", "pao", "ovos", "sal", "feijao", "queijo"};
    int precos[] = {2590, 1890, 549, 75, 1399, 350, 899, 4290};
    for (int i = 0; i < 8; i++) {
        guardar(loja, nomes[i], precos[i]);
    }
    const Vaga *v = achar(loja, "queijo");
    if (v != NULL) {
        printf("queijo custa %d centavos\n", v->preco);
    }
    return 0;
}

$ gcc -std=c23 -Wall -Wextra sondagem.c -o sondagem
$ ./sondagem
arroz  queria a vaga  1, ficou na  1
cafe   queria a vaga  0, ficou na  0
leite  queria a vaga 11, ficou na 11
pao    queria a vaga  7, ficou na  7
ovos   queria a vaga  9, ficou na  9
sal    queria a vaga  8, ficou na  8
feijao queria a vaga 11, ficou na 12
queijo queria a vaga  1, ficou na  2
queijo custa 4290 centavos

Vaga loja[VAGAS] = {0};

Um array de structs, sem malloc. Uma vaga com chave == NULL está livre. Aqui as chaves são textos fixos do programa, que existem até o fim; por isso não precisam de cópia.

i = (i + 1) % VAGAS;

Vaga ocupada por outra chave: tenta a seguinte. O "feijao" queria a 11 (do leite) e ficou na 12; o "queijo" queria a 1 (do arroz) e ficou na 2.

if (t[i].chave == NULL) return NULL;

Em achar: se chegou a uma vaga vazia sem encontrar a chave, ela não está na tabela (se estivesse, teria parado antes daquela vaga).

tentativas < VAGAS

Nunca dá mais que uma volta completa: com a tabela cheia, guardar devolve false em vez de rodar para sempre.

A sondagem tem um preço escondido: remover é complicado. Se você esvaziar a vaga do "arroz", a busca pelo "queijo" (que está depois dela) vai parar na vaga vazia e dizer que ele não existe. As implementações de verdade marcam a vaga removida com uma "lápide" (tombstone) em vez de esvaziá-la.

Qual usar

Tabela hash, árvore ou array ordenado?

• Achar pela chave exata ("qual o preço do leite?"), com muitos itens: tabela hash.
• Precisa da ordem (listar em ordem alfabética, o menor, o maior, "todos entre B e D"): árvore de busca, ou um array ordenado. A tabela hash espalha as chaves de propósito: a ordem dos baldes não quer dizer nada.
• Dados que quase não mudam: um array ordenado com qsort e procurado com bsearch é o mais simples.
• Poucos itens (algumas dezenas): um array e um for. Ninguém vai notar a diferença.

Quando dá errado

#include <stdio.h>

#define BALDES 13

int hash(const char *s) {
    int h = 0;
    for (int i = 0; s[i] != '\0'; i++) {
        h = h * 31 + s[i];
    }
    return h % BALDES;
}

int main(void) {
    int contagem[BALDES] = {0};
    const char *frutas[] = {"uva", "kiwi", "maçã", "melão"};
    for (int i = 0; i < 4; i++) {
        int b = hash(frutas[i]);
        printf("%s -> balde %d\n", frutas[i], b);
        contagem[b]++;
    }
    return 0;
}

$ gcc -std=c23 -Wall -Wextra negativo.c -o negativo
$ ./negativo
uva -> balde 11
kiwi -> balde 8
maçã -> balde -8
melão -> balde -1

$ gcc -std=c23 -Wall -Wextra -g -fsanitize=address,undefined negativo.c -o negativo
$ ./negativo
uva -> balde 11
kiwi -> balde 8
negativo.c:8:15: runtime error: signed integer overflow: 103492075 * 31 cannot be represented in type 'int'
maçã -> balde -8
negativo.c:19:17: runtime error: index -8 out of bounds for type 'int [13]'
=================================================================
==432907==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7bde120f0040 at pc 0x555651571a58 bp 0x7ffe1bcd1db0 sp 0x7ffe1bcd1da0
READ of size 4 at 0x7bde120f0040 thread T0
    #0 0x555651571a57 in main /home/ana/c/negativo.c:19
«  (… mais linhas: o mapa da memória em volta do erro …)

Item *achar(Item *baldes[], const char *chave) {
    for (Item *it = baldes[hash(chave) % BALDES]; it != NULL; it = it->prox) {
        if (it->chave == chave) {        // compara endereços, não textos
            return it;
        }
    }
    return NULL;
}
…
    Item leite = {strdup("leite"), 599, NULL};
    baldes[hash("leite") % BALDES] = &leite;
    Item *it = achar(baldes, "leite");

$ gcc -std=c23 -Wall -Wextra erro_igual.c -o erro_igual
$ ./erro_igual
leite: não temos

    char nome[20];
    int preco;
    while (scanf("%19s %d", nome, &preco) == 2) {
        guardar(baldes, nome, preco);     // guarda o endereço de nome
    }

$ gcc -std=c23 -Wall -Wextra sem_copia.c -o sem_copia
$ printf 'arroz 2590\ncafe 1890\nleite 599\n' | ./sem_copia
balde  0: leite=1890
balde  1: leite=2590
balde 11: leite=599
arroz: não temos

Referência rápida

Exercícios

Missão final: contar as palavras

o: 2
rato: 2
rei: 2
roma: 1
gato: 0

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

#define BALDES 13

typedef struct Item {
    char *palavra;
    int vezes;
    struct Item *prox;
} Item;

typedef struct {
    Item *baldes[BALDES];
} Tabela;

uint32_t hash(const char *s) {
    uint32_t h = 5381;
    for (int i = 0; s[i] != '\0'; i++) {
        h = h * 33 + (unsigned char)s[i];
    }
    return h;
}

Item *achar(const Tabela *t, const char *palavra) {
    for (Item *it = t->baldes[hash(palavra) % BALDES]; it != NULL; it = it->prox) {
        if (strcmp(it->palavra, palavra) == 0) {
            return it;
        }
    }
    return NULL;
}

bool contar(Tabela *t, const char *palavra) {
    Item *it = achar(t, palavra);
    // COMPLETE:
    // 1. se achou (it != NULL), some 1 em it->vezes e devolva true;
    // 2. senão, reserve um Item com malloc, copie a palavra com strdup,
    //    comece vezes em 1 e pendure o item no começo do balde
    //    hash(palavra) % BALDES (confira os dois retornos: NULL = sem memória).
    (void)it;
    return true;
}

int vezes(const Tabela *t, const char *palavra) {
    Item *it = achar(t, palavra);
    return it != NULL ? it->vezes : 0;
}

void liberar(Tabela *t) {
    for (int b = 0; b < BALDES; b++) {
        Item *it = t->baldes[b];
        while (it != NULL) {
            Item *prox = it->prox;
            free(it->palavra);
            free(it);
            it = prox;
        }
    }
}

int main(void) {
    char texto[] = "o rato roeu a roupa do rei de roma e o rei riu do rato";
    Tabela t = {0};
    for (char *p = strtok(texto, " "); p != NULL; p = strtok(NULL, " ")) {
        if (!contar(&t, p)) {
            fprintf(stderr, "Sem memória\n");
            liberar(&t);
            return 1;
        }
    }
    const char *perguntas[] = {"o", "rato", "rei", "roma", "gato"};
    for (int i = 0; i < 5; i++) {
        printf("%s: %d\n", perguntas[i], vezes(&t, perguntas[i]));
    }
    liberar(&t);
    return 0;
}

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

#define BALDES 13

typedef struct Item {
    char *palavra;
    int vezes;
    struct Item *prox;
} Item;

typedef struct {
    Item *baldes[BALDES];
} Tabela;

uint32_t hash(const char *s) {
    uint32_t h = 5381;
    for (int i = 0; s[i] != '\0'; i++) {
        h = h * 33 + (unsigned char)s[i];
    }
    return h;
}

Item *achar(const Tabela *t, const char *palavra) {
    for (Item *it = t->baldes[hash(palavra) % BALDES]; it != NULL; it = it->prox) {
        if (strcmp(it->palavra, palavra) == 0) {
            return it;
        }
    }
    return NULL;
}

bool contar(Tabela *t, const char *palavra) {
    Item *it = achar(t, palavra);
    if (it != NULL) {
        it->vezes++;
        return true;
    }
    it = malloc(sizeof *it);
    if (it == NULL) {
        return false;
    }
    it->palavra = strdup(palavra);
    if (it->palavra == NULL) {
        free(it);
        return false;
    }
    it->vezes = 1;
    uint32_t b = hash(palavra) % BALDES;
    it->prox = t->baldes[b];
    t->baldes[b] = it;
    return true;
}

int vezes(const Tabela *t, const char *palavra) {
    Item *it = achar(t, palavra);
    return it != NULL ? it->vezes : 0;
}

void liberar(Tabela *t) {
    for (int b = 0; b < BALDES; b++) {
        Item *it = t->baldes[b];
        while (it != NULL) {
            Item *prox = it->prox;
            free(it->palavra);
            free(it);
            it = prox;
        }
    }
}

int main(void) {
    char texto[] = "o rato roeu a roupa do rei de roma e o rei riu do rato";
    Tabela t = {0};
    for (char *p = strtok(texto, " "); p != NULL; p = strtok(NULL, " ")) {
        if (!contar(&t, p)) {
            fprintf(stderr, "Sem memória\n");
            liberar(&t);
            return 1;
        }
    }
    const char *perguntas[] = {"o", "rato", "rei", "roma", "gato"};
    for (int i = 0; i < 5; i++) {
        printf("%s: %d\n", perguntas[i], vezes(&t, perguntas[i]));
    }
    liberar(&t);
    return 0;
}

Com um texto do tamanho de um livro, o programa é o mesmo: só a tabela precisa de mais baldes (ou crescer sozinha, como na seção 5). É assim que funcionam os contadores de palavras, os índices de busca e os "mais vendidos" da lojinha.

Resumo

• Uma tabela hash guarda pares chave → valor num array de baldes. A função hash transforma a chave num número, e hash % BALDES diz o balde. A mesma chave sempre dá o mesmo balde.
• Somar as letras é um hash ruim (ignora a ordem). O djb2 (h = h * 33 + c, começando em 5381) é simples e bom. Use uint32_t e (unsigned char): sem sinal, nunca dá balde negativo, e o resultado é igual em qualquer computador.
• Colisões sempre acontecem. No encadeamento, cada balde é uma lista ligada; na sondagem linear, o item vai para a próxima vaga livre.
• Compare chaves com strcmp, nunca com ==. Guarde uma cópia da chave (strdup, C23) e libere-a junto com o item.
• Mantenha o fator de carga (itens ÷ baldes) perto de 1; quando passar, cresça: dobre os baldes e redistribua os itens.
• Hash é para achar pela chave exata. Para ordem, use árvore ou ordenação.