17. Hash Tables

From searching to maps#

A map stores pairs of a key and a value. The key is what we know; the value is what we want to retrieve. A student number can be a key and a student record its value. Keys are unique within a map, but values need not be: both Kevin and Alex may like blue.

The essential operations are insert(key, value), lookup(key) and delete(key). Inserting an existing key replaces its value, rather than creating another entry. A set only needs the keys; 18. Applications of Hash Tables develops this connection. Recall from 08. Abstract Data Types that the map is the interface; the hash table is one representation.

Notice that we store the key as well as the value. A slot number does not uniquely identify a key: different keys can hash to the same index, so we must compare the stored key with the requested one.

For $n$ pairs, an unordered array searches up to $n$ entries. Even insertion costs $O(n)$ if it must detect an existing key first. A sorted array gives $O(\log n)$ lookup, but insertion/deletion requires up to $n$ shifts. A balanced BST gives $O(\log n)$ operations and preserves key order. These costs assume fixed-cost key comparisons; comparing long strings adds character work.

A hash table aims for expected constant-time operations by computing where a key should live. It trades sorted order and a logarithmic worst-case guarantee for this expectation. For predecessor, successor or ranges of ordered keys, an AVL tree is often better.

Practice. Insert (jas, green), (andrew, red), then (jas, orange). How many pairs exist? Can two keys have value red?

Hashing and collisions#

Let $m$ be the number of array slots, indexed $0,\ldots,m-1$. A hash function maps a key to an index in that range, its home slot. For non-negative integer keys:

$$h(k)=k\bmod m.$$

With $m=11$, the lecture keys $4,8,15,16,23,42$ have homes $4,8,4,5,1,9$. Keys $4$ and $15$ both want slot $4$. This is a collision: distinct keys have the same home. The keys are still different; replacing one with the other would destroy the map.

Collisions are unavoidable when possible keys outnumber slots. A better hash spreads keys more evenly; it cannot assign every possible key a distinct slot in a smaller array.

A useful hash is deterministic, cheap, and distributes the actual keys reasonably evenly. Deterministic means an unchanged key has the same hash while the hash rules and capacity remain unchanged. Mutating a stored string key can make it belong to a different bucket without moving it there.

For a string of length $L$, hashing normally reads $L$ characters, costing $\Theta(L)$. Summing character codes is simple but maps "ab" and "ba" to the same result. Multiplying an accumulator before adding the next character makes order matter:

#include <stddef.h>
#include <stdint.h>

size_t stringSlot(const char *s, size_t slots) {
    /* Preconditions: slots > 0; s is a terminated string. */
    uint32_t h = 0;
    for (const unsigned char *p = (const unsigned char *)s; *p; p++)
        h = 31u * h + *p;
    return (size_t)h % slots;
}

Unsigned arithmetic wraps with defined C semantics. The lecture's rolling hash and PostgreSQL mixing example illustrate more elaborate mixing; you need not memorise those implementations. Table indexing is also a different design problem from password storage or cryptographic integrity checking. Those lecture asides motivate other uses of hashing; the course's simple modulo/string functions illustrate table indexing.

The load factor

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

is the average number of items per slot, before considering collision resolution. It does not guarantee every slot has that many items. Six items in seven slots gives $\alpha=6/7$, but all six could share one home.

Practice. For $m=7$, find the homes of $23,4,16,42,8,15$. Why can operations be slow even at low load?

Separate chaining#

In separate chaining, each array entry points to a linked list of pairs whose keys hash there. Empty buckets contain NULL. Recall 01. C and Linked Lists: a node contains data and a pointer to the next node. The bucket invariant is that every node in bucket $i$ satisfies $h(\text{key})=i$.

The lecture inserts $23,4,16,42,8,15$ into seven buckets, appending new keys:

To find 16, hash to bucket 2, compare with 23, then 16. To find absent 30, hash to bucket 2 and reach the end after those comparisons. Reaching NULL proves absence because the invariant confines all matches to this bucket.

Insertion searches the same chain: finding the key updates its value without changing $n$; reaching the end allocates one node and increases $n$. Deletion reconnects the pointer leading to the node to its successor, then frees it. Deleting a head updates the array entry itself.

A complete integer-key map in C#

This fixed-capacity teaching map accepts negative keys, reports allocation failure on insertion, and distinguishes absence from legitimate values such as zero. It does not resize automatically; resizing is developed below.

#include <stdbool.h>
#include <stddef.h>
#include <stdlib.h>

struct entry {
    int key, value;
    struct entry *next;
};
struct map {
    size_t slots, count;
    struct entry **bucket;
};

static size_t home(int key, size_t slots) {
    return (size_t)(unsigned int)key % slots;
}

struct map *mapNew(size_t slots) {
    if (slots == 0) return NULL;
    struct map *t = malloc(sizeof *t);
    if (t == NULL) return NULL;
    t->bucket = calloc(slots, sizeof *t->bucket);
    if (t->bucket == NULL) {
        free(t);
        return NULL;
    }
    t->slots = slots;
    t->count = 0;
    return t;
}

bool mapGet(const struct map *t, int key, int *out) {
    for (struct entry *p = t->bucket[home(key, t->slots)];
         p != NULL; p = p->next) {
        if (p->key == key) {
            if (out != NULL) *out = p->value;
            return true;
        }
    }
    return false;
}

bool mapPut(struct map *t, int key, int value) {
    struct entry **link = &t->bucket[home(key, t->slots)];
    while (*link != NULL) {
        if ((*link)->key == key) {
            (*link)->value = value;
            return true;
        }
        link = &(*link)->next;
    }
    struct entry *p = malloc(sizeof *p);
    if (p == NULL) return false;
    *p = (struct entry){key, value, NULL};
    *link = p;
    t->count++;
    return true;
}

bool mapRemove(struct map *t, int key) {
    struct entry **link = &t->bucket[home(key, t->slots)];
    while (*link != NULL && (*link)->key != key)
        link = &(*link)->next;
    if (*link == NULL) return false;
    struct entry *old = *link;
    *link = old->next;
    free(old);
    t->count--;
    return true;
}

void mapFree(struct map *t) {
    if (t == NULL) return;
    for (size_t i = 0; i < t->slots; i++) {
        struct entry *p = t->bucket[i];
        while (p != NULL) {
            struct entry *next = p->next;
            free(p);
            p = next;
        }
    }
    free(t->bucket);
    free(t);
}

link points to the pointer owning the current node: initially an array entry, then a previous node's next field. This makes head and interior deletion the same operation. Read old->next before free(old); accessing the node afterwards is invalid.

The map owns its array and nodes, and copies its integer keys/values. A string-key map must choose whether to copy strings or borrow them, and free only what it owns. All operations except mapFree require a valid live map.

mapGet(t, key, &value) performs one traversal and returns whether the key exists. Calling Contains then Get repeats the search. Get-or-default is convenient, but a default value alone cannot distinguish absence from an existing entry with that value. Initialise capacity before any loop using it; the lecture constructor's ordering is schematic, not a safe copyable constructor.

Practice. Bucket 2 contains 23 → 16. Explain deleting 23 and deleting absent 30.

Deriving chaining costs#

For a bucket with $\ell$ nodes, absent lookup takes $\Theta(1+\ell)$: compute the home and traverse its chain. Existing-key updates and deletion may also traverse the whole chain.

Under approximately uniform hashing, expected chain length is $\alpha=n/m$, giving expected $O(1+\alpha)$ operations for fixed-size keys. With constant-bounded load this is expected $O(1)$. Successful searches can stop earlier but have the same asymptotic bound.

Worst case puts all $n$ items in one chain: lookup, map insertion and deletion take $O(n)$. This bound uses items, not slots: the lecture briefly labels its worst case using the slot symbol, but chain length determines the work. Total storage is $\Theta(m+n)$. Iterative operations use $O(1)$ auxiliary space; recursive chain helpers may use $O(\ell)$ stack frames.

Linear probing#

Open addressing stores pairs directly in array slots. Linear probing tries consecutive positions, wrapping at the end:

$$h(k),\ (h(k)+1)\bmod m,\ldots,(h(k)+m-1)\bmod m.$$

Each slot stores one pair, so $n\leq m$. Insertion needs either a free slot or an existing matching key.

With seven slots, insert 7, 14, 21 using $h(k)=k\bmod7$. All hash to 0. 7 occupies 0; 14 checks 0 and occupies 1; 21 checks 0, 1 and occupies 2.

Absent lookup for 28 checks 0, 1, 2 and stops at unused slot 3. Lookup for 14 stops at 1 because the key matches. Stop at an unused slot or the matching key, never simply at a non-matching occupied slot.

The player records the same slots and decisions. Its snapshots are a teaching trace, not executed C.

Insertion also replaces existing keys. Bound probing by $m$ attempts so a full table cannot loop forever. The invariant is that every earlier position in this key's probe sequence has been checked without finding an unused slot or the key.

Here is the exact fixed-seven-slot insertion and lookup behind the player. The table must begin zero-initialised, for example struct lpSlot table[7] = {0};. The player draws keys only; the C array also carries values. lpPut updates a matching key in place. Its false return means all slots were occupied by other keys. lpGet stops at the first never-used slot because insertion could not have skipped it. This no-deletion version deliberately has no tombstones; use the deletion methods below before extending it.

#include <stdbool.h>
#include <stddef.h>

struct lpSlot { int key, value; bool used; };

bool lpPut(struct lpSlot table[7], int key, int value) {
    size_t home = (size_t)(unsigned)key % 7;
    for (size_t attempt = 0; attempt < 7; attempt++) {
        size_t i = (home + attempt) % 7;
        if (table[i].used && table[i].key != key) continue;
        table[i] = (struct lpSlot){key, value, true};
        return true;
    }
    return false; /* Full; caller must resize and rehash. */
}

bool lpGet(const struct lpSlot table[7], int key, int *out) {
    size_t home = (size_t)(unsigned)key % 7;
    for (size_t attempt = 0; attempt < 7; attempt++) {
        size_t i = (home + attempt) % 7;
        if (!table[i].used) return false;
        if (table[i].key == key) {
            if (out != NULL) *out = table[i].value;
            return true;
        }
    }
    return false;
}

Deletion and probe paths#

Deleting 7 and marking slot 0 unused makes lookup for 14 stop immediately at 0. The remaining key becomes unreachable. Deletion has broken its probe path, the sequence lookup must follow.

Remove and reinsert the following run. Clear the deleted slot, then remove/reinsert each successive occupied pair up to the next genuinely unused slot. This restores the search invariant. The lecture calls this backshift; moving every item one position left without considering its home is not equivalent.

In the ten-slot lecture example, deleting 24 at 4 frees that slot. 5 belongs at 5 and stays there. 14 hashes to 4 and moves there. 4 probes through 4 and 5 and occupies 6; 18 remains at 8. Deletion includes the reinsertion work, not just clearing a cell. For a run of $r$ keys all sharing a home, literal reinsertion can probe $1+2+\cdots+r$ positions, giving $O(r^2)$ worst-case repair work. An optimised backward-shift algorithm can instead decide directly which keys can move into each hole in linear work, but that is a different implementation from removing and reinserting every following pair.

Use a tombstone. Slots have three states: UNUSED, LIVE and DELETED. Lookup continues past DELETED; insertion can eventually reuse it.

For map insertion, remember the first tombstone while continuing to search for an existing matching key. Otherwise an immediate insertion could create a duplicate before encountering the original later in the run. Once an unused slot or full-cycle boundary establishes absence, use the remembered tombstone if available. Tombstones avoid movement but accumulate and lengthen unsuccessful searches; rebuilding removes them.

Practice. Slots 0, 1, 2 contain DELETED, 14, 21, all with home 0. Where should inserting (14, 99) write?

Clustering and cost#

A cluster is a consecutive run of occupied slots. Keys hashing into it traverse part of the run and often extend it. Longer runs attract more additions; two runs can join. This is primary clustering.

At load bounded away from 1, with well-distributed hashes, insertion and lookup have expected $O(1)$ probe counts. A single insertion, lookup or tombstone deletion search can visit $m$ slots in the worst case, giving $O(m)$ time. Literal remove-and-reinsert deletion additionally pays for all reinsertion probes, so its worst-case repair can be quadratic as explained above. When capacity is proportional to item count, this is often written $O(n)$. Storage is $\Theta(m)$ and probing uses $O(1)$ auxiliary space.

In the standard random-home linear-probing model without accumulated tombstones, approximate expected probes are

$$\text{successful}\approx\frac12\left(1+\frac1{1-\alpha}\right),\qquad \text{unsuccessful}\approx\frac12\left(1+\frac1{(1-\alpha)^2}\right).$$

These are model estimates, not exact counts for every table. At $\alpha=0.5$, they are $1.5$ and $2.5$; at $\alpha=0.9$, $5.5$ and $50.5$. The second formula is for unsuccessful search, clarifying the lecture's repeated successful label and ambiguous exponent. The important observation is how rapidly cost grows near full capacity.

Double hashing#

Double hashing gives each key its own probe increment:

$$\text{probe}_j(k)=(h_1(k)+j\,h_2(k))\bmod m.$$

$j$ starts at zero. Insertion and lookup must use the same hashes. Different increments reduce primary clustering because colliding keys need not follow the same consecutive sequence.

To visit every slot, the increment must be relatively prime to $m$: their greatest common divisor is 1. A convenient choice is prime $m$ and $1\leq h_2(k)\leq m-1$. With $m=8$ and increment 2, only four slots are visited before repeating, potentially missing empty slots.

The lecture uses $m=11$, $h_1(k)=k\bmod11$ and $h_2(k)=k\bmod5+1$:

Here is the same fixed eleven-slot variant in C. It reuses struct lpSlot defined above: every slot stores a key, value and used flag. Its secondary increment is always 1–5, so it is nonzero and relatively prime to prime capacity 11. Do not reuse the linear-probing lookup or deletion routine on this table; every operation must follow this key's own sequence. The example has no deletion, so used == false means a truly unused slot.

/* Requires <stdbool.h>, <stddef.h> and struct lpSlot from above. */
static size_t dhHome(int key) { return (size_t)(unsigned)key % 11; }
static size_t dhStep(int key) { return (size_t)(unsigned)key % 5 + 1; }

bool dhPut(struct lpSlot table[11], int key, int value) {
    size_t i = dhHome(key), step = dhStep(key);
    for (size_t attempt = 0; attempt < 11; attempt++) {
        if (!table[i].used || table[i].key == key) {
            table[i] = (struct lpSlot){key, value, true};
            return true;
        }
        i = (i + step) % 11;
    }
    return false; /* Every slot inspected; resize and rehash. */
}

bool dhGet(const struct lpSlot table[11], int key, int *out) {
    size_t i = dhHome(key), step = dhStep(key);
    for (size_t attempt = 0; attempt < 11; attempt++) {
        if (!table[i].used) return false;
        if (table[i].key == key) {
            if (out != NULL) *out = table[i].value;
            return true;
        }
        i = (i + step) % 11;
    }
    return false;
}

attempt bounds a full cycle even if no unused slot remains. At each step, the same key determines the same increment, so lookup retraces insertion's sequence. A matching key updates its value without adding a second entry. dhGet stops at a never-used slot because insertion would have stopped there too. Deletion requires tombstones or a full rehash; clearing a used flag in place would break that proof.

Returning home after $t$ advances means $t\,h_2(k)$ is divisible by $m$. If increment and capacity share no factors, the smallest positive such $t$ is $m$. The cycle therefore includes every position.

Tombstone deletion works here too. Reinserting only a consecutive run does not generally repair double hashing: probe paths are not consecutive. Under ideal uniform probing, expected successful search is approximately $\frac1\alpha\ln\frac1{1-\alpha}$ and unsuccessful search $\frac1{1-\alpha}$. Double hashing aims to approximate that distribution; arbitrary hashes do not guarantee it. Worst case remains $O(m)$.

Practice. Starting at home 3 in an eleven-slot table with increment 4, list four probes.

Resizing and choosing a representation#

When a load threshold is exceeded, allocate a larger table and rehash every live pair. Copying pairs to their previous indices is wrong: changing $m$ changes homes and probe paths. Keep the old table intact until allocation and reconstruction succeed, then release its representation.

Roughly doubling capacity produces $m,2m,4m,\ldots$. The rebuilding work forms a geometric sum smaller than twice the final capacity. With good distribution and bounded load, $n$ insertions have expected total $O(n)$ rebuilding work. This is expected amortised constant overhead: amortised averages across an operation sequence, while expected refers to a hashing distribution. One insertion triggering a rebuild still costs $\Theta(n)$ under these assumptions. See 03. Analysis of Algorithms for the distinction.

This does not rescue a poor hash. Rebuilding with all keys colliding can require quadratic insertion work. String hashing and comparison retain their character costs.

More exam-style practice#

Work each prompt before opening its answer. State the invariant or cost assumption that makes your reasoning valid.

Question 1. With table size 7 and h(k)=k mod 7, insert keys 10, 17 and 24 by linear probing into an empty table. Where do they land?

Question 2. Why must deleting key 17 from that table not simply mark slot 4 as never-used empty?

Question 3. A chaining table has n=80 keys and m=20 buckets. What is its load factor, and what does an expected constant-time claim assume?

Continue with 18. Applications of Hash Tables for sets and counting; 21. COMP2521 Revision compares hashing with trees, heaps and tries.