String Hashing

হ্যাশ এবং হ্যাশিং কি?    Introduction to Hash Table

String hashing function,

                       

where p is normally a prime greater than the alphabets size. But here is a problem for a large string, the result can be huge.

So let’s introduce a big number m, usually closer to INT MAX.

                                                

Since we chose m, there could be a chance that the mod values of two different string are same! Probability of that happening is close to 1/m .

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const ll p = 100050001;

const ll m = 1e9+7;

ll Hash(string s)

{

    /// value = hash value

    ll value = 0, mul = 1;

    int sz = s.size();

    for(int i=0; i<sz; i++)

    {

        value = (value + (mul * s[i])) % m;

        mul = (mul * p) % m;

    }

    return value;

}

int main()

{

    string s = "HappyNewYear";

    cout << "Hash value :: " << Hash(s) << "\n";

    return 0;

}