Computer Algorithms II Lecture Notes

23 September 2008 • Implementing Hash Tables


According to Knuth (The Art of Computer Programming, Vol. 3, Section 6.4), B should be a value which does not divide the values ri ± a, where a and i are small numbers and r is the radix of the chunk-size used to generate the key k (that is, if the key was generated from a sequence of bytes, r = 28 = 256). To avoid division, chose B to be a prime number such that (ri ≡ ±a) mod B.


This page last modified on 24 January 2006.