In hash tables, how many traversal of links does a successful search require?

Category: QuestionsIn hash tables, how many traversal of links does a successful search require?
Editor">Editor Staff asked 4 weeks ago

In hash tables, how many traversal of links does a successful search require?
 
(a) 1+⅄
 
(b) 1+⅄^2
 
(c) 1+ (⅄/2)
 
(d) ⅄^3
 
My query is from Hash Tables topic in portion Hash Tables of Data Structures & Algorithms I
 
I had been asked this question by my school principal while I was bunking the class.

1 Answers
Editor">Editor Staff answered 4 weeks ago

Right option is (c) 1+ (⅄/2)
 
Explanation: A successful search requires about 1+ (⅄/2) links to be traversed. There is a guarantee that at least one link must be traversed.