Why only use primes for Hash function division method
hash, modulo
Solution
All data in the computer is stored as binary data. A binary number is written in base-2.
If you hash data, you want to create a fingerprint that is easy comparable. If we have similar data that is not exactly the same as the original data, it shouldn't create the same fingerprint (hash).
Guess what happens if you use an m where `m = 2^p (p is int >= 0)`. Because 2^7 is a multiple of 2^4 for example, all bits left from 2^4 will be reduced to 0. You cut off part of the data. This means that if the data is different in the left-most bits of the binary number, they will create the same hash.
Example:
k: 1111111111010101
m: 0000000001000000 (2^6)
k(m): 0000000000010101
Now do the same for this:
k: 0000000000010101
m: 0000000001000000 (2^6)
k(m): 0000000000010101
Hey, that is the same hash! This is exactly the reason why a number far from 2^p is chosen. This way the left-most bits do matter in calculating the hash, and it is far less likely that two similar pieces of data create identical hashes.
Problem
Hashing using division method means h(k) = k mod m . I read that m should not be power of 2. This is because if m = 2^p, h becomes just the p lowest-order bits of k. Usually we choose m to be a prime number not too close to a power of 2. Could someone explain with a small example the lowest order bits part? I thought all (mod m) does is that it wraps the result around a range m. Somehow cant see the issue if m was power of 2.