Data Structures Hash Tables

Question 1

What is the average time complexity of lookup in a hash table?

Accepted Answer

O(1)

Answer

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?

Accepted Answer

Two different keys hashing to the same bucket index

Answer

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?

Accepted Answer

Separate chaining

Answer

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?

Accepted Answer

On collision, scanning sequentially (index+1, +2, ...) until an empty slot is found

Answer

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?

Accepted Answer

The ratio of stored entries to total bucket count

Answer

Load factor = (number of entries) / (number of buckets); a high load factor increases collision probability and degrades performance.

Data Structures Practice Test