Data Structures Hash Tables

Question 1

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

Accepted Answer

O(1)

Answer

O(n)

Answer

O(log n)

Answer

O(n log n)

Question 2

What is a collision in a hash table?

Accepted Answer

Two different keys hashing to the same bucket index

Answer

Two identical keys inserted simultaneously

Answer

A hash function returning a negative value

Answer

The table exceeding its capacity limit

Question 3

Which collision resolution strategy stores multiple colliding entries in a linked list at each bucket?

Accepted Answer

Separate chaining

Answer

Open addressing

Answer

Linear probing

Answer

Robin Hood hashing

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

Searching buckets in reverse order

Answer

Jumping by a fixed prime offset on collision

Answer

Rehashing with a secondary hash function

Question 5

What is the load factor of a hash table?

Accepted Answer

The ratio of stored entries to total bucket count

Answer

The number of buckets times the number of keys

Answer

The maximum chain length in separate chaining

Answer

The number of collisions divided by inserts

Question 6

Why is the worst-case time complexity of hash table lookup O(n)?

Accepted Answer

All keys hash to the same bucket, creating a single chain of length n

Answer

The hash function always produces the same value

Answer

The table must be fully scanned on each lookup

Answer

Hash tables don't support lookup operations