</>EmbeddedInterview

What is a hash table and how do you handle collisions?

MediumData Structures & Algorithms

Short answer: A hash table maps keys to array buckets with a hash function, giving O(1) average lookup, insertion and deletion. When two keys map to the same bucket (a collision), it is handled by chaining (each bucket holds a linked list of entries) or open addressing (probe for another slot: linear, quadratic or double hashing). For embedded use, a fixed-size open-addressing table with linear probing is common: no allocation, cache friendly, and predictable memory; keep the load factor below about 70% so probe sequences stay short.

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>

#define TBL 16u                          /* power of two */
typedef struct { uint32_t key; int val; bool used; } slot_t;
static slot_t tbl[TBL];

static uint32_t hash32(uint32_t x)       /* integer mixing hash */
{
    x ^= x >> 16; x *= 0x7feb352dU; x ^= x >> 15; x *= 0x846ca68bU; x ^= x >> 16;
    return x;
}

bool ht_put(uint32_t key, int val)
{
    for (uint32_t i = 0, h = hash32(key); i < TBL; i++) {
        slot_t *s = &tbl[(h + i) & (TBL - 1)];
        if (!s->used || s->key == key) { s->key = key; s->val = val; s->used = true; return true; }
    }
    return false;                                         /* full */
}

bool ht_get(uint32_t key, int *val)
{
    for (uint32_t i = 0, h = hash32(key); i < TBL; i++) {
        slot_t *s = &tbl[(h + i) & (TBL - 1)];
        if (!s->used) return false;                       /* empty slot ends the probe */
        if (s->key == key) { *val = s->val; return true; }
    }
    return false;
}

int main(void)
{
    ht_put(0x100, 1); ht_put(0x7E3, 2); ht_put(0xCAFE, 3);
    int v;
    printf("%d ", ht_get(0x7E3, &v) ? v : -1);
    printf("%d\n", ht_get(0x123, &v) ? v : -1);           /* 2 -1 */
    return 0;
}

Deletion with open addressing: you cannot simply mark a slot empty, because that would break the probe chain for keys inserted after it; use a tombstone marker or re-insert the following cluster (backward-shift deletion).

Choosing a hash function: fast and well-mixing (FNV-1a for strings, multiply-shift or murmur finalisers for integers). Hash tables used with untrusted input (network keys) need a seeded hash (SipHash) to avoid attackers forcing collisions.

Worst case: O(n) if many keys collide, so hard real-time code sometimes prefers a sorted array with binary search (O(log n) guaranteed) or a perfect hash generated offline for a fixed key set (e.g. command names).