Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
