Hash Table

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

#define NBUCKETS 8

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

typedef struct { Entry *buckets[NBUCKETS]; size_t count; } Map;

unsigned long hash(const char *s) {   /* djb2 by Dan Bernstein */
    unsigned long h = 5381;
    for (; *s; s++) h = h * 33 + (unsigned char)*s;
    return h;
}

void map_put(Map *m, const char *key, int value) {
    size_t i = hash(key) % NBUCKETS;
    for (Entry *e = m->buckets[i]; e; e = e->next)
        if (strcmp(e->key, key) == 0) { e->value = value; return; }   /* update */
    Entry *e = malloc(sizeof *e);
    if (!e) exit(1);
    size_t n = strlen(key) + 1;
    e->key = malloc(n);
    if (!e->key) exit(1);
    memcpy(e->key, key, n);
    e->value = value;
    e->next = m->buckets[i];          /* insert at bucket head */
    m->buckets[i] = e;
    m->count++;
}

int *map_get(Map *m, const char *key) {
    for (Entry *e = m->buckets[hash(key) % NBUCKETS]; e; e = e->next)
        if (strcmp(e->key, key) == 0) return &e->value;
    return NULL;
}

void map_free(Map *m) {
    for (int i = 0; i < NBUCKETS; i++)
        for (Entry *e = m->buckets[i], *next; e; e = next) {
            next = e->next;
            free(e->key);
            free(e);
        }
}

int main(void) {
    Map m = {0};
    const char *words[] = {"the", "cat", "sat", "on", "the", "mat", "the", "cat"};
    for (int i = 0; i < 8; i++) {
        int *c = map_get(&m, words[i]);
        if (c) (*c)++; else map_put(&m, words[i], 1);
    }
    const char *probe[] = {"the", "cat", "mat", "dog"};
    for (int i = 0; i < 4; i++) {
        int *c = map_get(&m, probe[i]);
        printf("%s: %d\n", probe[i], c ? *c : 0);
    }
    printf("distinct words: %zu\n", m.count);
    map_free(&m);
    return 0;
}

the: 3
cat: 2
mat: 1
dog: 0
distinct words: 5