Hash tables

Why this matters

Finding something in an unsorted array or a linked list means looking at every element: O(n). A hash table finds, inserts and deletes by key in O(1) on average, whatever the size. It is the most useful data structure in practical programming: Python's dict and set, JavaScript objects, symbol tables in compilers, caches, database indexes, routing tables, and the uniq-like counting you will do in the projects module are all hash tables. In C there is no built-in one, so writing your own (or knowing exactly what a library's does) is a rite of passage. It also brings together everything in this module: arrays, linked lists, strings and careful ownership of heap memory.

The idea

Suppose keys were small integers: you could use the key itself as an array index, and lookup would be one memory access. A hash table generalizes that trick to any key:

1. A hash function turns the key (say, a string) into a large integer.
2. That integer, reduced modulo the number of slots, picks a bucket in an array.
3. The entry is stored in that bucket.

  "apple" --hash--> 280767167 --% 8--> 7
  "kiwi"  --hash--> .........  --% 8--> 1

  buckets[0]  NULL
  buckets[1]  -> [kiwi=40]
  buckets[2]  NULL
  buckets[3]  -> [plum=30]
  buckets[4]  -> [lime=50]
  buckets[5]  -> [fig=99] -> [pear=10]      two keys, same bucket: a collision
  buckets[6]  NULL
  buckets[7]  -> [apple=0]

Different keys can land in the same bucket, a collision; with more keys than buckets it is unavoidable. The simplest way to handle it is separate chaining: each bucket holds a linked list of the entries that hash there. Lookup hashes the key, picks the bucket, and walks that (short) list comparing keys. (The alternative, open addressing, stores entries directly in the array and probes neighbouring slots on a collision; Python's dict does that.)

A good hash function

A hash function must be deterministic (same key, same hash) and should spread keys uniformly over the buckets, so that similar keys like "item1" and "item2" end up far apart. For strings, a simple and decent choice is FNV-1a:

uint32_t hash(const char *s)
{
    uint32_t h = 2166136261u;           /* "offset basis" */
    for (; *s != '\0'; s++) {
        h ^= (unsigned char)*s;          /* mix in one byte */
        h *= 16777619u;                  /* "FNV prime": spreads the bits */
    }
    return h;
}

The multiplication wraps modulo 2^32, which is well defined for uint32_t (and would be undefined for a signed int). XOR-then-multiply makes every input byte influence all the bits of the result. Production systems facing untrusted input use keyed hashes such as SipHash, because an attacker who knows your hash function can choose keys that all collide and turn every lookup into O(n): a real denial-of-service attack against web servers in 2011.

A complete chained table

typedef struct Entry {
    char *key;              /* owned copy of the key */
    int value;
    struct Entry *next;     /* next entry in the same bucket */
} Entry;

typedef struct {
    Entry **buckets;        /* array of nbuckets list heads */
    size_t nbuckets;
    size_t count;
} Table;

int table_init(Table *t, size_t nbuckets)
{
    t->buckets = calloc(nbuckets, sizeof *t->buckets);   /* all NULL */
    t->nbuckets = nbuckets;
    t->count = 0;
    return t->buckets ? 0 : -1;
}

Entry *table_find(const Table *t, const char *key)
{
    Entry *e = t->buckets[hash(key) % t->nbuckets];
    for (; e != NULL; e = e->next)
        if (strcmp(e->key, key) == 0)
            return e;
    return NULL;
}

/* Insert or update. Returns 0, or -1 if out of memory. */
int table_put(Table *t, const char *key, int value)
{
    Entry *e = table_find(t, key);
    if (e != NULL) {
        e->value = value;
        return 0;
    }
    e = malloc(sizeof *e);
    if (e == NULL)
        return -1;
    size_t len = strlen(key);
    e->key = malloc(len + 1);
    if (e->key == NULL) {
        free(e);
        return -1;
    }
    memcpy(e->key, key, len + 1);
    e->value = value;
    size_t b = hash(key) % t->nbuckets;
    e->next = t->buckets[b];        /* push onto the front of the bucket */
    t->buckets[b] = e;
    t->count++;
    return 0;
}

void table_free(Table *t)
{
    for (size_t b = 0; b < t->nbuckets; b++) {
        Entry *e = t->buckets[b];
        while (e != NULL) {
            Entry *next = e->next;
            free(e->key);
            free(e);
            e = next;
        }
    }
    free(t->buckets);
    t->buckets = NULL;
}

buckets is an array of Entry *, one list head per bucket, hence the type Entry **. calloc gives all-zero memory, which for pointers means NULL on every platform you will meet: empty lists.

Storing apple pear fig plum kiwi lime with values 0, 10, ... 50 into 8 buckets, then updating fig to 99, and printing every bucket gives the picture from the start of the lesson:

hash("apple") = 280767167, bucket 7
bucket 0:
bucket 1: kiwi=40
bucket 2:
bucket 3: plum=30
bucket 4: lime=50
bucket 5: fig=99 pear=10
bucket 6:
bucket 7: apple=0
plum -> 30, grape -> missing, count 6

Note the iteration order: it follows the buckets, not insertion order, and it changes whenever the table is resized. Never rely on a hash table's order. (That is why the exercise prints counts for words you name, rather than dumping the table.)

Owning the keys

table_put copies the key into its own allocation. That matters: the caller's string might be a buffer that is reused for the next word (exactly what scanf("%255s", word) in a loop does), or a local array that disappears when a function returns. If the table stored the caller's pointer, every entry would end up pointing at the same buffer. The table owns its key copies, and table_free releases them. This is the ownership discipline from the dynamic memory module applied to a container. (POSIX's strdup does the malloc + memcpy in one call, but it is not part of C17, so it needs a feature macro; writing it out keeps the code portable.)

Load factor and resizing

The load factor is count / nbuckets, the average chain length. Lookups cost about one hash plus a walk of length proportional to the load factor. With a fixed bucket array, inserting 1,000,000 keys into 64 buckets makes chains of about 15,000 entries, and the "O(1)" table is a slow linked list.

The fix is the same as for a dynamic array: when the load factor passes a threshold (0.75 for open addressing, 1 to 2 for chaining), double the number of buckets and rehash: move every entry to the bucket hash(key) % new_size, since its old index was computed with the old size. Rehashing is O(n), but doubling means it happens rarely enough that inserts stay O(1) amortized. Entries can be moved by relinking their nodes; the keys themselves never need copying.

Common mistakes

• Comparing keys with ==. That compares pointers. Use strcmp(a, b) == 0.
• Storing the caller's key pointer instead of a copy, so keys change or dangle.
• Using the old bucket count after resizing, or computing a bucket index before growing and using it after.
• Freeing entries during a resize. Only the old array is freed; the entries move.
• Signed hash arithmetic. int h; h *= 16777619; overflows: undefined behavior. Use uint32_t.
• Relying on iteration order. It is arbitrary and changes on resize.

Recap

• A hash table maps a key through a hash function to a bucket index: hash(key) % nbuckets.
• Collisions are handled by chaining: each bucket is a linked list, searched with strcmp.
• A good hash spreads keys uniformly; FNV-1a is simple and decent for strings.
• The table owns copies of its keys and frees them.
• Keep the load factor bounded by doubling and rehashing; operations stay O(1) on average.

Going further: add table_remove using the pointer-to-pointer technique from the linked list lesson. Then read about open addressing with linear probing and why it is often faster than chaining on modern CPUs (hint: the cache, again).