Hash

📌 Table of Contents

1. Introduction

In problems that involve comparing two strings, the time complexity is O(n), where n is the length of the string. For tasks that require many such comparisons, this complexity is too high.

→ That is why hashing is often used: it is easy to implement, very efficient, and has a very small error probability.

2. Idea behind

2.1 How does hashing work?

Suppose we only deal with strings consisting of lowercase English letters. Each character is mapped to a number: for example, a = 1, b = 2, …, z = 26.

Instead of characters, a string can then be represented as a number in a positional numeral system with some base. The base is usually chosen as a prime number larger than the maximum character code.

For example, with base = 31: "abz" = 31^0*1 + 31^1*2 + 31^2*26 = 25049

Thus, two identical strings will always have the same hash value. However, for long strings, the numeric value quickly grows too large to store. To handle this, we take the hash value modulo a large prime number. If the two modulo values are equal, we assume the strings are equal.

Of course, a mod m = b mod m does not guarantee a = b. The probability of such a collision is about 1/m. To reduce this further, we often use two large prime moduli at the same time. In that case, the probability of collision is about 1/(m1*m2), which is negligibly small for practical purposes.

2.2 Why should the base and modulus be prime?

If the base and modulus share common factors, patterns can repeat more frequently, increasing the chance of collisions. Choosing primes avoids this issue and ensures more uniform hash distribution.


// =======================
// Rolling Hash Template
// =======================

// Some common choices for base: 31, 41, 311, 331
// Some common choices for modulus: 1e9+7, 1e9+9, 1e9+21, 1e9+33
// Notes:
//   power[i] = base^i (mod mod[id])
//   f[i]     = hash value of substring s[1] → s[i]
// To compute hash of substring s[l…r]:
//   hash(l,r) = f[r] − f[l−1] * power[r−l+1] (mod mod[id])

const int maxn = 2e6+5;
const int num  = 1e9+7;

string s;
long long n;

// double hashing: 2 bases and 2 mods
long long base[] = {31, 41};
long long mod[]  = {num, num+2};

// power[id][i] = base[id]^i mod mod[id]
// f[id][i]     = hash of prefix s[1..i] with (base[id], mod[id])
long long power[2][maxn], f[2][maxn];

// get hash of substring s[l..r] under hash function id
long long gt(int l, int r, int id) {
    return ((f[id][r] - f[id][l-1] * power[id][r-l+1]) % mod[id] + mod[id]) % mod[id];
}

void input() {
    power[0][0] = power[1][0] = 1;

    cin >> s;
    n = s.size();
    s = '*' + s; // 1-indexing

    for (int i = 1; i <= n; ++i) {
        for (int id = 0; id < 2; ++id) {
            power[id][i] = power[id][i-1] * base[id] % mod[id];
            f[id][i]     = (f[id][i-1] * base[id] + s[i] - 'a' + 1) % mod[id];
        }
    }
}
        

3. Hash XOR

Problem: Given an array of integers a of length (n ≤ 10^5) with 1 ≤ a_i ≤n and q ≤ 10^5 queries of the form (l, r). For each query, determine whether the substring a[l] → a[r] is a perfect sequence. (A perfect sequence is a permutation of the sequence 1 → (r-l+1))

We can see that: The order of the numbers does not matter

Solution:

4. Hash sum

Problem: Given a sequence of n integers a (n ≤ 10^5) with 1 ≤ a_i ≤n and q ≤ 10^5 queries of the form l, r, k, u_1, v_1, .., u_k, v_k. For each query, determine whether the substring a[l] → a[r] contains exactly u_1 numbers v_1, … , u_k numbers v_k (sum k ≤ 10^5).

Solution:


#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const char el ='\n';
const int maxn = 2e5+5;
const ll inf = 1e18+1;
ll n, a[maxn], b[maxn], sum[2][maxn];
map<ll,ll> mark;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());

ll Rand(ll l, ll r)
{
    return l + rd()%(r-l+1);
}

bool check(int l, int r, int u, int v)
{
    if(r-l+1!=v-u+1)    return false;
    return (sum[0][r] - sum[0][l-1] == sum[1][v] - sum[1][u-1]);
}

void input()
{
    cin>>n;
    for(int i=1;i<=n;++i)   cin>>a[i];
    for(int i=1;i<=n;++i)   cin>>b[i];
    for(int i=1;i<=n;++i)
    {
        if(!mark[a[i]])   mark[a[i]] = Rand(1e17,inf);
        a[i] = mark[a[i]];
    }
    for(int i=1;i<=n;++i)
    {
        if(!mark[b[i]])   mark[b[i]] = Rand(1e17,inf);
        b[i] = mark[b[i]];
    }
    for(int i=1;i<=n;++i)
    {
        sum[0][i] = sum[0][i-1] + a[i];
        sum[1][i] = sum[1][i-1] + b[i];
    }
    int q;
    cin>>q;
    for(int i=1,l,r,u,v;i<=q;++i)
    {
        cin>>l>>r>>u>>v;
        if(check(l,r,u,v))  cout<<"Yes"<<el;
        else                cout<<"No"<<el;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    input();
    return 0;
}

        

5. Hash tree

Problem: Tree Isomorphism II - CSES

Method 1: Ahu encoding (using parentheses)

Method 2: Hash sum


#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e18 + 3;
const int MaxN = 1e5 + 5;
const int Base = 31;

int n;
vector<int> grapha[MaxN];
vector<int> graphb[MaxN];

void Inp()
{
    cin >> n;
    for (int x = 1; x <= n; x++)
    {
        grapha[x].clear();
        graphb[x].clear();
    }
    for (int x = 1; x < n; x++)
    {
        int u, v;
        cin >> u >> v;
        grapha[u].push_back(v);
        grapha[v].push_back(u);
    }
    for (int x = 1; x < n; x++)
    {
        int u, v;
        cin >> u >> v;
        graphb[u].push_back(v);
        graphb[v].push_back(u);
    }
}

long long RandLL(long long l, long long r)
{
    long long res = 0;
    for (int x = 0; x < 4; x++)
    {
        res = (res << 15) ^ (rand() & ((1 << 15) - 1));
    }
    return l + res % (r - l + 1);
}

map<long long, long long> mp;

long long DFS1(int u, int p)
{
    long long k = Base;
    for (int x : grapha[u])
    {
        if (x != p)
        {
            long long q = DFS1(x, u), hashing;
            if (mp.find(q) == mp.end())
            {
                hashing = RandLL(1, 1e18);
                mp[q] = hashing;
            }
            else
            {
                hashing = mp[q];
            }
            k = (k + hashing) % mod;
        }
    }
    return k;
}

long long DFS2(int u, int p)
{
    long long k = Base;
    for (int x : graphb[u])
    {
        if (x != p)
        {
            long long q = DFS2(x, u), hashing;
            if (mp.find(q) == mp.end())
            {
                hashing = RandLL(1, 1e18);
                mp[q] = hashing;
            }
            else
            {
                hashing = mp[q];
            }
            k = (k + hashing) % mod;
        }
    }
    return k;
}

void Exc()
{
    mp.clear();
    if (DFS1(1, -1) == DFS2(1, -1))
    {
        cout << "YES" << "\n";
    }
    else
    {
        cout << "NO" << "\n";
    }
}

int main()
{
    //freopen("J.INP", "r", stdin);
    //freopen("J.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    srand(time(nullptr));
    int test = 1;
    cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    return 0;
}