Lesson 12 · 12 of 20

A hash table · C

Program a hash table with chaining in C: the djb2 function, buckets holding linked lists, collisions and looking up drink prices.

C · A hash table in DMarlon Studio: the example's code and its output in the terminal

A hash table finds an item by its key almost instantly, without scanning everything. It is an array of buckets (table[BUCKETS]), and a hash function turns each key into the number of its bucket.

hash uses djb2: it starts at 5381 and, for each character, multiplies by 33 and adds the character. The same key always gives the same number, and % BUCKETS brings it into the 0 to 4 range. The (unsigned char) cast avoids surprises with accented characters, which would be negative in a signed char.

Two keys can land in the same bucket: that is a collision, and it happens here to tea and juice, both in bucket 1. That is why each bucket is a linked list (the next field): put allocates an entry with malloc and puts it at the front of its bucket's list.

get works out the bucket and walks only that list, comparing with strcmp. With few entries per bucket, a lookup is almost immediate even when the table holds thousands of keys. If the key is missing, like soup, it returns NULL.

At the end each list is freed, bucket by bucket. The keys are not freed because they are string literals, not heap memory.

Code · main.c

#include <stdio.h>#include <stdlib.h>#include <string.h>#define BUCKETS 5typedef struct Entry { const char *key; double price; struct Entry *next; } Entry;  // one list per bucketunsigned long hash(const char *s) {  // djb2: the same text, always the same number    unsigned long h = 5381;    while (*s) h = h * 33 + (unsigned char)*s++;    return h % BUCKETS;               // and % turns it into a bucket}unsigned long put(Entry *table[], const char *key, double price) {    unsigned long b = hash(key);    Entry *e = malloc(sizeof *e);    if (!e) exit(EXIT_FAILURE);    e->key = key; e->price = price; e->next = table[b]; table[b] = e;    return b;}Entry *get(Entry *table[], const char *key) {  // only one bucket is searched    for (Entry *e = table[hash(key)]; e; e = e->next)        if (strcmp(e->key, key) == 0) return e;    return NULL;}int main(void) {    Entry *table[BUCKETS] = {NULL};    const char *drinks[] = {"coffee", "tea", "juice", "water", "cola", "milk"};    for (int i = 0; i < 6; i++)        printf("%-7s -> bucket %lu\n", drinks[i], put(table, drinks[i], 1.10 + i * 0.35));    Entry *cola = get(table, "cola");    printf("cola costs %.2f, soup is %s\n", cola->price, get(table, "soup") ? "found" : "missing");    for (int b = 0; b < BUCKETS; b++)  // free every list        for (Entry *e = table[b], *next; e; e = next) { next = e->next; free(e); }    return 0;}

Output · cc main.c -o main && ./main

coffee  -> bucket 3
tea     -> bucket 1
juice   -> bucket 1
water   -> bucket 2
cola    -> bucket 4
milk    -> bucket 0
cola costs 2.50, soup is missing

Key points

The hash function turns a key into a bucket number.
A collision is two keys sharing a bucket.
With chaining, each bucket is a linked list.
A lookup walks the list of a single bucket.

Exercise

Make put look the key up with get first and, if it is already there, only update the price; test it by setting tea to 1.25.