7 Hash Tables

How Hash Tables Locate Keys

A Hash table stores associations such as student IDs mapped to names. Its main components are:

• An array of buckets or slots.

• A Hash function that converts each key into an integer hash value.

• A collision-resolution strategy for keys that receive the same location.

For a table with $m$ buckets and a key $k$, the table commonly computes an index using:

A lookup computes the hash value, selects the corresponding bucket or slot, examines candidate entries, and confirms the match using key equality. The equality check matters because a hash value does not prove that two keys are equal. Equal keys must have equal hash values, while unequal keys are allowed to collide.

Keys should remain effectively immutable while stored. If changing a key changes its hash value, the entry may remain in its original location while future searches look elsewhere.

Takeaway: Hashing narrows the search to a location, but equality checking establishes the actual key match.

Collision Resolution Strategies

A Collision occurs when different keys are assigned to the same bucket or slot. Collisions are expected because the set of possible keys is usually much larger than the number of table positions.

Two major strategies handle collisions:

• Separate chaining stores all entries assigned to one bucket in a chain or other collection. Searching scans that collection, insertion adds or updates an entry, and deletion removes the matching entry.

• Open addressing stores entries directly in the table array. After a collision, the table examines alternative positions in a probe sequence.

For a chained table, an average bucket may contain several entries. For an open-addressed table, the probe sequence must find an available slot, so the table must retain empty positions.

Takeaway: Collision resolution is a normal part of hash-table design, not an error condition.

Load Factor and Table Occupancy

The Load factor is defined as:

Here, $n$ is the number of stored entries and $m$ is the number of buckets or slots.

Its interpretation depends on the collision strategy:

• In separate chaining, it is the expected average number of entries per bucket. A bounded load factor supports expected search time of $O(1 + \alpha)$.

• In open addressing, it is the fraction of occupied slots. The load factor must remain below $1$, because probing requires available positions.

A lower load factor usually improves lookup time but uses more memory. A higher load factor saves space while increasing chain lengths or probe lengths. Many practical implementations use a threshold near $0.75$ as a time–space compromise, although the exact threshold is implementation-specific.

Takeaway: Controlling the load factor helps preserve fast operations.

Probing and Deletion

Open addressing uses a probe sequence after a collision. Linear probing checks consecutive positions:

It is straightforward and often cache-efficient, but it can create primary clustering, where occupied runs grow and cause later operations to perform more probes.

Quadratic probing uses increasingly larger offsets:

This can reduce primary clustering, although different keys may still follow related patterns. Double hashing uses a second hash function to determine the step size:

Deletion requires special care. Removing an entry and leaving an ordinary empty slot could make a later search stop before reaching a key farther along the probe sequence. A Tombstone marks a deleted position while instructing searches to continue. Accumulated tombstones increase probing costs, so rebuilding or resizing can remove them.

Takeaway: Probe design affects clustering, and deletion markers preserve search correctness.

Resizing and Performance

As entries accumulate, a table may exceed its chosen load-factor threshold. It then allocates a larger array and performs Rehashing:

1. Create a larger table, often with about twice the previous capacity.

2. Visit every existing entry.

3. Recompute each entry's bucket or probe position using the new capacity.

4. Insert the entries into the new table.

5. Replace the old table.

An entry usually cannot simply keep its old numerical index because the calculation based on $hash(key) \bmod m$ may change when $m$ changes.

One resize costs $O(n)$ for $n$ entries. However, if capacity grows geometrically, the cost is distributed across many insertions. Consequently, insertion is expected to be amortized $O(1)$, even though one insertion that triggers a resize can cost $O(n)$.

With a good hash function, controlled load factor, and effective collision handling, search, insertion, and deletion are expected $O(1)$. Their worst-case time is generally $O(n)$, which can occur when many keys collide or probe sequences become long. A hash table is preferable when fast average-case membership or key–value access matters more than sorted iteration, predecessor queries, or guaranteed logarithmic worst-case performance.

Takeaway: Hash tables trade ordered operations and guaranteed worst-case bounds for fast expected access, with geometric resizing preserving efficient insertion over a sequence of operations.