Showing posts with label rollinghash. Show all posts
Showing posts with label rollinghash. Show all posts

Thursday, 19 November 2026

Rolling Hash

From Hashing to Rolling Hashing

You know about hashing but do you know about "rolling hash". This is a very simple concept, whereby a hash function is applied to a rolling window of text.

A major application is the Rabin-Karp string search algorithm. Another important application is rsync.

The cleverness of a rolling hash is efficient calculation - instead of computing hash values fresh each time, it updates the hash incrementally as new data comes in.

Rolling Hash in Rabin-Karp

This is used in string matching, and plagiarism detection.

Rolling Hash in rsync

This is manifested in the form of a rolling checksum, to check "everything is ok" as the sync operation proceeeds.

Other names for Rolling Hash

Recursive hashing is another name for rolling hash, or rolling checksum, as in the case of rsync.