06 Hash Tables

From keys to table positions

A hash table stores key–value pairs in an array. To place or find a key, the table applies a hash function and converts the resulting hash code into a valid slot, often with

where $m$ is the number of slots.

For example, with $10$ slots and $h(k)=k$, key $42$ initially maps to slot $2$, since $42\bmod 10=2$. This mapping is not necessarily unique: different keys may produce the same index.

A good hash function has four important properties:

• Deterministic: the same key produces the same hash value during a table operation.

• Fast: computing the hash does not dominate lookup cost.

• Well distributed: unrelated keys are spread across the table rather than clustered.

• Consistent with equality: equal keys must have equal hash values.

Data-structure hashing prioritizes speed and distribution. It is not necessarily cryptographic hashing, which additionally aims to resist intentional attacks and make inputs difficult to recover or manipulate.

The expected $O(1)$ cost often associated with a hash table depends on these properties and on maintaining a suitable load factor. It is not a worst-case guarantee.

Takeaway: Hashing provides a fast route from a key to a likely table position, but it does not guarantee a unique position.

Collisions and resolution strategies

A collision occurs when distinct keys map to the same index. For a table with $10$ slots, keys $12$ and $42$ collide because

Collisions are unavoidable when many possible keys are mapped into a finite array. The table must therefore choose a collision-resolution strategy. The two central approaches are separate chaining and open addressing.

The distinction is where colliding entries are stored:

• In separate chaining, a slot refers to a collection of entries.

• In open addressing, all entries remain in the main array and the algorithm probes other slots.

A hash match is not proof that two keys are equal. After locating a candidate slot or entry, the implementation must compare the keys themselves.

Takeaway: A hash table is effective not because collisions disappear, but because it handles them efficiently.

Separate chaining

Separate chaining gives each table slot a collection, often a linked list. If several keys map to index $2$, they can appear in that slot's chain in sequence, such as $(12,A)$, $(42,B)$, and $(72,C)$.

For lookup, the table computes the index, traverses that chain, and compares keys until it finds the target or reaches the end. Insertion searches the chain first: an existing key normally has its value replaced, while a new key is added to the chain. Deletion removes the matching entry directly, without requiring a special marker.

If there are $n$ entries and $m$ chains, the load factor is

Here, $\alpha$ represents the average number of entries per chain and may be greater than $1$. Under a simple uniform-hashing assumption, expected search and update time is $\Theta(1+\alpha)$.

Advantages include straightforward deletion, the ability to store more entries than there are slots, and gradual performance degradation as chains grow. The trade-offs are extra memory for chain nodes or collections and potentially poor cache locality. A poor hash function can still create a chain of length $n$.

Takeaway: Chaining makes deletion simple and tolerates load factors above $1$, but long chains increase work.

Open addressing and probing

Open addressing stores every entry directly in the table array. After a collision, the algorithm follows a probe sequence to inspect alternative slots. Because an unsuccessful search must eventually encounter an empty slot, the load factor must satisfy

With linear probing, the probe positions are

for $i=0,1,2,\ldots$. The algorithm checks the initial position, then successive positions, wrapping around when it reaches the end of the array. This layout is cache-friendly, but occupied runs can form primary clustering, which increases later probe lengths.

Other strategies change how alternative positions are selected:

• Quadratic probing uses increasingly larger offsets, such as $h(k)+1^2$, $h(k)+2^2$, and so on.

• Double hashing uses a second hash function for the step size:

  $$p_i(k)=(h_1(k)+i\,h_2(k))\bmod m.$$

Deletion requires care. If a slot is simply cleared, a later search may stop there even though its target lies farther along the probe sequence. A tombstone marks the slot as previously occupied and tells searches to continue. Tombstones preserve correctness but may lengthen probes, so rebuilding can be useful.

Takeaway: Open addressing saves separate chain storage and can be cache-friendly, but it requires careful probing, deletion, and occupancy control.

Load factor, resizing, and rehashing

The load factor measures how full a table is:

where $n$ is the number of stored entries and $m$ is the table capacity. Its meaning depends on the collision strategy:

• With separate chaining, it is the average number of entries per chain and may exceed $1$.

• With open addressing, it is the fraction of occupied slots and must remain below $1$.

As $\alpha$ increases, collisions and search costs generally increase. For linear probing, probe counts can rise sharply as the table approaches full capacity. A lower load factor usually improves speed but uses more memory; a higher load factor saves memory but increases collision and probe costs.

A table typically resizes when $\alpha$ crosses a threshold. Resizing and rehashing means creating a larger array, recomputing each index using the new capacity, and reinserting every entry. Recomputing is necessary because changing $m$ changes the remainder. For instance, an entry mapped by $h(k)\bmod 8$ may move when the capacity becomes $16$.

If a capacity of $8$ has a threshold of $0.75$, the threshold count is $0.75\times 8=6$. Inserting a seventh entry may trigger growth to capacity $16$. One resize costs $O(n)$, but geometric growth spreads these costs across many insertions, giving amortized $O(1)$ insertion time.

Takeaway: Resizing trades occasional rebuilding work for shorter chains or probe sequences during ordinary operations.

Performance and when to choose a hash table

With a well-distributed hash function, a controlled load factor, and an appropriate collision strategy, the usual performance profile is:

• Search: expected $O(1)$; worst-case $O(n)$.

• Insert: expected amortized $O(1)$; worst-case $O(n)$, including possible resizing work.

• Delete: expected $O(1)$; worst-case $O(n)$.

• Resize: $O(n)$ when all entries are moved and reinserted.

The worst case can occur when many keys collide or when clustering creates long probe sequences. Performance is influenced by hash-function quality, load factor, collision strategy, equality checks, resizing policy, and adversarial input.

A hash table is a strong choice for dictionaries and maps, sets of unique values, caches, symbol tables, frequency counting, indexes, and membership tests when fast lookup by key is more important than sorted order. A balanced search tree is often preferable when the application needs sorted traversal, minimum or maximum operations, predecessor or successor queries, or guaranteed $O(\log n)$ worst-case operations.

Use the following decision rule:

1. Choose a hash table when direct key-based access and expected fast operations are the main goals.

2. Choose separate chaining when straightforward deletion, flexible occupancy, or gradual degradation is valuable.

3. Choose open addressing when compact storage and cache-friendly access are important and occupancy can be controlled.

4. Choose a balanced search tree when sorted order or guaranteed logarithmic worst-case operations are required.

Final takeaway: Hash tables offer expected constant-time key-based operations, but their performance depends on distribution, occupancy, collision handling, and resizing rather than on the name of the data structure alone.