Rehashing in Hashtable

Question

I have a question about rehashing. As far as i know, when the load factor (number of elements in the table / size of table) reaches 0.5, we use rehashing and by rehashing, we expect to decrease collisions. I am pretty sure that rehashing can be used while doing quadratic probing, and my question is, should can rehashing be used with linear probing, or separate chaining? Is there any logic of using rehash while doing separate chaining, or linear probing?

Thanks

Solution

Generally we do re-hashing when hashtable is filles beyond certain number-Load Factor, as you have explained. While doing re-hash, we increase the size of hashtable and do the re-hashing. Rehashin is not about using alternative hashing strategy its about rehashing into new sized hashtale(with old/new strategy)

It's up to you which collision handling strategy to use. Generally people go for closed hashing.We can use separate chaining also but it is used for only for unknown and known sizes but open addressing is used for known sizes .So if the size is known mostly we prefer open addressing to avoid data wastage.