Data Structures Hash Tables 2 — Questions and Answers
Question 1: What triggers rehashing in a hash table?
- Any insertion operation
- When the load factor exceeds a threshold (commonly 0.75) (Correct answer)
- When a collision occurs
- When a deletion creates empty slots
Correct answer: When the load factor exceeds a threshold (commonly 0.75)
Most hash table implementations rehash (resize and redistribute all entries) when the load factor exceeds a threshold like 0.75 to maintain O(1) average performance.
Question 2: What is double hashing in open addressing?
- Using two separate hash tables for redundancy
- Using a secondary hash function to determine the probe step size on collision (Correct answer)
- Hashing the key twice to increase security
- Storing each key in two separate buckets
Correct answer: Using a secondary hash function to determine the probe step size on collision
Double hashing uses a secondary hash function to compute the step size for probing, reducing clustering compared to linear or quadratic probing.
Question 3: Which problem can be solved optimally using a hash map to track complement pairs?
- Finding the longest increasing subsequence
- Two Sum: finding two indices that add to a target (Correct answer)
- Detecting cycles in a linked list
- Computing the shortest path in a graph
Correct answer: Two Sum: finding two indices that add to a target
For Two Sum, store each number and its index in a hash map; for each new number, check if its complement (target - number) is already in the map in O(1).
Question 4: What is the purpose of a hash set compared to a hash map?
- A hash set stores key-value pairs; a hash map stores only keys
- A hash set stores only unique keys with no associated values; a hash map stores key-value pairs (Correct answer)
- A hash set uses open addressing; a hash map uses chaining
- A hash set is ordered; a hash map is unordered
Correct answer: A hash set stores only unique keys with no associated values; a hash map stores key-value pairs
A hash set tracks membership — just unique keys — while a hash map associates each unique key with a value.
Question 5: Which hash function property ensures similar inputs produce very different outputs?
- Uniformity
- Avalanche effect (Correct answer)
- Determinism
- Idempotency
Correct answer: Avalanche effect
The avalanche effect means that a small change in input (even one bit) causes a drastically different hash output, preventing clustering of similar keys.
Question 6: How does a Bloom filter differ from a hash table?
- A Bloom filter stores exact key-value pairs
- A Bloom filter uses multiple hash functions with a bit array to test membership with possible false positives but no false negatives (Correct answer)
- A Bloom filter is slower but more space-efficient
- A Bloom filter sorts keys during insertion
Correct answer: A Bloom filter uses multiple hash functions with a bit array to test membership with possible false positives but no false negatives
A Bloom filter uses k hash functions to set bits in a bit array; it can report false positives (saying a key is present when it isn't) but never false negatives.
Data Structures Hash Tables 2
What triggers rehashing in a hash table?