Rolling hash

The Rabin–Karp string search algorithm is often explained using a rolling hash function that only uses multiplications and additions:

${\displaystyle H=c_{1}a^{k-1}+c_{2}a^{k-2}+c_{3}a^{k-3}+...+c_{k}a^{0},}$

where ${\displaystyle a}$ is a constant, and ${\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 ${\displaystyle H}$ values, all math is done modulo ${\displaystyle n}$. The choice of ${\displaystyle a}$ and ${\displaystyle n}$ is critical to get good hashing; 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 ${\displaystyle H}$ by ${\displaystyle a}$. Shifting all characters by one position to the right requires dividing the entire sum ${\displaystyle H}$ by ${\displaystyle a}$. Note that in modulo arithmetic, ${\displaystyle a}$ can be chosen to have a multiplicative inverse ${\displaystyle a^{-1}}$ by which ${\displaystyle H}$ can be multiplied to get the result of the division without actually performing a division.

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 CRC32). The hash is the result of 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. The backup software restic uses a Rabin fingerprint for splitting files, with blob size varying between 512 bytes and 8MiB.[2]

Hashing by cyclic polynomial[3]—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 ${\displaystyle h}$ from characters to integers in the interval ${\displaystyle [0,2^{L})}$. This hash function might be simply an array or a hash table mapping characters to random integers. Let the function ${\displaystyle s}$ be a cyclic binary rotation (or circular shift): it rotates the bits by 1 to the left, pushing the latest bit in the first position. E.g., ${\displaystyle s(10011)=00111}$. Let ${\displaystyle \oplus }$ be the bitwise exclusive or. The hash values are defined as

${\displaystyle H=s^{k-1}(h(c_{1}))\oplus s^{k-2}(h(c_{2}))\oplus \ldots \oplus s(h(c_{k-1}))\oplus h(c_{k}),}$

where the multiplications by powers of two can be implemented by binary shifts. The result is a number in ${\displaystyle [0,2^{L})}$.

Computing the hash values in a rolling fashion is done as follows. Let ${\displaystyle H}$ be the previous hash value. Rotate ${\displaystyle H}$ once: ${\displaystyle H\leftarrow s(H)}$. If ${\displaystyle c_{1}}$ is the character to be removed, rotate it ${\displaystyle k}$ times: ${\displaystyle s^{k}(h(c_{1}))}$. Then simply set

${\displaystyle H\leftarrow s(H)\oplus s^{k}(h(c_{1}))\oplus h(c_{k+1}),}$

where ${\displaystyle c_{k+1}}$ is the new character.

Hashing by cyclic polynomials is strongly universal or pairwise independent: simply keep the first ${\displaystyle L-k+1}$ bits. That is, take the result ${\displaystyle H}$ and dismiss any ${\displaystyle k-1}$ consecutive bits.[1] In practice, this can be achieved by an integer division ${\displaystyle H\rightarrow H\div 2^{k-1}}$.

One of the interesting use cases of the rolling hash function is that it can create dynamic, content-based chunks of a stream or file. This is especially useful when it is required to send only the changed chunks of a large file over a network and a simple byte addition at the front of the file would cause all the fixed size windows to become updated, while in reality, only the first "chunk" has been modified.

The simplest approach to calculate the dynamic chunks is to calculate the rolling hash and if it matches a pattern (like the lower N bits are all zeroes) then it’s a chunk boundary. This approach will ensure that any change in the file will only affect its current and possibly the next chunk, but nothing else.

When the boundaries are known, the chunks need to be compared by their hash values to detect which one was modified and needs transfer across the network.[4] The backup software Attic uses a Buzhash algorithm with a customizable chunk size range for splitting file streams.[5]

Several programs, including gzip (with the --rsyncable option) and rsyncrypto, do content-based slicing based on this specific (unweighted) moving sum:[6]

${\displaystyle S(n)=\sum _{i=n-8195}^{n}c_{i},}$

${\displaystyle H(n)=S(n)\mod 4096,}$

where

• ${\displaystyle S(n)}$ is the sum of 8196 consecutive bytes ending with byte ${\displaystyle n}$ (requires 21 bits of storage),
• ${\displaystyle c_{i}}$ is byte ${\displaystyle i}$ of the file,
• ${\displaystyle H(n)}$ is a "hash value" consisting of the bottom 12 bits of ${\displaystyle S(n)}$.

Shifting the window by one byte simply involves adding the new character to the sum and subtracting the oldest character (no longer in the window) from the sum.

For every ${\displaystyle n}$ where ${\displaystyle H(n)==0}$, these programs cut the file between ${\displaystyle n}$ and ${\displaystyle n+1}$. This approach will ensure that any change in the file will only affect its current and possibly the next chunk, but no other chunk.

The Content-Defined Chunking (CDC) algorithm needs to compute the hash value of a data stream byte by byte and split the data stream into chunks when the hash value meets a predefined value. However, comparing a string byte-by-byte will introduce the heavy computation overhead. FastCDC [7] proposes a new and efficient Content-Defined Chunking approach. It uses a fast rolling Gear hash algorithm,[8] skipping the minimum length, normalizing the chunk-size distribution, and last but not the least, rolling two bytes each time to speed up the CDC algorithm, which can achieve about 10X higher throughput than Rabin-based CDC approach.[9]

The basic version pseudocode is provided as follows:

algorithm FastCDC
    input: data buffer src, 
           data length n, 
    output: cut point i
    
    MinSize ← 2KB     // split minimum chunk size is 2 KB
    MaxSize ← 64KB    // split maximum chunk size is 64 KB
    fp ← 0
    i ← MinSize
    Mask ← 0x0000d93003530000LL
    
    // buffer size is less than minimum chunk size
    if n ≤ MinSize then
        return n
    if n ≥ MaxSize then
        n ← MaxSize
     
    while i < n do
        fp ← (fp << 1 ) + Gear[src[i]]
        if !(fp & Mask) then
            return i
   
    return i

Where Gear array is a pre-calculated hashing array. Here FastCDC uses Gear hashing algorithm which can calculate the rolling hashing results quickly and keep the uniform distribution of the hashing results as Rabin. Compared with the traditional Rabin hashing algorithm, it achieves a much faster speed. Experiments suggest that it can generate nearly the same chunk size distribution in the much shorter time (about 1/10 of rabin-based chunking [9]) when segmenting the data stream.

All rolling hash functions are linear in the number of characters, but their complexity with respect to the length of the window (${\displaystyle k}$) varies. Rabin–Karp rolling hash requires the multiplications of two ${\displaystyle k}$-bit numbers, integer multiplication is in ${\displaystyle O(k\log k2^{O(\log ^{*}k)})}$.[10] Hashing ngrams by cyclic polynomials can be done in linear time.[1]

• rollinghashcpp is a free-software C++ implementation of several rolling hash functions
• rollinghashjava is an Apache-licensed Java implementation of rolling hash functions

• MinHash
• w-shingling

• MIT 6.006: Introduction to Algorithms 2011- Lecture Notes - Rolling Hash