Cyclic Polynomial
Hashing by cyclic polynomial—sometimes called Buzhash—is also simple, but it has the benefit of avoiding multiplications, using barrel shifts instead. It is a form of tabulation hashing: it presumes that there is some hash function from characters to integers in the interval . This hash function might be simply an array or a hash table mapping characters to random integers. Let the function be a cyclic binary rotation (or barrel shift): it rotates the bits by 1 to the left, pushing the latest bit in the first position. E.g., . Let be the bit-wise exclusive or. The hash values are defined as
where the multiplications by powers of two can be implemented by binary shifts. The result is a number in .
Computing the hash values in a rolling fashion is done as follows. Let be the previous hash value. Rotate once: . If is the character to be removed, rotate it times: . Then simply set
where is the new character.
Hashing by cyclic polynomials is strongly universal or pairwise independent: simply keep the first bits. That is, take the result and dismiss any consecutive bits. In practice, this can be achieved by an integer division .
Read more about this topic: Rolling Hash