{"history":[],"article":{"id":"74b07c63-b55c-4898-b9bd-b8fe8bcc5cc4","title":"Rolling hash","slug":"rolling-hash","content":":::summary\n:::\n\n# \nA **rolling hash** (also known as recursive hashing or rolling checksum) is a [hash function](https://bliptext.com/articles/hash-function) where the input is hashed in a window that moves through the input.\nA 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](https://bliptext.com/articles/moving-average) function can be computed much more quickly than other low-pass filters; and similar to the way a [Zobrist hash](https://bliptext.com/articles/zobrist-hashing) can be [rapidly updated](https://bliptext.com/articles/zobrist-hashing) from the old hash value.\nOne of the main applications is the [Rabin–Karp string search algorithm](https://bliptext.com/articles/rabin-karp-string-search-algorithm), which uses the rolling hash described below.\nAnother popular application is the [rsync](https://bliptext.com/articles/rsync) program, which uses a checksum based on Mark Adler's [adler-32](https://bliptext.com/articles/adler-32) as its rolling hash.\nLow Bandwidth Network Filesystem (LBFS) uses a [Rabin fingerprint](https://bliptext.com/articles/rabin-fingerprint) as its rolling hash.\nFastCDC (Fast Content-Defined Chunking) uses a compute-efficient Gear fingerprint as its rolling hash.\nAt best, rolling hash values are [pairwise independent](https://bliptext.com/articles/pairwise-independent) or strongly [universal](https://bliptext.com/articles/universal-hashing).\nThey cannot be [3-wise independent](https://bliptext.com/articles/k-independent-hashing), for example.\n\n# Polynomial rolling hash\nThe [Rabin–Karp string search algorithm](https://bliptext.com/articles/rabin-karp-string-search-algorithm) is often explained using a rolling hash function that only uses multiplications and additions:\nwhere a is a constant, and are the input characters (but this function is not a [Rabin fingerprint](https://bliptext.com/articles/rabin-fingerprint), see below).\nIn order to avoid manipulating huge H values, all math is done [modulo](https://bliptext.com/articles/modular-arithmetic) n. The choice of a and n is critical to get good hashing; in particular, the modulus n is typically a prime number.\nSee [linear congruential generator](https://bliptext.com/articles/linear-congruential-generator) for more discussion.\nRemoving and adding characters simply involves adding or subtracting the first or last term.\nShifting all characters by one position to the left requires multiplying the entire sum H by a. Shifting all characters by one position to the right requires dividing the entire sum H by a. Note that in modulo arithmetic, a can be chosen to have a [multiplicative inverse](https://bliptext.com/articles/modular-multiplicative-inverse) a^{-1} by which H can be multiplied to get the result of the division without actually performing a division.\n\n# Rabin fingerprint\nThe [Rabin fingerprint](https://bliptext.com/articles/rabin-fingerprint) is another hash, which also interprets the input as a polynomial, but over the [Galois field](https://bliptext.com/articles/finite-field) [GF(2)](https://bliptext.com/articles/gf-2).\nInstead 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](https://bliptext.com/articles/crc32)).\nThe hash is the result of the division of that polynomial by an irreducible polynomial over GF(2).\nIt is possible to update a Rabin fingerprint using only the entering and the leaving byte, making it effectively a rolling hash.\nBecause 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.\nThe backup software [restic](https://bliptext.com/articles/restic) uses a Rabin fingerprint for splitting files, with blob size varying between 512 KiB and 8 MiB.\n\n# Cyclic polynomial\nHashing by cyclic polynomial —sometimes called Buzhash—is also simple and it has the benefit of avoiding multiplications, using [barrel shifts](https://bliptext.com/articles/barrel-shifter) instead.\nIt is a form of [tabulation hashing](https://bliptext.com/articles/tabulation-hashing): it presumes that there is some hash function h from characters to integers in the interval [0,2^L). This hash function might be simply an array or a [hash table](https://bliptext.com/articles/hash-table) mapping characters to random integers. Let the function s be a cyclic binary rotation (or [circular shift](https://bliptext.com/articles/circular-shift)): it rotates the bits by 1 to the left, pushing the latest bit in the first position. E.g., s(101)=011. Let \\oplus be the bitwise [exclusive or](https://bliptext.com/articles/exclusive-or). The hash values are defined as\nwhere the multiplications by powers of two can be implemented by binary shifts.\nThe result is a number in [0,2^L).\nComputing the hash values in a rolling fashion is done as follows.\nLet H be the previous hash value.\nRotate H once:.\nIf c_1 is the character to be removed, rotate it k times:.\nThen simply set\nwhere c_{k+1} is the new character.\nHashing by cyclic polynomials is strongly universal or pairwise independent: simply keep the first L-k+1 bits.\nThat is, take the result H and dismiss any k-1 consecutive bits.\nIn practice, this can be achieved by an integer division.\n\n# Content-based slicing using a rolling hash\nOne of the interesting use cases of the rolling hash function is that it can create dynamic, content-based chunks of a stream or file.\nThis is especially useful when it is required to send only the changed chunks of a large file over a network: a simple byte addition at the front of the file would normally cause all fixed size windows to become updated, while in reality, only the first \"chunk\" has been modified.\nA simple approach to making dynamic chunks is to calculate a rolling hash, and if the hash value matches an arbitrary pattern (e.g. all zeroes) in the lower N bits (with a probability of, given the hash has a uniform probability distribution) then it’s chosen to be a chunk boundary.\nEach chunk will thus have an average size of 2^n bytes.\nThis approach ensures that unmodified data (more than a window size away from the changes) will have the same boundaries.\nOnce the boundaries are known, the chunks need to be compared by cryptographic hash value to detect changes.\nThe backup software [Borg](https://bliptext.com/articles/borg-backup-software) uses the Buzhash algorithm with a customizable chunk size range for splitting file streams.\nSuch content-defined chunking is often used for [data deduplication](https://bliptext.com/articles/data-deduplication).\n\n# Content-based slicing using moving sum\nSeveral programs, including gzip (with the option) and rsyncrypto, do content-based slicing based on this specific (unweighted) moving sum:\nwhere\nShifting 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.\nFor every n where H(n) == 0, these programs cut the file between n and n+1.\nThis approach will ensure that any change in the file will only affect its current and possibly the next chunk, but no other chunk.\n\n# Gear fingerprint and content-based chunking algorithm FastCDC\nChunking is a technique to divide a data stream into a set of blocks, also called chunks.\nContent-defined chunking (CDC) is a chunking technique in which the division of the data stream is not based on fixed chunk size, as in fixed-size chunking, but on its content.\nThe Content-Defined Chunking 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.\nHowever, comparing a string byte-by-byte will introduce the heavy computation overhead.\nFastCDC proposes a new and efficient Content-Defined Chunking approach.\nIt uses a fast rolling Gear hash algorithm, 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.\nThe basic version pseudocode is provided as follows:\n**algorithm** FastCDC\n**input:** data buffer src,\ndata length n,\n**output:** cut point i\nMinSize ← 2KB // split minimum chunk size is 2 KB MaxSize ← 64KB // split maximum chunk size is 64 KB Mask ← 0x0000d93003530000LL\nfp ← 0\ni ← 0\n// buffer size is less than minimum chunk size\n**if** n ≤ MinSize **then**\n**return** n\n**if** n ≥ MaxSize **then**\nn ← MaxSize\n// Skip the first MinSize bytes, and kickstart the hash\n**while** i < MinSize **do**\nfp ← (fp << 1 ) + Gear[src[i]]\ni ← i + 1\n**while** i < n **do**\nfp ← (fp << 1 ) + Gear[src[i]]\n**if** !(fp & Mask) **then**\n**return** i\ni ← i + 1\n**return** i\nWhere Gear array is a pre-calculated hashing array.\nHere FastCDC uses Gear hashing algorithm which can calculate the rolling hashing results quickly and keep the uniform distribution of the hashing results as Rabin.\nCompared with the traditional Rabin hashing algorithm, it achieves a much faster speed.\nExperiments suggest that it can generate nearly the same chunk size distribution in the much shorter time (about 1/10 of rabin-based chunking ) when segmenting the data stream.\n\n# Computational complexity\nAll rolling hash functions can be computed in time linear in the number of characters and updated in constant time when characters are shifted by one position.\nIn particular, computing the Rabin-Karp rolling hash of a string of length k requires O(k) modular arithmetic operations, and hashing by cyclic polynomials requires O(k) bitwise [exclusive ors](https://bliptext.com/articles/exclusive-or) and [circular shifts](https://bliptext.com/articles/circular-shift).\n\n# Footnotes","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-26T07:10:32.432Z","updated_at":"2025-01-26T07:10:32.432Z","search_vector":"'hash':2 'roll':1","search_content":" \n \n\n# \nA **rolling hash** (also known as recursive hashing or rolling checksum) is a [hash function](https://bliptext.com/articles/hash-function) where the input is hashed in a window that moves through the input.\nA 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](https://bliptext.com/articles/moving-average) function can be computed much more quickly than other low-pass filters; and similar to the way a [Zobrist hash](https://bliptext.com/articles/zobrist-hashing) can be [rapidly updated](https://bliptext.com/articles/zobrist-hashing) from the old hash value.\nOne of the main applications is the [Rabin–Karp string search algorithm](https://bliptext.com/articles/rabin-karp-string-search-algorithm), which uses the rolling hash described below.\nAnother popular application is the [rsync](https://bliptext.com/articles/rsync) program, which uses a checksum based on Mark Adler's [adler-32](https://bliptext.com/articles/adler-32) as its rolling hash.\nLow Bandwidth Network Filesystem (LBFS) uses a [Rabin fingerprint](https://bliptext.com/articles/rabin-fingerprint) as its rolling hash.\nFastCDC (Fast Content-Defined Chunking) uses a compute-efficient Gear fingerprint as its rolling hash.\nAt best, rolling hash values are [pairwise independent](https://bliptext.com/articles/pairwise-independent) or strongly [universal](https://bliptext.com/articles/universal-hashing).\nThey cannot be [3-wise independent](https://bliptext.com/articles/k-independent-hashing), for example.\n\n# Polynomial rolling hash\nThe [Rabin–Karp string search algorithm](https://bliptext.com/articles/rabin-karp-string-search-algorithm) is often explained using a rolling hash function that only uses multiplications and additions:\nwhere a is a constant, and are the input characters (but this function is not a [Rabin fingerprint](https://bliptext.com/articles/rabin-fingerprint), see below).\nIn order to avoid manipulating huge H values, all math is done [modulo](https://bliptext.com/articles/modular-arithmetic) n. The choice of a and n is critical to get good hashing; in particular, the modulus n is typically a prime number.\nSee [linear congruential generator](https://bliptext.com/articles/linear-congruential-generator) for more discussion.\nRemoving and adding characters simply involves adding or subtracting the first or last term.\nShifting all characters by one position to the left requires multiplying the entire sum H by a. Shifting all characters by one position to the right requires dividing the entire sum H by a. Note that in modulo arithmetic, a can be chosen to have a [multiplicative inverse](https://bliptext.com/articles/modular-multiplicative-inverse) a^{-1} by which H can be multiplied to get the result of the division without actually performing a division.\n\n# Rabin fingerprint\nThe [Rabin fingerprint](https://bliptext.com/articles/rabin-fingerprint) is another hash, which also interprets the input as a polynomial, but over the [Galois field](https://bliptext.com/articles/finite-field) [GF(2)](https://bliptext.com/articles/gf-2).\nInstead 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](https://bliptext.com/articles/crc32)).\nThe hash is the result of the division of that polynomial by an irreducible polynomial over GF(2).\nIt is possible to update a Rabin fingerprint using only the entering and the leaving byte, making it effectively a rolling hash.\nBecause 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.\nThe backup software [restic](https://bliptext.com/articles/restic) uses a Rabin fingerprint for splitting files, with blob size varying between 512 KiB and 8 MiB.\n\n# Cyclic polynomial\nHashing by cyclic polynomial —sometimes called Buzhash—is also simple and it has the benefit of avoiding multiplications, using [barrel shifts](https://bliptext.com/articles/barrel-shifter) instead.\nIt is a form of [tabulation hashing](https://bliptext.com/articles/tabulation-hashing): it presumes that there is some hash function h from characters to integers in the interval [0,2^L). This hash function might be simply an array or a [hash table](https://bliptext.com/articles/hash-table) mapping characters to random integers. Let the function s be a cyclic binary rotation (or [circular shift](https://bliptext.com/articles/circular-shift)): it rotates the bits by 1 to the left, pushing the latest bit in the first position. E.g., s(101)=011. Let \\oplus be the bitwise [exclusive or](https://bliptext.com/articles/exclusive-or). The hash values are defined as\nwhere the multiplications by powers of two can be implemented by binary shifts.\nThe result is a number in [0,2^L).\nComputing the hash values in a rolling fashion is done as follows.\nLet H be the previous hash value.\nRotate H once:.\nIf c_1 is the character to be removed, rotate it k times:.\nThen simply set\nwhere c_{k+1} is the new character.\nHashing by cyclic polynomials is strongly universal or pairwise independent: simply keep the first L-k+1 bits.\nThat is, take the result H and dismiss any k-1 consecutive bits.\nIn practice, this can be achieved by an integer division.\n\n# Content-based slicing using a rolling hash\nOne of the interesting use cases of the rolling hash function is that it can create dynamic, content-based chunks of a stream or file.\nThis is especially useful when it is required to send only the changed chunks of a large file over a network: a simple byte addition at the front of the file would normally cause all fixed size windows to become updated, while in reality, only the first \"chunk\" has been modified.\nA simple approach to making dynamic chunks is to calculate a rolling hash, and if the hash value matches an arbitrary pattern (e.g. all zeroes) in the lower N bits (with a probability of, given the hash has a uniform probability distribution) then it’s chosen to be a chunk boundary.\nEach chunk will thus have an average size of 2^n bytes.\nThis approach ensures that unmodified data (more than a window size away from the changes) will have the same boundaries.\nOnce the boundaries are known, the chunks need to be compared by cryptographic hash value to detect changes.\nThe backup software [Borg](https://bliptext.com/articles/borg-backup-software) uses the Buzhash algorithm with a customizable chunk size range for splitting file streams.\nSuch content-defined chunking is often used for [data deduplication](https://bliptext.com/articles/data-deduplication).\n\n# Content-based slicing using moving sum\nSeveral programs, including gzip (with the option) and rsyncrypto, do content-based slicing based on this specific (unweighted) moving sum:\nwhere\nShifting 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.\nFor every n where H(n) == 0, these programs cut the file between n and n+1.\nThis approach will ensure that any change in the file will only affect its current and possibly the next chunk, but no other chunk.\n\n# Gear fingerprint and content-based chunking algorithm FastCDC\nChunking is a technique to divide a data stream into a set of blocks, also called chunks.\nContent-defined chunking (CDC) is a chunking technique in which the division of the data stream is not based on fixed chunk size, as in fixed-size chunking, but on its content.\nThe Content-Defined Chunking 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.\nHowever, comparing a string byte-by-byte will introduce the heavy computation overhead.\nFastCDC proposes a new and efficient Content-Defined Chunking approach.\nIt uses a fast rolling Gear hash algorithm, 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.\nThe basic version pseudocode is provided as follows:\n**algorithm** FastCDC\n**input:** data buffer src,\ndata length n,\n**output:** cut point i\nMinSize ← 2KB // split minimum chunk size is 2 KB MaxSize ← 64KB // split maximum chunk size is 64 KB Mask ← 0x0000d93003530000LL\nfp ← 0\ni ← 0\n// buffer size is less than minimum chunk size\n**if** n ≤ MinSize **then**\n**return** n\n**if** n ≥ MaxSize **then**\nn ← MaxSize\n// Skip the first MinSize bytes, and kickstart the hash\n**while** i < MinSize **do**\nfp ← (fp << 1 ) + Gear[src[i]]\ni ← i + 1\n**while** i < n **do**\nfp ← (fp << 1 ) + Gear[src[i]]\n**if** !(fp & Mask) **then**\n**return** i\ni ← i + 1\n**return** i\nWhere Gear array is a pre-calculated hashing array.\nHere FastCDC uses Gear hashing algorithm which can calculate the rolling hashing results quickly and keep the uniform distribution of the hashing results as Rabin.\nCompared with the traditional Rabin hashing algorithm, it achieves a much faster speed.\nExperiments suggest that it can generate nearly the same chunk size distribution in the much shorter time (about 1/10 of rabin-based chunking ) when segmenting the data stream.\n\n# Computational complexity\nAll rolling hash functions can be computed in time linear in the number of characters and updated in constant time when characters are shifted by one position.\nIn particular, computing the Rabin-Karp rolling hash of a string of length k requires O(k) modular arithmetic operations, and hashing by cyclic polynomials requires O(k) bitwise [exclusive ors](https://bliptext.com/articles/exclusive-or) and [circular shifts](https://bliptext.com/articles/circular-shift).\n\n# Footnotes","revisionCount":0},"hasMore":false,"nextCursor":null}

History