This is a textbook based question. In The Art of Computer Programming Volume 3, Knuth says that for a hash function $h(k) = k \bmod M$, $M$ should not be a multiple of $3$.

The explanation given is:

If keys are alphabetic, two keys that differ only by permutation of letters would differ in numeric value by a multiple of 3. This occurs because $2^{2n} \bmod 3 = 1$ and $10^{n} \bmod 3 = 1$)."

I'd be grateful, if someone can clarify why this is so, and how that equation is connected to alphabetical keys and $M$ being a power of $3$.

  • 4
    $\begingroup$ The question as stated is unclear. $\endgroup$ – Yuval Filmus Oct 26 '12 at 4:58

Observe that $2^{2n} = 4^n \equiv 1^n\equiv 1 \mod 3$ and $10^n \equiv 1^n\equiv 1 \mod 3$. The relevance of $2^{2n}$ is that exchanging two characters (stored in bytes with even numbers of bits) amounts to multiplying one part of a key by $2^{2n}$ for some $n$, and dividing another part by a like amount. (Also note, powers of 3 ($3^k$ for some $k$) are multiples of 3 ($3\cdot m$ for some $m$ if $k>0$) but multiples of 3 are much more common than its powers.)

| cite | improve this answer | |

Your Answer

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