A rolling hash 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.
One of the main applications is the Rabin-Karp string search algorithm, which uses the rolling hash described below.
Another popular application is rsync program which uses a checksum based on Mark Adler's adler-32 as its rolling hash.
At best, rolling hash values are pairwise independent or strongly universal. They cannot be 3-wise independent, for example.
Read more about Rolling Hash: Rabin-Karp Rolling Hash, Content Based Slicing Using Rabin-Karp Hash, Cyclic Polynomial, Computational Complexity, Software, See Also, External Links
Famous quotes containing the word rolling:
“... in the cities there are thousands of rolling stones like me. We are all alike; we have no ties, we know nobody, we own nothing. When one of us dies, they scarcely know where to bury him.... We have no house, no place, no people of our own. We live in the streets, in the parks, in the theatres. We sit in restaurants and concert halls and look about at the hundreds of our own kind and shudder.”
—Willa Cather (1873–1947)