Data Structures Hash Tables 2

Question 1

What triggers rehashing in a hash table?

Accepted Answer

When the load factor exceeds a threshold (commonly 0.75)

Answer

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?

Accepted Answer

Using a secondary hash function to determine the probe step size on collision

Answer

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?

Accepted Answer

Two Sum: finding two indices that add to a target

Answer

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?

Accepted Answer

A hash set stores only unique keys with no associated values; a hash map stores key-value pairs

Answer

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?

Accepted Answer

Avalanche effect

Answer

The avalanche effect means that a small change in input (even one bit) causes a drastically different hash output, preventing clustering of similar keys.

Data Structures Practice Test

Data Structures Practice Test

Data Structures Hash Tables 2