Question

Which of the following scenarios leads to linear running time for a random search hit in a linear-probing hash table?

(a) All keys hash to same index

(b) All keys hash to different indices

(c) All keys hash to an even-numbered index

(d) All keys hash to different even-numbered indices

The question was posed to me in an internship interview.

I'd like to ask this question from Hashing techniques topic in division Indexing and Hashing of Database Management

Answer 1

The correct choice is (a) All keys hash to same index

Easiest explanation - If all keys hash to the same location then the i-th inserted key would need i lookups to be found. The probability of looking up i-th key is 1/n (since it’s random). If you know some probability it’s trivial to show that such lookups have linear time.