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)) % nRelated terms
- hash function — A function that turns data of any size into a fixed-size value, called its hash, used to find items quickly in a table or to detect any change in the data.
- modulo — The operation that gives the remainder after division, written % in many programming languages, so 17 % 5 is 2.
- anagram — A word made by rearranging the letters of another word, such as "listen" and "silent".
Taught in
- What A Hash Function Promises — Algorithms & Data Structures for Working Engineers
- Collisions In Practice And Hash Flooding — Algorithms & Data Structures for Working Engineers