Rolling hash in Python

Why this matters

Many string jobs compare pieces of text over and over. A program might ask, "Does the text from position 10 to 20 equal the text from position 500 to 510?" It might ask that question thousands of times. The direct way to answer is to compare the characters one by one. For a short piece of text that is fast. For a long piece, asked many times, it adds up.

A rolling hash is a trick that answers each question with a few arithmetic steps, no matter how long the pieces are. You do one pass over the string at the start. After that, each comparison costs the same small amount of work.

This lesson builds the trick from the ground up. It uses integers, the % operator, slices and the ord function. The earlier lessons in this module covered strings, lists and searching. This lesson does not repeat them. It also does not teach the full search algorithm that uses rolling hashes, which is a separate topic.

The problem: comparing pieces of text is slow

Take the word banana. Positions start at 0, so the letters are:

index:  0  1  2  3  4  5
letter: b  a  n  a  n  a

The piece from index 1 up to index 4 (not including 4) is ana. The piece from index 3 up to index 6 is also ana. To check that they match, a program compares the first letters, then the second, then the third. Three letters means three comparisons.

A piece of length k costs up to k comparisons. If the pieces are 1,000 letters long and you ask 100,000 questions, the work is about 100 million letter comparisons. That is a lot of work for a simple question.

The rolling hash changes the cost of one question from about k steps to a fixed number of steps. It does this by replacing the text with numbers that are cheap to compare.

The idea: a string is a number

Start with a simpler question. How do you write the word abc as a number?

Give each letter a number. Use a = 1, b = 2, c = 3. Then use the rule you already know from decimal numbers: each new digit is worth ten times the digit before it. Reading 1, 2, 3 left to right gives:

start:           0
read 1 (a):      0 * 10 + 1  = 1
read 2 (b):      1 * 10 + 2  = 12
read 3 (c):     12 * 10 + 3  = 123

The word abc becomes the number 123. The number is called a hash of the word. A hash is a short number computed from a larger piece of data. Two words with different letters usually get different hashes, but not always. That gap is handled later in this lesson.

The number 10 in the calculation is called the base. Any base works, as long as it is big enough that the digits do not mix. Real rolling hashes use a base such as 31 or 131, because those give good spread for letters. The example uses 10 so the arithmetic is easy to follow by hand.

The rule is simple. For each new letter, multiply the running number by the base and add the letter's value:

new number = old number * base + value of the new letter

In the code below the value of a letter is ord(ch), the character's code, which is 97 for a. The hand examples use 1, 2 and 3 only to keep the numbers small.

Prefix hashes

A prefix is the start of a string. The prefix of length 3 in abcab is abc. A prefix hash is the hash of a prefix. It is useful to store the prefix hash for every length, so that the program can look it up later.

Use the word abcab with values a = 1, b = 2, c = 3 and base 10. Here are the prefix hashes:

prefix length:  0  1   2    3     4      5
prefix text:       a   ab   abc   abca   abcab
prefix hash:    0  1  12  123  1231  12312

Each entry is built from the one before it, using the rule above. The entry for abcab is 1231 * 10 + 2 = 12312.

Filling this table takes one pass over the string. The table is called the prefix array. The string has 5 letters, and the table has 6 entries. Entry 0 is the empty prefix, and its hash is 0. Entry i is the hash of the first i letters. That is why the array is one longer than the string.

Getting the hash of any piece

Now the hard question. Suppose you want the hash of the piece from index 3 up to index 5 in abcab. That piece is ab, and its hash is 12. The prefix table holds the hash of abcab (12312) and the hash of abc (123), but it does not hold ab in the right place.

Here is the trick. The hash of abcab is made of two parts: the hash of abc, followed by the two letters ab. The hash of abc is 123. Appending two letters multiplies by 10 twice, so the first part is shifted left by two digits:

hash of abcab  = hash of abc * 10 * 10 + hash of ab
12312          = 123 * 100 + 12
12312          = 12300 + 12

To get the hash of ab alone, remove the first part. Subtract the shifted prefix:

hash of ab = hash of abcab - hash of abc * 10 * 10
           = 12312 - 123 * 100
           = 12312 - 12300
           = 12

The general rule has the same shape. For a piece from index l up to index r (not including r):

hash(l, r) = prefixHash[r] - prefixHash[l] * base^(r - l)

The term base^(r - l) means the base raised to the length of the piece. For the example, l is 3, r is 5, the length is 2, and 10^2 is 100. The formula gives 12312 - 123 * 100 = 12.

This is the whole idea of a rolling hash. After a single pass that builds the prefix array, the hash of any piece takes one subtraction and one multiplication. This is called constant time: the cost does not depend on the length of the piece.

The formula needs the power base^(r - l). The program stores these powers in a second list during the same pass. Entry i holds base^i.

Keeping the numbers small with a modulus

The numbers grow fast. A string of 20 letters with base 31 gives a hash with about 30 digits. Python integers have no fixed size, so the arithmetic never overflows, but a number with thousands of digits is slow to multiply. The fix is the remainder operator %. The remainder is what is left after dividing. In Python, 17 % 5 is 2, because 5 goes into 17 three times with 2 left over. Taking the remainder after each step keeps every number below a chosen limit called the modulus. A common modulus is 1_000_000_007, a prime number near one billion.

Taking remainders does not break the formula. The hash of a piece is still correct when each step works modulo the same number. There is one new problem. Subtraction can make a negative number. In some languages the remainder of a negative number is negative, but Python's % with a positive modulus always returns a value from 0 up to the modulus minus one. So -7 % 5 is 3 in Python. That is why the function below needs no extra line to fix negative results.

With a modulus near one billion, each stored value is below about one billion. Multiplying two of them gives a number below about 10 to the 18th. Python handles that size without any special type, which is the reason the code can use plain integers.

Example 1: the RollingHash class

The class below builds the prefix and power lists in one pass. It answers hash questions for any piece in constant time. The main part of the file checks the answers against a slow direct calculation for every piece of the word banana.

The output is:

hash of ana at 1..4: 96724
hash of ana at 3..6: 96724
hash of ban at 0..3: 97295
naive hash of ana: 96724
all substrings match naive hash: True

The first two lines show that the two ana pieces, at different positions, get the same hash. The line all substrings match naive hash: True shows that the fast hash method agrees with the slow direct calculation for every piece of banana. The naive method costs time proportional to the piece length, so it is only used here as a check.

The constructor is the one pass over the string. It runs once, and it fills two lists of length n + 1. The hash method does one multiplication, one subtraction and one remainder. It never reads the characters of the piece.

The constructor line self.power[0] = 1 % mod stores the power of the base to the zero, which is 1. Writing 1 % mod instead of 1 keeps every stored number below the modulus, which matters only when the modulus is 1.

Collisions: different text, same hash

A collision happens when two different pieces of text have the same hash. The hash is a number below the modulus, so there are only a fixed number of possible hashes. With a small modulus, collisions are easy to find.

The next part uses a modulus of 101 instead of one billion. With only 101 possible hash values, and 676 two-letter strings made from lowercase letters, some two strings must share a hash. This is the pigeonhole idea: if you put 676 letters into 101 boxes, some box holds more than one.

The function below searches the two-letter strings and reports the first pair that shares a hash:

def find_collision(mod):
    seen = {}
    for a in "abcdefghijklmnopqrstuvwxyz":
        for b in "abcdefghijklmnopqrstuvwxyz":
            t = a + b
            h = RollingHash(t, 31, mod).hash(0, 2)
            if h in seen:
                return seen[h], t
            seen[h] = t
    return None
 
pair = find_collision(101)
print("colliding pair with mod 101:", pair[0], "and", pair[1])
both = pair[0] + pair[1]
small = RollingHash(both, 31, 101)
print("hash(0,2) =", small.hash(0, 2), ", hash(2,4) =", small.hash(2, 4))
print("hashes equal:", small.hash(0, 2) == small.hash(2, 4))

The output is:

colliding pair with mod 101: aa and di
hash(0,2) = 74 , hash(2,4) = 74
hashes equal: True

This block uses the RollingHash class from the previous example, so define the class first.

The pair is aa and di. Here is the check by hand. The letter a has code 97, and d has code 100, i has code 105:

hash of aa = 97 * 31 + 97   = 3104
3104 mod 101 = 3104 - 30 * 101 = 3104 - 3030 = 74
 
hash of di = 100 * 31 + 105 = 3205
3205 mod 101 = 3205 - 31 * 101 = 3205 - 3131 = 74

Both are 74, but aa and di are not the same text. The program joins them into aadi and asks for the hash of the two halves. The hashes match, so the cheap test says "maybe the same". The character check says "not the same". The line characters equal: False in the next example shows the second check at work.

This is why the function same_substring checks the hash first and then the characters. The rule is:

• If two hashes differ, the pieces are definitely different. The program can stop there.
• If two hashes match, the pieces are probably the same. The program must compare the characters to be sure.

The character comparison is the slice comparison s[i:i + length] == s[j:j + length]. It returns true only when the characters match. The check costs time proportional to the length, but it runs only when the hashes match. With a large modulus, that happens rarely for real data, so most comparisons still cost constant time.

def same_substring(s, rh, i, j, length):
    if rh.hash(i, i + length) != rh.hash(j, j + length):
        return False
    return s[i:i + length] == s[j:j + length]
 
both = "aadi"
small = RollingHash(both, 31, 101)
print("characters equal:", same_substring(both, small, 0, 2, 2))

The output is:

characters equal: False

A second, separate hash with a different base or modulus is another way to make collisions rare. The program then needs two matching hashes before it trusts the answer. The character check is simpler to get right, and it always gives a correct answer.

Example 2: counting equal pairs

The next example uses the rolling hash inside a bigger job. The task is to count pairs of positions where a piece of length k appears twice in the string, with the first position before the second.

The string abcabcab has these pieces of length 3, one for each start position from 0 to 5:

start 0: abc
start 1: bca
start 2: cab
start 3: abc
start 4: bca
start 5: cab

Three pairs match: starts 0 and 3 both give abc, starts 1 and 4 both give bca, and starts 2 and 5 both give cab.

The naive version compares every pair of starts. With n starts, that is about n * n / 2 pairs, and each comparison costs up to k steps. The rolling hash version does something smarter. It keeps a list of earlier starts for each hash value, in a dict. For each new start i, it looks only at the earlier starts whose hash matches. That keeps the work small when most pieces have different hashes.

The output is:

equal pairs of length 3 in abcabcab: 3
naive count: 3

The output agrees with the list of pieces above. Here is the behaviour for abcabcab, step by step:

• Start 0 has hash H_abc. The dict is empty, so nothing is counted. The dict now holds H_abc -> [0].
• Start 1 has hash H_bca. Nothing matches. The dict now also holds H_bca -> [1].
• Start 2 has hash H_cab. Nothing matches yet.
• Start 3 has hash H_abc. The dict has [0] under that hash. Check position 0 against position 3. They match, so the count is 1.
• Starts 4 and 5 do the same, which adds 2 more. The total is 3.

Each start is looked up once, and only the matching hash bucket is checked. The defaultdict(list) creates an empty list the first time a hash appears, and returns the existing list after that. The bucket.append(i) line runs after the checks, so a start never pairs with itself.

Example 3: where the hash is a shortcut, not a guarantee

The third example asks a question that depends on the collision rule. Given a string s and a length k, count how many positions i have a piece that matches the first k letters of the string.

The function matches_prefix answers this for one position. It first checks that the piece fits inside the string, then calls same_substring to compare the piece at i with the piece at 0:

def matches_prefix(s, rh, i, k):
    if i + k > len(s):
        return False
    return same_substring(s, rh, 0, i, k)

The boundary check on the first line matters. The rolling hash only works for pieces that lie inside the string. Asking for a piece that runs past the end is a mistake, which the next section covers.

For the string abcabcab with k equal to 3, the prefix is abc. The pieces at positions 0 and 3 match it, so the count is 2. The position 6 gives only ab, which is too short, so it does not count.

Common mistakes

Doing the arithmetic in a fixed-size integer. A language with fixed-size integers, such as Java's int, wraps large results around and prints a wrong number with no error. Python does not do that. Its integers grow as needed, so 2_000_000_000 * 2 prints 4000000000. The cost is speed: a hash that is never reduced by the modulus grows with every step, and multiplication of huge numbers is slow. Always take the remainder after each multiplication, as the class does.

Letting a letter have the value 0. If the value of a letter is ord(ch) - ord("a"), then a has value 0. A zero adds nothing to the running number, so different strings can share a hash. The next program shows the problem:

The output is:

zero-valued letter a: 0
zero-valued aa: 0

The strings a and aa both hash to 0. The fix is to use the character's own code, ord(ch), as the RollingHash class does, or to add 1 to the offset value so that no letter is zero.

Making the prefix list one slot too short. The prefix list needs n + 1 entries, one for each prefix length from 0 to n. If it has only n entries, reading the last prefix fails:

The output is:

prefix length: 6
IndexError: list index out of range

The word banana has 6 letters, so the list has 6 slots, numbered 0 to 5. The prefix for the whole word is at index 6, which does not exist. The fix is [0] * (len(s) + 1). The same error appears if you ask for hash(start, end) with end larger than the length of the string.

Trusting a hash match without a character check. A matching hash only means the pieces are probably equal. For a small modulus like 101, collisions appear in a few lines of code. Always call same_substring, or compare the characters, before you report a match.

Comparing hashes made with different settings. Two RollingHash objects only give comparable numbers when they use the same base and the same modulus. A hash made with modulus 101 and a hash made with modulus one billion are different numbers, even for the same text. Keep the settings in one place, such as one object per string.

Practice

Exercise 1

Build the prefix list for a string of 10 letters. How many entries does it have, and what does entry 0 hold?

Show the answer

The list has 11 entries, numbered 0 to 10. Entry 0 is the hash of the empty prefix, which is 0. Entry i is the hash of the first i letters. The list is one longer than the string because the empty prefix needs a slot.

Exercise 2

Use the values a = 1, b = 2, c = 3, base 10, and no modulus. The word is abcab. Find the hash of the piece from index 0 up to index 2, and the hash of the piece from index 3 up to index 5. Are they equal?

Show the answer

The prefix hashes are 0, 1, 12, 123, 1231 and 12312. The piece from 0 to 2 is ab, with hash 12 - 0 * 10^2 = 12. The piece from 3 to 5 is also ab, with hash 12312 - 123 * 10^2 = 12312 - 12300 = 12. Both are 12, so the pieces are equal.

Exercise 3

Write a function count_matches(s, rh, k) that returns how many positions i have a piece of length k equal to the prefix of length k. Use the rules from matches_prefix.

Show the answer

def count_matches(s, rh, k):
    count = 0
    for i in range(len(s)):
        if matches_prefix(s, rh, i, k):
            count += 1
    return count

For abcabcab and k equal to 3, the function returns 2, because the pieces at positions 0 and 3 are both abc.

Exercise 4

A student writes if rh.hash(i, i + k) == rh.hash(j, j + k): return True and nothing else. Give one input where this returns the wrong answer, and say why the check is only a shortcut.

Show the answer

Take s = aadi, k = 2, and a RollingHash with base 31 and modulus 101. The pieces at positions 0 and 2 are aa and di. Both have the hash 74, but they are different text. The student's function returns true for them, which is wrong. The hash only says the pieces are probably equal. The character comparison is needed to confirm it.

Exercise 5

With letter values as the raw character codes, what is the hash of the single letter a under a very large modulus such as 1_000_000_007? Why does this avoid the zero-value mistake?

Show the answer

The letter a has code 97, so its hash is 97. The number is below the modulus, so the remainder does not change it. The zero-value mistake happens only when a letter gets the value 0, and the code 97 is never 0. Using the raw character codes keeps every letter's value above zero.

Summary

• A rolling hash turns a string into a number, using a base and a modulus.
• A prefix list holds the hash of every prefix. It is built in one pass and is one entry longer than the string.
• The hash of any piece is prefix[r] - prefix[l] * base^(r - l), taken modulo the chosen number, which takes constant time per question.
• A matching hash only suggests equal text. Compare the characters before you trust a match.
• Python integers do not overflow, but the remainder after each step keeps the numbers small and fast. Python's % always gives a result from 0 up to the modulus minus one, so negative results need no fix.