Rolling hash

A rolling hash (also known as recursive hashing or rolling checksum) is a <a href="/facts/Hash_function/rk6MlCt3">hash function</a> 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 <a href="/facts/Moving_average/tWY74500">moving average</a> function can be computed much more quickly than other low-pass filters; and similar to the way a <a href="/facts/Zobrist_hashing/CTfD0GWd">Zobrist hash</a> can be <a href="/facts/Zobrist_hashing/CTfD0GWd">rapidly updated</a> from the old hash value.
One of the main applications is the <a href="/facts/Rabin%E2%80%93Karp_string_search_algorithm/Wf7f0F53">Rabin–Karp string search algorithm</a>, which uses the rolling hash described below. Another popular application is the <a href="/facts/Rsync/H4UlsQ3U">rsync</a> program, which uses a checksum based on <a href="/facts/Mark_Adler/p202HSHc">Mark Adler</a>'s <a href="/facts/Adler-32/fcUX7I00">adler-32</a> as its rolling hash. Low Bandwidth Network Filesystem (LBFS) uses a <a href="/facts/Rabin_fingerprint/AqXtlXwP">Rabin fingerprint</a> 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 <a href="/facts/Pairwise_independent/Y9kL13Cw">pairwise independent</a> or strongly <a href="/facts/Universal_hashing/NICffew4">universal</a>. They cannot be <a href="/facts/K-independent_hashing/xRDnzsPa">3-wise independent</a>, for example.

Rolling hash open-in-new

Rolling hash