Appendix A
Hashing
In this chapter
Learning outcomes
Resolve collisions, calculate load factor and explain why open-address deletion needs a special marker.
A.1 Key-to-slot mapping
Hashing maps a key to a table position using a hash function. A collision occurs when different keys map to the same slot. Collisions are normal; a correct table must handle them. Load factor is number of stored keys / number of slots.
A hash table is not a sorted structure. Expected constant-time lookup depends on assumptions about hashing, load and collision handling; worst-case lookup can be linear.
A.2 Chaining and open addressing
Chaining stores a collection of keys at each bucket. Open addressing stores keys in table slots and probes alternatives after a collision. Linear probing uses consecutive slots with wraparound; quadratic probing and double hashing use different probe sequences and require suitable table-size and step choices.
For capacity 7 and h(k) = k mod 7 on nonnegative keys, 10, 17 and 24 all start at slot 3. Linear probing places them at 3, 4 and 5. Searching for 24 must inspect the intervening occupied slots.
A.3 Deletion and tombstones
If 17 is removed and slot 4 is simply marked never-used, a search may stop there and incorrectly report 24 absent. Mark it deleted, or tombstone, instead. Lookup continues through a tombstone but may stop at a never-used slot. Insertion may reuse a tombstone after checking that the key is not already present later in the probe sequence.
Bound every probe by table capacity. A full table or one containing only tombstones must not cause an infinite loop. The supplied integer-set lab uses capacity 7, distinguishes empty/occupied/deleted states and rejects a new key when no slot is available. It does not resize.
Practice
- Insert 8, 15 and 22 into an empty capacity-seven linear-probing table.
- Why is a tombstone different from an unused slot?
- Explain why a hash table does not directly answer “print keys in sorted order”.
Programming laboratory
Download hashing.c · Contracts and run instructions
Compile this file on its own. Check the empty, boundary and ordinary cases before changing the implementation.
Read the complete C11 program
/* C11. integer set: linear probing with tombstones. */
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <limits.h>
#include <stdio.h>
#define CAP 7
typedef enum { EMPTY, OCCUPIED, DELETED } State;
typedef struct { int key; State state; } Slot;
typedef struct { Slot slot[CAP]; } Table;
/* Nonnegative modulo, including negative keys; no negation of INT_MIN. */
static size_t hash(int key)
{
int remainder = key % CAP;
return (size_t)(remainder < 0 ? remainder + CAP : remainder);
}
static size_t locate(const Table *t, int key)
{
size_t start = hash(key);
for (size_t step = 0; step < CAP; ++step) {
size_t i = (start + step) % CAP;
if (t->slot[i].state == EMPTY) return CAP;
if (t->slot[i].state == OCCUPIED && t->slot[i].key == key) return i;
}
return CAP;
}
static bool insert(Table *t, int key)
{
size_t start = hash(key), available = CAP;
for (size_t step = 0; step < CAP; ++step) {
size_t i = (start + step) % CAP;
if (t->slot[i].state == OCCUPIED) {
if (t->slot[i].key == key) return true; /* set: no duplicates */
} else {
if (available == CAP) available = i;
if (t->slot[i].state == EMPTY) break;
}
}
if (available == CAP) return false;
t->slot[available] = (Slot){key, OCCUPIED}; return true;
}
static bool erase(Table *t, int key)
{
size_t i = locate(t, key);
if (i == CAP) return false;
t->slot[i].state = DELETED; /* Do not break a later key's probe chain. */
return true;
}
int main(void)
{
Table t = {{{0, EMPTY}}};
assert(locate(&t, 10) == CAP && !erase(&t, 10));
assert(insert(&t, 10) && insert(&t, 17) && insert(&t, 24));
assert(locate(&t, 10) == 3 && locate(&t, 17) == 4 && locate(&t, 24) == 5);
assert(erase(&t, 17)); assert(locate(&t, 24) == 5);
assert(insert(&t, 31)); assert(locate(&t, 31) == 4);
assert(insert(&t, 24)); /* Duplicate after a previously deleted position. */
assert(insert(&t, -1)); assert(locate(&t, -1) != CAP);
assert(insert(&t, 0) && insert(&t, 1) && insert(&t, 2));
assert(!insert(&t, 99)); assert(locate(&t, 99) == CAP);
assert(insert(&t, 10)); /* Existing key succeeds even in a full table. */
assert(erase(&t, 0) && insert(&t, 99));
printf("Collision chain: 10 at %zu, 31 at %zu, 24 at %zu\n",
locate(&t, 10), locate(&t, 31), locate(&t, 24));
Table negatives = {{{0, EMPTY}}};
assert(insert(&negatives, INT_MIN) && insert(&negatives, INT_MAX));
assert(locate(&negatives, INT_MIN) != CAP && locate(&negatives, INT_MAX) != CAP);
Table tombstones = {{{0, EMPTY}}};
for (int i = 0; i < CAP; ++i) assert(insert(&tombstones, i));
for (int i = 0; i < CAP; ++i) assert(erase(&tombstones, i));
assert(locate(&tombstones, 99) == CAP);
assert(insert(&tombstones, 99) && locate(&tombstones, 99) != CAP);
puts("hashing tests passed");
return 0;
}