Confusion on hash table efficiency?
I am confused on the efficiency of hash tables. Say my hash table has a size of 200 and I store 150 objects inside. Using linear probing to deal with collisions, I'll be rehashing a lot to find an empty space. Now after increasing the size of the hash table to reduce collision, wouldn't it be harder to search for an element since the hash function will no longer hash to the same value thus elminating the point for using hash tables (my hash function uses tablesize so hash value will be different)?
More Questions From This User See All
Answers & Comments
When you increase the size, you will need to "add all the elements" of the first table into the new table. So the actual change will be an expensive (order N) operation, but it will be an amortized cost due to the efficiency it gives.