Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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$.

share|improve this question

migrated from cstheory.stackexchange.com Nov 1 '12 at 20:47

This question came from our site for theoretical computer scientists and researchers in related fields.

4  
The question as stated is unclear. –  Yuval Filmus Oct 26 '12 at 4:58

1 Answer 1

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.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.