Offensive Security Researcher & Quantum Cryptography Analyst

Hash Tables Data Structure: Comprehensive Guide with C Implementations

Abdul Wahab Junaid
Hash Tables: Comprehensive Guide with C Implementations

Hash tables are, without exaggeration, one of the data structures I reach for the most in everyday programming. Whenever I need fast lookups by key — a dictionary, a cache, a set of unique items — a hash table is almost always my first instinct. What I find fascinating about them is how they trade a small amount of theoretical worst-case guarantee for extremely fast average-case performance, achieving expected $O(1)$ time for search, insertion, and deletion, something no comparison-based structure like a binary search tree can match.

I want to walk through not just how to use a hash table, but how it actually works underneath: how keys get mapped to positions in an array, what happens when two keys collide, and why the choice of hash function matters so much for performance in practice.

History and Background

Hashing as a technique dates back to the early 1950s. Hans Peter Luhn, a researcher at IBM, is often credited with proposing the core idea of hashing in an internal IBM memo around 1953, aiming to speed up search in symbol tables. The term “hashing” itself and further formalization came through subsequent work by researchers including Arnold Dumey, who discussed the idea in a 1956 paper on computer indexing.

Collision resolution techniques, including both chaining and open addressing, were developed and refined through the 1960s, with significant contributions by researchers publishing in the Communications of the ACM and other venues of that era. Universal hashing, which provides strong theoretical guarantees against adversarial inputs, was introduced by J. Lawrence Carter and Mark N. Wegman in their 1979 paper “Universal Classes of Hash Functions,” a major theoretical advance that underlies much of the rigorous analysis used in modern textbook treatments.

Problem Statement

I want to implement a dictionary (also called an associative array or symbol table): a data structure supporting INSERT, SEARCH, and DELETE operations on a dynamic set of key-value pairs, ideally all in $O(1)$ expected time, regardless of how large the set of possible keys is. A direct-address table (an array indexed directly by key) achieves $O(1)$ worst-case time, but only works when the universe of possible keys is small enough to allocate an array of that size — which is rarely practical, since keys might be strings, large integers, or other complex objects.

Core Concepts

How It Works

When I insert a key-value pair, I compute h(key) to get a slot index, and then place the pair at that slot. If chaining is used, I simply add the pair to the front (or end) of the linked list stored at that slot — collisions are handled gracefully since multiple entries can coexist in the same slot’s list. If open addressing is used, and the computed slot is already occupied by a different key, I compute an alternative probe position using a probe sequence, and repeat until I find an empty slot.

Searching for a key follows the same process: compute h(key), then either scan the linked list at that slot (chaining) or follow the same probe sequence used during insertion (open addressing) until I find the key or conclusively determine it’s absent (an empty slot, in the case of open addressing, signals the key isn’t present, assuming careful handling of deletions).

Deletion under chaining is simple — I find the node in the appropriate list and unlink it. Deletion under open addressing is trickier, because simply emptying a slot could break the probe sequence for other keys that were placed after a collision; this is typically handled by marking slots as “deleted” (a tombstone) rather than truly empty, so that searches continue to probe past them correctly.

Working Principle

The reason hash tables achieve such fast average performance is rooted in the simple uniform hashing assumption: if a good hash function spreads keys roughly evenly across the $m$ slots, then the expected number of keys per slot is the load factor $\alpha = n/m$. As long as $m$ is kept proportional to $n$ (i.e., $\alpha = O(1)$), the expected work per operation stays constant.

The internal mechanism differs meaningfully between the two collision-resolution strategies. Chaining essentially degrades gracefully — even under a bad hash function, correctness is never at risk, only speed, since a linked-list scan will always eventually find the key if it’s present. Open addressing is more delicate: the entire table’s occupied slots and empty slots must be consistent with the deterministic probe sequences used, and this interdependency is what makes deletion and dynamic resizing require extra care.

Mathematical Foundation

Expected search time in chaining, under simple uniform hashing. For a hash table with $m$ slots and $n$ stored keys using chaining, the expected length of a linked list at any slot is:

$$ \alpha = \frac{n}{m} $$

For an unsuccessful search (the key is not present), the expected number of elements examined is exactly $\alpha$, since the expected chain length is $\alpha$ and every element in that chain must be examined to confirm absence:

$$ E[\text{unsuccessful search}] = \Theta(1 + \alpha) $$

For a successful search, the expected number of elements examined is:

$$ E[\text{successful search}] = \Theta\left(1 + \frac{\alpha}{2}\right) = \Theta(1 + \alpha) $$

The $+1$ term accounts for the constant time needed to compute the hash function itself, which is independent of $\alpha$. If $m$ is chosen proportional to $n$, then $\alpha = O(1)$, giving expected $O(1)$ time per operation.

Open addressing probe sequence. The hash function is extended to include a probe number $i$:

$$ h(k, i) : U \times {0, 1, \dots, m-1} \rightarrow {0, 1, \dots, m-1} $$

For linear probing with an auxiliary hash function $h’$:

$$ h(k, i) = (h'(k) + i) \bmod m $$

For double hashing, using two auxiliary hash functions $h_1$ and $h_2$:

$$ h(k, i) = (h_1(k) + i \cdot h_2(k)) \bmod m $$

Expected number of probes under uniform hashing (open addressing). For an unsuccessful search with load factor $\alpha < 1$:

$$ E[\text{probes, unsuccessful}] \le \frac{1}{1 – \alpha} $$

For a successful search:

$$ E[\text{probes, successful}] \le \frac{1}{\alpha} \ln\left(\frac{1}{1 – \alpha}\right) $$

These formulas show clearly why open addressing performance degrades sharply as $\alpha$ approaches 1 — the denominator $1 – \alpha$ shrinks toward zero, causing the expected probe count to blow up.

Diagrams

flowchart TD
    A[Key k arrives for insert/search] --> B[Compute slot index using h of k]
    B --> C{Slot occupied?}
    C -->|No| D[Place key here - chaining: new list node<br/>open addressing: store directly]
    C -->|Yes, chaining| E[Append/search within linked list at that slot]
    C -->|Yes, open addressing| F[Compute next probe using h of k, i+1]
    F --> C

Pseudocode

Chained hash table:

CHAINED-HASH-INSERT(T, x)
    insert x at the head of list T[h(x.key)]

CHAINED-HASH-SEARCH(T, k)
    search for an element with key k in list T[h(k)]

CHAINED-HASH-DELETE(T, x)
    delete x from the list T[h(x.key)]

Open-addressing hash table:

HASH-INSERT(T, k)
    i = 0
    repeat
        j = h(k, i)
        if T[j] == NIL or T[j] == DELETED
            T[j] = k
            return j
        i = i + 1
    until i == m
    error "hash table overflow"

HASH-SEARCH(T, k)
    i = 0
    repeat
        j = h(k, i)
        if T[j] == k
            return j
        i = i + 1
    until T[j] == NIL or i == m
    return NIL

Step-by-Step Example

Let me trace chained hashing with a table of size $m = 7$ and the simple hash function $h(k) = k \bmod 7$. I insert keys 10, 22, 31, 4, 15, 28 in that order.

Final table:

Slot 0: 28
Slot 1: 15 -> 22
Slot 2: (empty)
Slot 3: 31 -> 10
Slot 4: 4
Slot 5: (empty)
Slot 6: (empty)

If I now search for 31, I compute $h(31) = 3$, go to slot 3’s list, and find 31 at the front — a fast, one-comparison search. If I search for 100, I compute $h(100) = 2$, find slot 2 empty, and correctly conclude 100 isn’t in the table.

Time Complexity

Space Complexity

A chained hash table uses $\Theta(n + m)$ space: $\Theta(m)$ for the array of slot headers, and $\Theta(n)$ for the actual stored elements distributed across the linked lists. An open-addressing hash table uses $\Theta(m)$ space total, since all elements are stored directly within the array itself with no extra linked-list overhead — this is one of open addressing’s practical advantages when memory efficiency matters, though it requires $m \ge n$ always, whereas chaining can technically handle $\alpha > 1$ (at a performance cost).

Correctness Analysis

For chaining, correctness is straightforward: since every key that hashes to a given slot is guaranteed to be somewhere in that slot’s linked list, a full scan of the list will always correctly find the key if present, or correctly conclude its absence if the list is exhausted without a match.

For open addressing, correctness depends critically on the probe sequence being a genuine permutation of ${0, 1, \dots, m-1}$ for each key — meaning that as $i$ ranges from 0 to $m-1$, $h(k, i)$ visits every slot in the table exactly once. This guarantees that if there’s an empty slot anywhere in the table, the insertion algorithm will eventually find it. Search correctness in open addressing crucially depends on this same guarantee, plus correct handling of deletions: if a naive deletion sets a slot back to genuinely empty (NIL) rather than using a “deleted” tombstone marker, a subsequent search might incorrectly stop probing early at that empty slot and wrongly report a key as absent even though it exists further along the original probe sequence.

Advantages

Disadvantages

Applications

Implementation in C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE 7

typedef struct HashNode {
    int key;
    int value;
    struct HashNode* next;
} HashNode;

typedef struct {
    HashNode* buckets[TABLE_SIZE];
} HashTable;

void initTable(HashTable* table) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        table->buckets[i] = NULL;
    }
}

/* A simple hash function: key mod table size. In production code,
   I would use a stronger hash function to spread keys more evenly. */
int hashFunction(int key) {
    return key % TABLE_SIZE;
}

void insert(HashTable* table, int key, int value) {
    int index = hashFunction(key);

    /* Check whether the key already exists, and update it if so */
    HashNode* current = table->buckets[index];
    while (current != NULL) {
        if (current->key == key) {
            current->value = value;
            return;
        }
        current = current->next;
    }

    /* Otherwise, insert a new node at the head of the chain */
    HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
    newNode->key = key;
    newNode->value = value;
    newNode->next = table->buckets[index];
    table->buckets[index] = newNode;
}

int search(HashTable* table, int key, int* found) {
    int index = hashFunction(key);
    HashNode* current = table->buckets[index];

    while (current != NULL) {
        if (current->key == key) {
            *found = 1;
            return current->value;
        }
        current = current->next;
    }
    *found = 0;
    return -1;
}

void deleteKey(HashTable* table, int key) {
    int index = hashFunction(key);
    HashNode* current = table->buckets[index];
    HashNode* prev = NULL;

    while (current != NULL) {
        if (current->key == key) {
            if (prev == NULL) {
                table->buckets[index] = current->next;
            } else {
                prev->next = current->next;
            }
            free(current);
            return;
        }
        prev = current;
        current = current->next;
    }
}

void printTable(HashTable* table) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        printf("Slot %d: ", i);
        HashNode* current = table->buckets[i];
        while (current != NULL) {
            printf("(%d,%d) -> ", current->key, current->value);
            current = current->next;
        }
        printf("NULL\n");
    }
}

int main(void) {
    HashTable table;
    initTable(&table);

    int keys[] = {10, 22, 31, 4, 15, 28};
    int n = sizeof(keys) / sizeof(keys[0]);

    for (int i = 0; i < n; i++) {
        insert(&table, keys[i], keys[i] * 100);  /* store key*100 as a sample value */
    }

    printf("Hash table contents:\n");
    printTable(&table);

    int found;
    int value = search(&table, 31, &found);
    printf("\nSearch for key 31: %s (value=%d)\n", found ? "Found" : "Not found", value);

    deleteKey(&table, 31);
    printf("\nHash table after deleting key 31:\n");
    printTable(&table);

    return 0;
}

I want to point out that insert here checks for an existing key first and updates its value rather than blindly adding a duplicate node — this mirrors how most real dictionary implementations behave, where inserting an already-present key updates it rather than creating a second entry.

Sample Input and Output

Input:
Insert keys (with value = key*100): 10, 22, 31, 4, 15, 28
Search for key: 31
Delete key: 31

Output:
Hash table contents:
Slot 0: (28,2800) -> NULL
Slot 1: (15,1500) -> (22,2200) -> NULL
Slot 2: NULL
Slot 3: (31,3100) -> (10,1000) -> NULL
Slot 4: (4,400) -> NULL
Slot 5: NULL
Slot 6: NULL

Search for key 31: Found (value=3100)

Hash table after deleting key 31:
Slot 0: (28,2800) -> NULL
Slot 1: (15,1500) -> (22,2200) -> NULL
Slot 2: NULL
Slot 3: (10,1000) -> NULL
Slot 4: (4,400) -> NULL
Slot 5: NULL
Slot 6: NULL

This matches my hand-traced example precisely, and shows the deletion correctly unlinking 31 while leaving 10 (which shared the same slot) intact.

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version