Hash tables

/* djb2, a simple, well-known string hash by Daniel J. Bernstein */
unsigned long hash_str(const char *s) {
    unsigned long h = 5381;
    int c;
    while ((c = (unsigned char) *s++) != 0) {
        h = h * 33 + (unsigned long) c;      /* often written ((h << 5) + h) + c */
    }
    return h;
}
size_t bucket = hash_str("Pune") % NBUCKETS;

#define NBUCKETS 64

typedef struct Entry {
    char key[32];
    int value;
    struct Entry *next;          /* other entries in the same bucket */
} Entry;

Entry *table[NBUCKETS];          /* all NULL at start (static/global storage) */

buckets:
[0]  NULL
[1]  ──► ["Pune" | 411] ──► ["Goa" | 403] ──► NULL     (a collision: both hashed to 1)
[2]  NULL
[3]  ──► ["Delhi" | 110] ──► NULL
…

int ht_put(const char *key, int value) {
    size_t b = hash_str(key) % NBUCKETS;
    for (Entry *e = table[b]; e; e = e->next) {
        if (strcmp(e->key, key) == 0) { e->value = value; return 0; }   /* update */
    }
    Entry *e = malloc(sizeof *e);
    if (!e) return -1;
    snprintf(e->key, sizeof e->key, "%s", key);
    e->value = value;
    e->next = table[b];          /* insert at the head of the bucket's list */
    table[b] = e;
    return 0;
}

int ht_get(const char *key, int *out) {
    size_t b = hash_str(key) % NBUCKETS;
    for (Entry *e = table[b]; e; e = e->next) {
        if (strcmp(e->key, key) == 0) { *out = e->value; return 1; }
    }
    return 0;                    /* not found */
}