Lecture
A rolling (sliding, circular) hash, rolling hash — is a hash function that processes input within some window. Computing the hash function’s value for a shifted window is a cheap operation for such functions. To recompute the value, one only needs to know the previous hash value, the value of the input data that fell outside the window, and the value of the data that entered the window. In other words, if 
is the hash of the sequence 
, then the hash 
for the “shifted” sequence 
can be obtained using an easily computable function 
.
The ability to quickly “shift” the hash imposes certain limits on the theoretical guarantees. In particular, it has been shown that families of rolling hashes cannot be 3-independent[en]; at best — universal or 2-independent[en]. However, for most applications (even approximate) universality is sufficient.
One of the main applications is the Rabin–Karp string search algorithm, which uses the rolling hash described below. The rolling hash is used for substring search in the Rabin—Karp algorithm, for computing hashes of N-grams in text , and also in the rsync program for comparing binary files (a rolling version of adler-32 is used).
Another popular application is the rsync program, which uses a checksum based on Mark Adler’s adler-32 as a rolling hash. The Low-Bandwidth File System (LBFS) uses a Rabin fingerprint as its rolling hash. FastCDC (Fast Content-Defined Chunking) uses a computationally efficient Gear fingerprint as its rolling hash.
In the best case, rolling hash values are pairwise independent or strongly universal. For example, they cannot be 3-independent.
The Rabin—Karp algorithm often uses a simple polynomial rolling hash built from multiplication and addition operations :
.
To avoid using arbitrary-precision integer arithmetic, arithmetic is performed in the ring of residues modulo 
, which fits into a single machine word. The choice of the constants 
and is very important for obtaining a good-quality hash. In the original version of the hash, it was assumed that should be a randomly chosen prime number, and 
. However, since the algorithm for choosing a random prime is not so simple, a variant of the hash is preferred in which is a fixed prime number and is chosen randomly from the range 
. Dietzfelbinger et al. showed that this variant of the hash has the same theoretical properties as the original. In particular, the probability that the hash values of two different strings and 
collide does not exceed 
, provided that 
and 
are integers from the range 
, and 
and are chosen truly at random.
Removing old input symbols and adding new ones is done by adding or subtracting the first or last term of the formula (modulo ). To remove the term 
, a precomputed value 
is stored. The window is shifted by multiplying the entire polynomial 
by or dividing by (if is prime, then in the ring of residues one can multiply by the inverse instead of dividing). In practice it is most convenient to take 
or 
for 32-bit and 64-bit machine words respectively (these are the so-called Mersenne primes). In this case the modulo operation can be performed on many computers using fast bitwise shift and addition operations . Another possible choice — the values 
or 
, for which fast algorithms for taking the remainder modulo also exist (in this case the range of allowed values of is narrowed slightly) . A common misconception — assuming 
. There exist families of strings for which a hash with 
will always produce many collisions, regardless of the choice of 
. These and other further implementation and theoretical-analysis details of the polynomial hash can be found in the article on the Rabin—Karp algorithm.
This hash is similar to the ordinary polynomial hash, but all computations in it are carried out in the finite field 
. Usually is chosen to be 64. The elements of the field — these are the numbers 
. Addition in the field is implemented using the bitwise exclusive “or” operation 
, and multiplication is performed using the operation 
, which first carrylessly multiplies[en] 
by 
, and then takes the remainder of the “carryless” division of the result by some chosen fixed element 
(carryless division here is the operation inverse to carryless multiplication). The element 
must be chosen so that 
and 
— is an irreducible polynomial over the field 
(the field is often viewed as the set of polynomials over the field 
modulo some arbitrary irreducible polynomial of degree ). For instance, one can set 
. Then the hash is computed as follows :
,
where — a number randomly chosen during hash initialization from the range 
, and 
— a short notation for 
, where is repeated 
times. Using the fundamental theorem of algebra, it can be shown that the probability of a collision between the hashes of two different strings of length 
does not exceed 
. It has been shown that on modern Intel and AMD processors, all the arithmetic over the field needed for the hash can be efficiently computed using instructions from the CLMUL[en] extension.
Let 
— be some hash that maps the characters of the string being hashed to -bit numbers (usually 
or 
). Cyclic polynomial hashing is defined as follows :
where — the bitwise exclusive “or” operation, and 
— the operation of a cyclic left shift of the -bit number by 
bits. It is easy to show that this hash is rolling:
The main advantage of this hash is that it uses only fast bitwise operations available on most modern computers. The quality of the hash depends directly on the choice of the function . Lemire and Kaser proved that if the function is chosen randomly from a family of independent hash functions[en], then the probability that the hashes of two different strings of length collide does not exceed 
. This imposes certain restrictions on the range of problems in which this hash can be used. First, the length of the strings being hashed must be less than . For general-purpose hashing algorithms this condition can be a problem, but, for instance, for hashing -grams, where usually does not exceed 16, this restriction is natural (in the case of -grams, the role of the characters is played by individual tokens of the text). Second, the choice of a family of independent functions can also be a problem in some cases. For a byte alphabet, the property of independence is possessed by the family of functions , encoded by a table of 256 different random -bit numbers (choosing the function — filling in the table). For hashing -grams, one can assign different random -bit numbers to different tokens (the number of distinct tokens in such tasks is usually relatively small), and such a family of hash functions also has the independence property.
This hash is applicable only in the special case where the characters of the string being hashed are the numbers 0 and 1. The idea of the hash is to view the input string as a polynomial 
over the field , and the hash itself is the remainder of dividing 
by an irreducible polynomial 
of degree over the field , chosen randomly during hash initialization. Essentially this is the same procedure used in CRC. Let us examine it in more detail.
The result of hashing the string — this is the sequence of bits 
. The number is chosen to be prime and large enough, but such that the sequence fits into a single machine word (usually 
or 
is taken). Let 
be some irreducible polynomial of degree over the field . Denote by 
the corresponding number with bit representation 
. The hash function is defined as the number with bit representation 
such that the polynomial 
is the remainder of dividing the polynomial 
by the polynomial , that is, 
.
Despite its rather convoluted definition, the Rabin hash is fairly simple to implement (once the irreducible polynomial has already been found). The computation relies on the following simple observation: if the number with bit representation encodes the polynomial , then the number 
encodes the polynomial 
, where denotes the operation of shifting the number one bit to the left, filling the low-order bit with zero (not to be confused with the cyclic shift 
defined above!). Let 
, and — this is the bit representation of . Then 
is computed as follows:
if 
if 
The hash is rolling. Let 
, and — this is the bit representation of . The hash is computed as follows :
if
if 
where 
— this is the -bit number whose bit representation corresponds to the polynomial 
. The number is precomputed when initializing the hash for a string of length .
The main difficulty — randomly choosing an irreducible polynomial of degree . Rabin described an efficient algorithm for doing this, and proved that the probability of a collision between the hashes of two different strings of length , for a random choice of , does not exceed .
Note that this hash is often confused with the polynomial hash, owing to their similar area of application, their common use of polynomials, and a shared author.
One interesting use of a rolling hash function is that it can be used to create dynamic blocks based on the content of a stream or file. This is especially useful when only the changed portions of a large file need to be sent over the network, since simply adding a byte at the start of the file would cause all the fixed-size windows to be updated, whereas in fact only the first "chunk" was changed.
The simplest approach to computing dynamic fragments is to compute the rolling hash, and if it matches a pattern (for example, all of the low-order N bits are zero), then that is a fragment boundary. This approach guarantees that any change to the file will affect only its current and, possibly, the next fragment, but nothing else.
Once the boundaries are known, the blocks must be compared by their hash values to determine which of them has changed and needs to be sent over the network. The Attic backup program uses the Buzhash algorithm with a configurable block-size range to split file streams.
Several programs, including gzip (with the --rsyncable option) and rsyncrypto, perform content-defined chunking based on this particular (unweighted) rolling sum:
where
is the sum of 8196 consecutive bytes ending with byte (requires 21 bits of memory),
is byte of the file,
the "hash value", consisting of the low 12 bits of .Shifting the window by one byte simply involves adding the new character to the sum and subtracting the oldest character (no longer within the window) from the sum.
For every where 
, these programs split the file between and 
. This approach guarantees that any change to the file will affect only its current and, possibly, the next fragment, but not any other fragment.
The Content-Defined Chunking (CDC) algorithm must compute the hash value of the data stream byte by byte and split the data stream into fragments when the hash value matches a predefined value. However, comparing the string byte by byte leads to significant computational overhead. FastCDC proposes a new and efficient approach to Content-Defined Chunking. It uses the fast Gear hashing algorithm , skipping a minimum length, normalizing the distribution of fragment sizes, and, last but not least, rolling two bytes at a time to speed up the CDC algorithm, which achieves roughly 10 times greater throughput than the Rabin-based CDC approach.
Pseudocode for the basic version is given below:
Here, the Gear array is a precomputed hashing array. FastCDC uses the Gear hashing algorithm, which can quickly compute rolling-hash results and maintain a uniform distribution of hash results, just as Rabin’s does. Compared with the traditional Rabin hashing algorithm, it provides much higher speed. Experiments show that when segmenting a data stream, it can generate almost the same distribution of fragment sizes in much less time (about 1/10 of the time of the Rabin-based approach ).
All rolling hash functions are linear in the number of characters, but their complexity, which depends on the window length (
), varies. The Rabin–Karp rolling hash requires multiplying two -bit numbers, an integer multiplication in 
. [10] Hashing n-grams with cyclic polynomials can be done in linear time.
Comments