Hash Codes (cont.) Polynomial accumulation:
■ We partition the bits of the key into a sequence of components of fixed length (e.g., 8, 16 or 32 bits) ao a₁ an-1 ***
■ We evaluate the polynomial p(z)= a + a₁z + a₂z² + ... + a₁-12-1 at a fixed value z, ignoring overflows Especially suitable for strings (e.g., the choice z = 33 gives at most 6 collisions on a set of 50,000 English words) a Polynomial p(z) can be evaluated in O(n) time using Horner's rule: .
The following polynomials are successively computed, each from the previous one in 0(1) time Po(z)=an-1 Pi(z)=an-i-1+zPi-1(z) (i=1,2,..., n-1) We have p(z) =Pn-1(z)