Data Structures Hash Tables 1 — Questions and Answers
Question 1: What is the average time complexity of lookup in a hash table?
- O(n)
- O(log n)
- O(1) (Correct answer)
- O(n log n)
Correct answer: O(1)
With a good hash function and low load factor, hash table lookups are O(1) on average because the key maps directly to a bucket.
Question 2: What is a collision in a hash table?
- Two identical keys inserted simultaneously
- Two different keys hashing to the same bucket index (Correct answer)
- A hash function returning a negative value
- The table exceeding its capacity limit
Correct answer: Two different keys hashing to the same bucket index
A collision occurs when two distinct keys produce the same hash value, mapping them to the same bucket and requiring a resolution strategy.
Question 3: Which collision resolution strategy stores multiple colliding entries in a linked list at each bucket?
- Open addressing
- Linear probing
- Separate chaining (Correct answer)
- Robin Hood hashing
Correct answer: Separate chaining
Separate chaining attaches a linked list (or other structure) to each bucket, storing all colliding keys in that list.
Question 4: What is linear probing in the context of open addressing?
- Searching buckets in reverse order
- On collision, scanning sequentially (index+1, +2, ...) until an empty slot is found (Correct answer)
- Jumping by a fixed prime offset on collision
- Rehashing with a secondary hash function
Correct answer: On collision, scanning sequentially (index+1, +2, ...) until an empty slot is found
Linear probing resolves collisions by sequentially checking the next bucket until an empty slot is found, keeping all entries in the main array.
Question 5: What is the load factor of a hash table?
- The number of buckets times the number of keys
- The ratio of stored entries to total bucket count (Correct answer)
- The maximum chain length in separate chaining
- The number of collisions divided by inserts
Correct answer: The ratio of stored entries to total bucket count
Load factor = (number of entries) / (number of buckets); a high load factor increases collision probability and degrades performance.
Question 6: Why is the worst-case time complexity of hash table lookup O(n)?
- The hash function always produces the same value
- All keys hash to the same bucket, creating a single chain of length n (Correct answer)
- The table must be fully scanned on each lookup
- Hash tables don't support lookup operations
Correct answer: All keys hash to the same bucket, creating a single chain of length n
In the worst case (e.g., a poor hash function or adversarial keys), all n entries collide into one bucket, degrading lookup to O(n) list search.
Data Structures Hash Tables 1
What is the average time complexity of lookup in a hash table?