The polynomial rolling hash function

Polynomial rolling hash function is a hash function that uses only multiplications and additions. The following is the function:

or simply,

Where

The input to the function is a string of length .
and are some positive integers.
The choice of and affects the performance and the security of the hash function.
If the string consists of only lower-case letters, then is a good choice.
- Competitive Programmers prefer using a larger value for . Examples include , , .
shall necessarily be a large prime since the probability of two keys colliding (producing the same hash) is nearly . and are widely used values for .
The output of the function is the hash value of the string which ranges between and inclusive.

Below is the implementation of the Polynomial Rolling Hash Function

C++

#include <bits/stdc++.h>
using namespace std;
 
struct Hash {
    long long p = 31, m = 1e9 + 7;
    long long hash_value;
    Hash(const string& s)
    {
        long long hash_so_far = 0;
        long long p_pow = 1;
        const long long n = s.length();
        for (long long i = 0; i < n; ++i) {
            hash_so_far
                = (hash_so_far + (s[i] - 'a' + 1) * p_pow)
                  % m;
            p_pow = (p_pow * p) % m;
        }
        hash_value = hash_so_far;
    }
    bool operator==(const Hash& other)
    {
        return (hash_value == other.hash_value);
    }
};
 
int main()
{
    const string s = "w3wiki";
    Hash h(s);
    cout << "Hash of " << s << " is: " << h.hash_value
         << '\n';
    return 0;
}

C

#include <stdio.h>
#include <string.h>
 
int get_hash(const char* s, const int n) {
    long long p = 31, m = 1e9 + 7;
    long long hash = 0;
    long long p_pow = 1;
    for(int i = 0; i < n; i++) {
        hash = (hash + (s[i] - 'a' + 1) * p_pow) % m;
        p_pow = (p_pow * p) % m;
    }
    return hash;
}
 
int main() {
    char s[] = "w3wiki";
    int n = strlen(s);
    printf("Hash of %s is %d\n", s, get_hash(s, n));
    return 0;
}

Java

class Hash {
    final int p = 31, m = 1000000007;
    int hash_value;
    Hash(String S)
    {
        int hash_so_far = 0;
        final char[] s = S.toCharArray();
        long p_pow = 1;
        final int n = s.length;
        for (int i = 0; i < n; i++) {
            hash_so_far = (int)((hash_so_far
                                 + (s[i] - 'a' + 1) * p_pow)
                                % m);
            p_pow = (p_pow * p) % m;
        }
        hash_value = hash_so_far;
    }
}
 
class Main {
    public static void main(String[] args)
    {
        String s = "w3wiki";
        Hash h = new Hash(s);
        System.out.println("Hash of " + s + " is "
                           + h.hash_value);
    }
}

Python3

class Hash:
    def __init__(self, s: str):
        self.hash_value = 0
        self.p, self.m = 31, 10**9 + 7
        self.length = len(s)
        hash_so_far = 0
        p_pow = 1
        for i in range(self.length):
            hash_so_far = (hash_so_far + (1 + ord(s[i]) - ord('a')) * p_pow) % self.m
            p_pow = (p_pow * self.p) % self.m
        self.hash_value = hash_so_far
     
    def __eq__(self, other):
        return self.hash_value == other.hash_value
 
 
if __name__ == '__main__':
    s = "w3wiki"
    h = Hash(s)
    print("Hash value of {} is {}".format(s, h.hash_value))

C#

//C# program to implement the above approach
using System;
 
public struct Hash
{
    public long p;    // the prime number used for the hash function
    public long m;    // the modulus used for the hash function
    public long hash_value;     // the hash value of the string
 
    public Hash(string s)
    {
        p = 31;
        m = 1000000007;
        long hash_so_far = 0;
        long p_pow = 1;
        long n = s.Length;
        for (long i = 0; i < n; ++i)
        {
            hash_so_far = (hash_so_far + (s[(int)i] - 'a' + 1) * p_pow) % m;
            p_pow = (p_pow * p) % m;
        }
        hash_value = hash_so_far;
    }
 
    public static bool operator ==(Hash a, Hash b)
    {
        return a.hash_value == b.hash_value;
    }
 
    public static bool operator !=(Hash a, Hash b)
    {
        return !(a == b);
    }
}
 
//Driver code
public class MainClass
{
    public static void Main()
    {
        string s = "w3wiki";
        Hash h = new Hash(s);
        Console.WriteLine($"Hash of {s} is: {h.hash_value}");
    }
}
//contributed by adityasha4x71

Javascript

// Calculates the hash value of a string using a polynomial rolling hash function.
 // @param {string} s - The input string.
 // @returns {number} The hash value of the input string.
function get_hash(s) {
    const p = 31;
    const m = 1e9 + 7;
    let hash = 0;
    let pPow = 1;
    for (let i = 0; i < s.length; i++) {
        hash = (hash + (s.charCodeAt(i) - 'a'.charCodeAt(0) + 1) * pPow) % m;
        pPow = (pPow * p) % m;
    }
    return hash;
}
 
const s = "w3wiki";
console.log(`Hash of ${s} is ${get_hash(s)}`);

Output

Hash of w3wiki is 609871790

Time Complexity: O(N)

Auxiliary Space: O(1)

The polynomial rolling hash function

C++

C

Java

Python3

C#

Javascript

String hashing using Polynomial rolling hash function

Categories

Contact US

The polynomial rolling hash function

C++

C

Java

Python3

C#

Javascript

String hashing using Polynomial rolling hash function

Similar Reads

Categories

Contact US