Polynomial Hashing Function

Polynomial Hash Function : String Hashing

Suppose, we have a string s.

s = s[0] + s[1] + s[2] +......+ s[n];

   

we have a prime number P.

if the string contains only lowercase letters of the english alphabet, then the appropriate value of  P = 31.

if the input string contains both uppercase and lowercase letters, then the appropriate value of  P = 53.

for mod we choose a m.  This m should be a large prime number since the probability of two random string colliding is about ≈ 1/m. Normally we use,  m = 1000000009.

for Convenience  the values assigned to each character in english alphabet,

                         a = 1, b = 2, c = 3, ....... , z = 26.

So we can write our polynomial hashing equation,

                                                                                                                                                                

Below The Coding Part :

#include<bits/stdc++.h>

#define ll long long int

using namespace std;

ll hash_function(string s)

{

    ll p = 31;

    ll m = 1e9 + 9;

    ll hash_value = 0;

    ll p_power = 1;

    for(int i=0; i<s.size(); i++)

    {

   hash_value = (hash_value + (s[i] - 'a' + 1) * p_power) % m;

   p_power = (p_power * p) % m;

    }

    return hash_value;

}

int main()

{

    string s;

    cout << "Enter A String :: ";    /// input a lowercase string

    cin >> s;

    cout << "\nHash Value of '" << s << "' :: " << hash_function(s) << "\n";

    return 0;

}