A rolling hash (also known as recursive hashing or rolling checksum) is a hash function where the input is hashed in a window that moves through the input. A few hash functions allow a rolling hash to be computed very quickly—the new hash value is rapidly calculated given only the old hash value, the old value removed from the window, and the new value added to the window—similar to the way a moving average function can be computed much more quickly than other low-pass filters; and similar to the way a Zobrist hash can be rapidly updated from the old hash value. One of the main applications is the Rabin–Karp string search algorithm, which uses the rolling hash described below. Another popular application is the rsync program, which uses a checksum based on Mark Adler's adler-32 as its rolling hash. Low Bandwidth Network Filesystem (LBFS) uses a Rabin fingerprint as its rolling hash. FastCDC (Fast Content-Defined Chunking) uses a compute-efficient Gear fingerprint as its rolling hash. At best, rolling hash values are pairwise independent or strongly universal. They cannot be 3-wise independent, for example.
Polynomial rolling hash The Rabin–Karp string search algorithm is often explained using a rolling hash function that only uses multiplications and additions:
H = c 1 a k − 1 + c 2 a k − 2 + c 3 a k − 3 + . . . + c k a 0 {\displaystyle H=c_{1}a^{k-1}+c_{2}a^{k-2}+c_{3}a^{k-3}+...+c_{k}a^{0}} , where a {\displaystyle a} is a constant, and c 1 , . . . , c k {\displaystyle c_{1},...,c_{k}} are the input characters (but this function is not a Rabin fingerprint, see below). In order to avoid manipulating huge H {\displaystyle H} values, all math is done modulo n {\displaystyle n} . The choice of a {\displaystyle a} and n {\displaystyle n} is critical to get good hashing; in particular, the modulus n {\displaystyle n} is typically a prime number. See linear congruential generator for more discussion. Removing and adding characters simply involves adding or subtracting the first or last term. Shifting all characters by one position to the left requires multiplying the entire sum H {\displaystyle H} by a {\displaystyle a} . Shifting all characters by one position to the right requires dividing the entire sum H {\displaystyle H} by a {\displaystyle a} . Note that in modulo arithmetic, a {\displaystyle a} can be chosen to have a multiplicative inverse a − 1 {\displaystyle a^{-1}} by which H {\displaystyle H} can be multiplied to get the result of the division without actually performing a division.
Rabin fingerprint The Rabin fingerprint is another hash, which also interprets the input as a polynomial, but over the Galois field GF(2). Instead of seeing the input as a polynomial of bytes, it is seen as a polynomial of bits, and all arithmetic is done in GF(2) (similarly to CRC-32). The hash is the remainder after the division of that polynomial by an irreducible polynomial over GF(2). It is possible to update a Rabin fingerprint using only the entering and the leaving byte, making it effectively a rolling hash. Because it shares the same author as the Rabin–Karp string search algorithm, which is often explained with another, simpler rolling hash, and because this simpler rolling hash is also a polynomial, both rolling hashes are often mistaken for each other.
Cyclic polynomial Hashing by cyclic polynomial—sometimes called Buzhash—is also simple and it has the benefit of avoiding multiplications, using circular shift instead. It is a form of tabulation hashing: it presumes that there is some substitution function s {\displaystyle s} from characters to integers in the interval [ 0 , 2 L ) {\displaystyle [0,2^{L})} , essentially a lookup table (each of the 32 bit-positions of the values of s should be balanced, i.e. have as many 1s as there are 0s). Let the function rol {\displaystyle \operatorname {rol} } be bitwise rotation. E.g., rol ( 101 ) = 011 {\displaystyle \operatorname {rol} (101)=011} . Let ⊕ {\displaystyle \oplus } be the bitwise exclusive or. Let c i {\displaystyle c_{i}} be the i-th byte in a stream, and w {\displaystyle w} be the window size in use. We precalculate s ′ {\displaystyle s'} for removing the contribution of a byte that is out of the window:
… excerpt ends here. Continue reading the full article.
