Search Complexity of a Hashtable within a Hashtable?
- by spacker_lechuck
Say we have a hashtable of size m, and at each bucket we store a hashtable of size p.
What would the worst case/average case search complexity be?
I am inclined to say that since computing a hash function is still atomic, the only worst case scenario is if the value is at the end of the linked list in the hashtable of size p, so O(n)?
I have no idea how to calculate the average case for this scenario and would appreciate any pointers!