0

I've looked into a lot of questions on this site about whether one should use prime number or power of 2 for mod. Thankfully, I understood the idea

However, my situation is different. I couldn't find any question that dealt with the right array size when resizing hash tables.

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. So which of the following is best choice for the hash function that takes the hashcode to produce a value between 0 and P-1 where P is close to M?

a) Modulo P where P is a prime closest to M

b) Modulo P where P is the power of 2 closest to M

c) Either

d) Neither

I've been trying to figure this out for hours, but with no luck.

TheSaviour
  • 61
  • 1
  • 7
  • If you understood the choice between prime number or power of two, as you claimed in the first paragraph, you should be able to answer the question yourself, as this decision *is* the answer. It’s not clear though, why you want to use a different array size than the parameter to the modulo function or what “approximate” is supposed to mean in a programming context. – Holger Sep 26 '17 at 09:33
  • https://stackoverflow.com/q/15437345/2235885 – joop Oct 03 '17 at 11:22

0 Answers0