CODEWITHSUNDEEP
hashtable
Matan Wiesner
Matan Wiesner

Reputation: 186

Hash table understading

I understand that in I have a hash table with m cells and n elements, the search cost O(n/m) (by average) Let's look about two sub-algorithms of using a hashtable: A. When you have n elements, insert them to a hashtable with m=100 and use it to search element. B. When you have n elements, insert them to a hashtable with m=n/3 and use it to search element.

In case A the complexity of the search is O(n/100)=O(n) In case B the complexity of the search is O(n/(n/3))=O(1) THat means that if we want to use hashtable that search element in O(1) complexity , we must know the number of elements when we create the hashtable, calculate the m by dividing n by a constant and pass to the constructor of the set the m

Am I right? Must I pass the m in the constructor of my hashtable to use the benefit of hash table?

Upvotes: 0

Views: 36

Answers (1)

Matan Wiesner
Matan Wiesner

Reputation: 186

The answer is, as I learned from the comments above, is that most implementations automatically adjust hashtable size, so m is always something like n..2n. When the number of elements becomes too large for the current m, the greater hashtable is allocated It means that add to hashtable can be in worst case O(n) (because the greater hashtable is allocated) but in amortized it is O(1), like adding an element to ArrayList

Upvotes: 0

Related Questions