1
$\begingroup$

I am implementing a hash table that may need to grow and shrink as the number of stored keys varies. I have a hashcode function that uniformly hashes keys to positive 32-bit integers. The table itself will use a smaller array of approximate size M.

If I wanted to use the hash function to produce a value between 0 and P-1 (if P is close to M), can I use mod P if P is a power of 2?

What about using mod P, where P is a prime?

$\endgroup$
2
$\begingroup$

The exact size of the backing array is not that important only that it can hold enough buckets.

The reason why power of 2 is often used is because this can be implemented as a bitmask instead of a integer divide. Integer divides are pretty slow compared to other operation so they are often avoided by people trying to optimize data structures.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Alright. So would power of 2 be appropriate for the hash table described above? $\endgroup$ – TheSaviour Sep 22 '17 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.