Hashing under collisions and adversarial inputs

Prerequisites: Arrays, equality, modular arithmetic, and probability.

Learning objectives

• Trace chaining and linear probing.
• Explain load factor and tombstones.
• Separate hash equality from key equality.

A hash is an address suggestion

A hash table maps a key to a bucket or probe sequence. The hash is not normally a unique identifier for the key. Distinct keys can collide, so a lookup must compare the stored key for equality before returning its value. The table’s behavior depends on collision handling, capacity, load factor, and the relationship between the hash function and actual inputs.

With separate chaining, each bucket stores a collection of entries. For m buckets and n keys, load factor α=n/m is the average bucket size. Under an appropriate uniform-distribution model, expected successful or unsuccessful lookup work is O(1+α), plus key hashing and equality costs. A long string can make those latter operations significant even when only one bucket is examined.

Trace an open-addressed table

In linear probing, a key starts at h(key) and scans successive slots modulo capacity until it finds the key or an available position. Use capacity 7 and h(k)=k mod 7. Insert keys 10,17,24, then 11. They occupy slots 3,4,5,6 respectively. The keys with home slot 3 form a cluster; key 11, whose home slot is 4, joins it.

Deleting 17 cannot simply turn slot 4 into a never-used empty slot. A search for 24 beginning at slot 3 could stop at slot 4 and incorrectly report absence. A tombstone marks a deleted slot that preserves the search path. Insertions can reuse tombstones, but lookups must continue through them. Periodic rebuilding removes accumulated tombstones and restores probe efficiency.

A lookup for absent key 31 starts at 3, examines the cluster, and stops at the first genuinely empty slot, 0. Keeping an empty slot reachable and controlling occupancy matter. As the table approaches full capacity, probes become long even without a malicious input distribution. The simple chaining bound O(1+α) should not be transferred unchanged to linear probing.

The probability model is part of the contract

Expected bounds can rely on random selection of a hash function or assumptions about inputs. An attacker who can choose many colliding keys may cause long chains or probes in a predictable implementation. Randomized hashing reduces some attacks, while worst-case guarantees may require another structure or fallback. None of this removes the need to compare keys correctly.

Choose capacity growth, deletion behavior, and iteration semantics explicitly. Rehashing can invalidate stored pointers or change iteration order. If a product needs sorted range queries, a hash table’s fast equality lookup does not supply that capability. Implement the small trace yourself, then compare it with the hashing chapter in Open Data Structures. The important exercise is to explain each continuation or stopping decision using the table’s invariants.

Practice problem

Use linear probing with seven slots and h(k)=k mod 7. Insert 3,10,17,4. Delete 10 using a tombstone. Trace lookup of 17 and insertion of 24, stating whether the insertion may stop immediately at the tombstone. Finally explain why replacing the tombstone with an ordinary empty slot would be incorrect.

Worked solution

The first four insertions occupy slots 3,4,5,6. Deleting 10 leaves a tombstone at 4. Lookup of 17 checks 3, passes the tombstone at 4, and succeeds at 5. Inserting 24 can remember slot 4 as the first reusable slot, but it must continue the probe far enough to ensure that key 24 is not already present later in the cluster. When it reaches a never-used empty slot, it can insert at remembered slot 4. Clearing slot 4 as ordinary empty would cause lookup of 17 to terminate before reaching its stored entry, violating the lookup invariant.

Check your understanding

Distinct keys k1 and k2 have the same hash and occupy the same bucket. What must a correct dictionary lookup do?

• Compare actual keys among collision candidates.
• Compare only the stored values.
• Reject insertion of k2 because the hash function is invalid.
• Return the first entry because equal hashes identify equal keys.

Explanation

Hash equality selects candidates; key equality determines which mapping is requested.

Linear probing has 10 at slot 3, a tombstone at 4, and 24 at 5. Both keys hash to 3. What happens if lookup 24 treats the tombstone as an unused empty slot?

• It falsely reports 24 absent by stopping before slot 5.
• It correctly finds 24 by binary search.
• It returns 10 because hashes must be unique.
• It merely takes one extra probe without changing correctness.

Explanation

A tombstone preserves the search path through a cluster. A never-used empty slot can terminate search, but a deleted slot generally cannot.

Primary reading

• Open Data Structures: Pat Morin, open textbook

Open the study and save your work →