We saw a neat way to recover hashes using rolling hash, but unfortunately, we still ended up with a hashing collision in the case of palindromic strings. Simply multiplying primes will not make a good hash function. For this reason, the Rabin-Karp algorithm uses a Polynomial Hash Function. This is a combination of sums and products (as opposed to only products) to make the final output more unique and therefore almost entirely immune to hash values colliding.
In Python, a polynomial hash of a string 'ABCD'
can be calculated as follows:
ord('A') * 26**3 + ord('B') * 26**2 + ord('C') * 26**1 + ord('D') * 26**0
In this exercise, we will implement the same idea but automate the process using for
loops.
Instructions
Complete the function polynomial_hash()
to return the polynomial hash of a generic substring s
of uppercase
. Using the example above as a reference that showed you how to calculate the polynomial hash of 'ABCD'
, think about how you would do this for any generic substring.
Use a for
loop to iterate through all character indexes in s
. Then sum up the individual contributions of each character towards the total polynomial hash of s
.
The contribution of each character is its ASCII value multiplied by some power of 26
. The exponent of 26
starts at len(s)-1
for the first character and goes down by 1
for each subsequent character.
Use string slicing and a for
loop to access all the substrings of length 4
in uppercase
. Find the polynomial hash of each of these substrings using the polynomial_hash()
function you have just implemented.
Store the mapping of each substring of length 4
to its corresponding polynomial hash in the polynomial_hash_values
dictionary.