Rehashing doubt

#1

how can i find prime no near 2*table size if i make prime seive it will be costly

#2

bhaaiya has taken an artbitary prime no which is neither too large nor to small in magnitutde

so u can take a decent prime no in order to get a good load factor at all time.
u do not have to go on implementing the prime sieve to find a no close to 2* tableSize

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#4

rehashing wiil occur when the load factor crosses a certain value if once rehashing has done then if again some entries is ;oad factor crosses so i have written the rehash fn for a perticular prime no how it will work then

#5

@deepakjumani09
Hi, so i was going through some of the video i realised that the prime no is near 2*tableSize and yes if u need to programmatically choose the value then u will have to implement the prime sieve

#6

@deepakjumani09
So yeah , these are your only two choices.

  1. You can precompute the primes using prime sieve. It will take a precomputation and not advisable if rehashing doesn’t occur often.
  2. When you rehash, start iterating forwards from 2*table_size and iterate till you hit a prime number ( check using the O(sqrt(n)) method. Advisable if there are very few rehashings but not at all advisable if the rehashings are occuring frequently.

Since the frequency of hashing depends upon your load factor ratio and the values you are putting in and the choice of your base prime number , it cannot be said for certain which method is better for all situations. It will depend on the situation.
Choose one of the above as per your need.