Count the words of a sentence in a table of eight buckets. Watch where two different words that land in the same bucket go, and how a lookup for a missing word ends.
Where colliding keys go
Counting the words of a sentence in eight chained buckets
#define M 8 #ifndef WORDS#define WORDS 13#endif struct entry { const char *key; int count; struct entry *next;}; struct table { struct entry *bucket[M];}; void put(struct table *t, const char *key){ uint32_t b = fnv1a(key) % M; for (struct entry *e = t->bucket[b]; e != NULL; e = e->next) { if (strcmp(e->key, key) == 0) { e->count++; return; } } struct entry *e = malloc(sizeof *e); if (e == NULL) exit(1); e->key = key; e->count = 1; e->next = t->bucket[b]; t->bucket[b] = e;} int get(const struct table *t, const char *key){ uint32_t b = fnv1a(key) % M; for (const struct entry *e = t->bucket[b]; e != NULL; e = e->next) if (strcmp(e->key, key) == 0) return e->count; return 0;} int main(void){ const char *text[13] = { "the", "cat", "sat", "on", "the", "mat", "and", "the", "dog", "sat", "on", "the", "log" }; struct table t = { { NULL } }; for (int i = 0; i < WORDS; i++) put(&t, text[i]); int a = get(&t, "the"); int b = get(&t, "sat"); int c = get(&t, "fox"); printf("the %d, sat %d, fox %d\n", a, b, c); for (int k = 0; k < M; k++) { struct entry *e = t.bucket[k]; while (e != NULL) { struct entry *next = e->next; free(e); e = next; } } return 0;}main has started: the sentence and an empty table.
- words put
- 0
- keys
- 0
- α
- 0
Output
Describe this picture
Eight bucket heads in a column, numbered 0 to 7, under the name struct entry *bucket[8], with the code beside them, the line about to run marked. The clip takes about 32 seconds. The thirteen words of “the cat sat on the mat and the dog sat on the log” are put one by one. A new word flies in from a line over the table that shows its hash and bucket, such as “the”: 3020861980 % 8 = 4, and attaches at the front of its bucket’s chain: “sat” goes in front of “cat” in bucket 7, “log” in front of “dog” in bucket 1. A word already in the table lights its entry instead, and its count rises: “the ×2”. At the end bucket 0 holds on ×2, bucket 1 log and dog, bucket 4 the ×4, bucket 5 mat, bucket 6 and, bucket 7 sat ×2 and cat; buckets 2 and 3 are empty. Then “fox” is looked up: bucket 6 lights, its one entry, “and”, is marked, and the lookup finds nothing. Last, main frees every entry, and each greys as it goes. Under the picture are one sentence on the current step and the readouts “words put”, “keys” and “α”, which ends at 1. After the clip, the slider “Words put” sets how many words are put, from 1 to 13, and replays from the last of them. The transport plays and pauses, steps one beat back or forward, and scrubs; the number of words and a paused step are kept in the page address as chaining.words and chaining.step.
A chain per bucket
A hash function sends a key to a bucket, and collisions are certain. Chaining handles them in the simplest way: each bucket holds a linked list of every key that hashes there.
To put a key, hash it, walk its bucket’s chain, and if the key is there, update it (here, raise its count). If not, make a new entry and push it on the front of the chain, which takes one step whatever the chain’s length. To get a key, hash it and walk the same chain.
The code and its cost
struct entry {
const char *key;
int count;
struct entry *next;
};
struct table {
struct entry *bucket[M];
};
void put(struct table *t, const char *key)
{
uint32_t b = fnv1a(key) % M;
for (struct entry *e = t->bucket[b]; e != NULL; e = e->next) {
if (strcmp(e->key, key) == 0) {
e->count++;
return;
}
}
struct entry *e = malloc(sizeof *e);
if (e == NULL)
exit(1);
e->key = key;
e->count = 1;
e->next = t->bucket[b];
t->bucket[b] = e;
}
int get(const struct table *t, const char *key)
{
uint32_t b = fnv1a(key) % M;
for (const struct entry *e = t->bucket[b]; e != NULL; e = e->next)
if (strcmp(e->key, key) == 0)
return e->count;
return 0;
}The keys are compared with strcmp, not ==: two different pointers can hold the same word. An entry is 24 bytes: the key pointer, the count, 4 bytes of padding, and the next pointer. With M 8, fnv1a from the last lesson, and the thirteen words, the program prints the 4, sat 2, fox 0.
The load factor
With n keys in m buckets, the load factor is
The sentence has 8 different words in 8 buckets, so α = 1. If the hash spreads keys evenly, a chain holds α keys on average. A lookup computes the hash, then walks one chain, so it costs O(1 + α): the 1 for the hash and the bucket, the α for the chain.
As long as α stays near a constant, a lookup takes constant time on average. The next lessons keep it there by growing the table when α gets too large.
The worst case
A lookup is not always one step. If every key lands in the same bucket, the table is a single linked list of n keys, and a lookup costs O(n). A poor hash or keys chosen against the hash can cause it. Even with a good hash, the chains are uneven: with 8 keys in 8 buckets, the sentence fills six buckets, two with two keys each, and leaves two empty.
Worked example
1,000 keys in 1,000 buckets. α = 1, so the average chain holds one key. Not every bucket gets one: a bucket stays empty with probability (1 − 1/1000)¹⁰⁰⁰ ≈ e⁻¹, so about 36.8 % of the buckets are empty, and the keys pile up in the rest.
1,000 keys in 10 buckets. α = 100, so the chains hold about 100 keys each. Finding a key at position p of its chain costs p comparisons, so on average (1 + 2 + … + 100)/100 = 50.5 comparisons. The table is ten linked lists, each a hundred long.
All keys in one bucket. The table is a linked list, and every lookup walks it.
Two checks. What is α after the first 7 words? (6 different words in 8 buckets: 0.75.) What does get return for a key that was never put? (0.)
Where it’s used
Compilers’ symbol tables, which find each name’s declaration as they read the code.
Dictionaries and sets in scripting languages, many of which chain.
Caches that map a key to a stored result, and counting words, as here.
Reference card
| Code or idea | Meaning |
|---|---|
fnv1a(key) % M | the key’s bucket |
| a chain | a linked list per bucket |
| put | walk the chain; update, or push a new entry on the front |
| get | walk the chain; the value, or 0 |
| α = n/m | load factor: keys over buckets |
| a lookup | O(1 + α) on average |
| worst case | every key in one chain: O(n) |
Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, struct entry 24, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.