Questions: Hash Tables

Question 1

A hash table has 10 slots and currently holds 9 items (load factor = 0.9). What is the most accurate characterization of its performance risk?

• A. O(1) is still guaranteed because the hash function is deterministic
• B. The high load factor increases collision probability, risking O(n) operations if collisions cluster
• C. Performance is unaffected; only the hash function quality matters, not the load factor
• D. The table must immediately resize or all insert operations will fail

Answer: (B)

Load factor measures how full the table is. As load factor approaches 1, collisions become frequent even with a good hash function — many keys compete for few slots. In chaining, long lists form; in open addressing, many probe steps are needed. Most implementations resize (typically by doubling) when load factor exceeds a threshold (often 0.7–0.75) to keep average-case O(1) realistic.

Question 2

Hash tables generally preserve the insertion order of keys.

• T. True
• F. False

Answer: False

In most hash table implementations, keys are placed at array indices determined by their hash values, not insertion order, so retrieval order is unpredictable. Python 3.7+ dicts happen to preserve insertion order as an implementation detail (now part of the language spec), but this is an exception — not a property of hash tables in general. Relying on hash table ordering in other languages (Java's HashMap, C++ unordered_map) is a bug.

Question 3

Why is worst-case O(n) lookup possible in a hash table even when the hash function is perfectly uniform on average?

Model answer: An adversary (or unlucky input) can supply keys that all hash to the same slot. With chaining, that slot's linked list grows to length n, and lookup must scan the entire list. With open addressing, the probe sequence degrades similarly. Uniform average-case performance assumes keys are effectively random with respect to the hash function — a condition that does not hold for adversarial or poorly distributed inputs.

This is why cryptographic hash functions or randomized hash functions (like universal hashing) are used in security-sensitive contexts: an attacker who knows the hash function can craft inputs that cause O(n) behavior, a technique called hash flooding. Python uses randomized hash seeds at startup (since 3.3) to prevent this attack.