polynomial rolling hash

A string hash that treats the characters as digits of a number in some base, such as 31, and reduces the result modulo the table size.

In more detail

For each character it computes h = (h * base + code) % n, so every character and its position affect the result. Anagrams such as "cat" and "act" get different hashes, unlike a simple sum of character codes. Rabin-Karp text search uses the same idea and can update the hash cheaply as a window slides along a string.

Example

h = (h * 31 + ord(ch)) % n

Related terms

Taught in

References