Buckets and Collisions

A 32-bit hash is too big to be an array index, so the map keeps nbuckets slots and folds the hash down with modulo:

size_t index = hash % nbuckets;

Different keys will inevitably share a bucket — with 4 billion possible hashes squeezed into a handful of buckets, collisions are a certainty to design for, not an error. The simplest fix is separate chaining: each bucket holds the head of a singly linked list of entries, and colliding entries just line up behind each other.

struct hm_entry {
	char *key;
	int value;
	struct hm_entry *next;   /* next entry in the same bucket */
};

Each bucket is a chain head; colliding keys queue up behind each other. Here "ada" and "ken" both landed in bucket 1, so bucket 1's chain holds both:

Finding a key inside a bucket is a plain list walk. One subtlety: keys are strings, so the comparison is strcmp(...) == 0 — comparing char * pointers with == asks "is this the same memory?", not "is this the same text?", and will appear to work in toy tests only to fail in production.