Question

What is the best case and worst case performance for a hashtable lookup explain answer very clearly and answer must be explained how hashtables work and how that relates to performance in both the cases.

Answer 1

When we searching for any particular value it will compute the hash for that value and finds the bucket number using that value and checks if that bucket contains the value if Yes than it will return If no it will move to next node from that bucket and search it.. it will keep on searching in that chain from that bucket.. here I am taking separate chaining method as the example

So Coming to the performence here if we found the element in the bucket it self directly than that is the best case which is O(1)

if we dont find in that bucket than we need to search all elements in that list so if we found element in the end of list than that is the worst case which is O(N)

Please find the image below to understand clearly

In the above diagram 1,10 are best cases and 5 ,50 are worst cases

NOTE : PLEASE COMMENT BELOW IF YOU HAVE CONCERNS.

I AM HERE TO HELP YOUIF YOU LIKE MY ANSWER PLEASE RATE AND HELP ME IT IS VERY IMP FOR ME