1.4.2 - Hash tables and collision handling

Use a key to choose a home location

A hash table stores records for retrieval by key. A key identifies an entry, such as an equipment number; its associated value might be the equipment's description. A hash function maps that key to a table index. The index is a starting location, not proof that the matching record is there.

For a table with seven slots indexed 0–6, use the deliberately simple function $h(k)=k\bmod7$ for integer keys. Key 10 has home index 3, because 10 divided by 7 leaves remainder 3. Keys 17 and 24 also map to 3.

Creation allocates a stated positive number of slots and gives each an empty state. Before choosing operations, specify the key type, hash function, capacity, collision method, empty/deleted markers and duplicate policy. Here keys are unique integers, and inserting a key already present replaces its value without creating another entry. We compare stored keys to establish equality; matching just the hash index is insufficient.

Hash-table indexing and cryptographic hashing have different purposes. This remainder function is for a small storage example; it provides no password protection or collision resistance. A good storage hash aims to spread the application's keys across available positions. Collisions remain possible whenever many possible keys share a finite set of indices.

Keep colliding records in a bucket

Separate chaining stores a collection of entries at each table index. Compute the key's home index, then inspect the entries in that bucket. A linked list is one implementation; a dynamic list is another. Colliding records stay in the same bucket instead of moving to another table slot.

With five buckets, insert (8,"lamp"), (18,"stand"), (4,"lens"). Bucket 3 contains the first two records; bucket 4 contains the third. Search for 18 computes index 3 then compares 8 and 18. Search for 13 scans bucket 3 and fails after its last entry. Deleting 8 removes only its record, so 18 remains reachable in the bucket. Repeating key 18 with value "tripod" updates that one entry, following our duplicate-key policy.

The Python representation below uses a list of distinct lists. [[]] * size would repeat references to one shared list, so adding to one bucket would appear in every bucket. The comprehension creates separate bucket objects.

def make_buckets(size):
    if size <= 0:
        raise ValueError("size must be positive")
    return [[] for _ in range(size)]

def chain_put(buckets, key, value):
    bucket = buckets[key % len(buckets)]
    for index, (stored_key, stored_value) in enumerate(bucket):
        if stored_key == key:
            bucket[index] = (key, value)
            return
    bucket.append((key, value))

def chain_find(buckets, key):
    for stored_key, value in buckets[key % len(buckets)]:
        if stored_key == key:
            return True, value
    return False, None

def chain_delete(buckets, key):
    bucket = buckets[key % len(buckets)]
    for index, (stored_key, value) in enumerate(bucket):
        if stored_key == key:
            bucket.pop(index)
            return True
    return False

buckets = make_buckets(5)
for key, value in [(8, "lamp"), (18, "stand"), (4, "lens")]:
    chain_put(buckets, key, value)
chain_delete(buckets, 8)
chain_put(buckets, 18, "tripod")
print(chain_find(buckets, 18))

The output is (True, 'tripod'). A found Boolean separates an absent key from a stored value of None. The operations assume buckets created by make_buckets, valid integer keys and well-formed entry pairs. Finding or deleting an absent key scans its bucket and returns false; an empty bucket simply has no comparisons. Chaining can store more records than the number of buckets if its collections can grow, though memory is still finite.

Resolve a collision by probing other slots

Open addressing stores each entry in a table slot. Linear probing tries the home slot, then the next slot, wrapping to index 0 after the final index. For capacity $m$, probe offset $i$ uses $(h(k)+i)\bmod m$. An operation must be bounded to at most $m$ probes so a full table cannot loop forever.

With seven initially never-used slots and h(k)=k mod 7, insert keys 10, 17, 24, 6. Key 10 occupies 3. Key 17 tries 3 then 4. Key 24 tries 3, 4 then 5. Key 6 occupies 6. The final states are:

Insertion needs three slot states: never used (None), occupied (a key/value pair), and previously used but deleted (a distinct marker). For a new key, a deleted slot can be reused. However, do not insert there immediately: the same key might already occur later in its probe sequence. Remember the first deleted position, continue to check for an existing key, then use the remembered position when absence is established at a never-used slot or after a complete cycle.

DELETED = object()

def put(table, key, value):
    size = len(table)
    if size == 0:
        raise ValueError("table must have positive capacity")
    first_deleted = None
    for offset in range(size):
        index = (key % size + offset) % size
        entry = table[index]
        if entry is DELETED:
            if first_deleted is None:
                first_deleted = index
        elif entry is None:
            destination = index if first_deleted is None else first_deleted
            table[destination] = (key, value)
            return True
        elif entry[0] == key:
            table[index] = (key, value)
            return True
    if first_deleted is not None:
        table[first_deleted] = (key, value)
        return True
    return False

Start with table = [None] * 7; sharing the immutable None sentinel is safe. True means the insertion/update was accepted, not necessarily that a new slot was occupied. A fully occupied table can still update an existing key. For an absent key with no reusable slot, return false and leave the table unchanged. This routine does not resize automatically. It assumes valid integer keys, occupied entry pairs and the same DELETED object used by deletion.

Preserve a probe chain when searching and deleting

Search must follow the same probe sequence as insertion. A matching occupied key is found. A different occupied key or a deleted marker means continue. A never-used slot means absent: if the key had been inserted along this sequence, insertion would have used an available earlier position rather than passing this never-used slot. After a complete cycle with no match, the key is also absent.