The concept and application of hash table

Hash table is an algorithm that we have to master

1. hash Tabular 2 Applications

It is commonly used to convert a large range of data , But it is usually discrete , Map a large range of data to a small range of question types . Explained between Interval and This is the type of question .

1.1. Zipper method

such as L The value range is [-10⁹ - 10⁹] , We need to map to 10⁵ Within the scope of
The common practice is ：

1. First pair x mod 10⁵ （ there 10⁵ It is random , If you want less conflict value , The experience value is 131 Or is it 13331）
2. Handling conflicts （ Because mapping from a large range to a small range may probably repeat ） Example ： h(11) = 3, h(23) = 3 （ here h A function is a hash function ）

Generally in the hash table , As long as the operation is to add and find , If you really need to delete , A mark should be made on the corresponding mark position

Look for a greater than 100000 The prime number of
code:

#include <iostream>

using namespace std;

int main()
{
    
    for(int i = 100000;; i ++)
    {
    
        bool flag = true;
        for(int j = 2; j * j <= i; j ++)
            if(i % j == 0)
            {
    
                flag = false;
                break; 
            }
        if (flag)
        {
    
            cout << i << endl;
            break;
        }
    }
    return 0;
}

1.2. Open addressing

Another open addressing method is introduced in this article ：
https://blog.csdn.net/qq_39486027/article/details/125096272

Open addressing ： Generally, the open array is originally a small range 2-3 times
add to ：

1. after h(x) Find out where it should exist ;
2. See if there is anyone in this position , If someone goes on , Until no one , preservation ; If no one , Save directly .

lookup ：

• Directly find the specified location , If there are elements , Compare whether to find the value , It's not equal to , See if the next position is , By analogy , Until you find or no element next time

Delete ：

• To find the first , If you find it , Make a mark

Here is a related simulation hash Get examples ：

2. hash Examples of tables

subject ：
Maintain a collection , The following operations are supported ：

I x, Insert a number x;
Q x, Ask the number x Whether there has been... In the collection ;
Now it's time to N operations , For each query operation, the corresponding result is output .

Input format
The first line contains integers N, Represents the number of operations .

Next N That's ok , Each line contains an operation instruction , The operation instruction is I x,Q x One of the .

Output format
For each inquiry instruction Q x, Output a query result , If x In the collection , The output Yes, Otherwise output No.

Each result takes up one line .

Data range
1≤N≤105
−109≤x≤109

sample input ：
5
I 1
I 2
I 3
Q 2
Q 5
sample output ：
Yes
No

2.1 Zipper method code implementation ：

Code:

#include <iostream>
#include <cstring>
using namespace std;

const int N = 100003;
int h[N], e[N], ne[N], idx;

///  Zipper method 
void insert(int x)
{
    
    int k = (x % N + N) % N;
    e[idx] = x;     //  Insertion of single chain table  
    ne[idx] = h[k];
    h[k] = idx ++;
}

bool find(int x)
{
    
    int k = (x % N + N ) % N;
    for(int i=h[k]; i != -1; i= ne[i])
        if(e[i] == x)
            return true;
    return false;
}

int main()
{
    
    int n;
    cin >> n;
    memset(h, -1, sizeof h);

    while(n --)
    {
    
        char op[2];
        int x;
        cin >> op >> x;
        if(op[0] =='I') insert(x);
        else
        {
    
            if(find(x)) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}

2.2 Open addressing code implementation ：

Code:

#include <iostream>
#include <cstring>
using namespace std;

const int N = 200003, null = 0x3f3f3f3f;
int h[N];

//  Open addressing 
//  Back to x ：  exist ,  return x The location of 
//  If it doesn't exist ,  What is returned is the location that should be stored 
int find(int x)  
{
    
    int k = (x % N + N) % N;

    while(h[k] != null && h[k] != x)
    {
    
        k++;
        if(k == N) k = 0;
    }
    return k;
}


int main()
{
    
    int n;
    cin >> n;
    memset(h, 0x3f, sizeof h);

    while(n --)
    {
    
        char op[2];
        int x;
        cin >> op >> x;
        if(op[0] =='I') 
        {
    
            int k = find(x);
            h[k] = x;
        }
        else
        {
    
            int k = find(x);
            if(h[k] != null)  puts("Yes");
            else puts("No");
        }
    }

    return 0;
}

3. character string hash The way

The other is string hash.

3.1 character string hash Treatment principle

Here is about string prefix hash
for example ： str = “ABCDEFG”
We make use of hash The function needs to find the string prefix hash , What is a string prefix hash
h[0] = 0
h[1] = “A” Of hash value
h[2] = “AB” Of hash value
h[3] = “ABC” Of hash value
…

So how do we define this prefix hash value , The step method used here is like this

for example ： str = “ABCD”

First step ： Put the above characters Mapped from 1 At the beginning A - 1; B - 2 …
The second step ： Consider the above string as a P Binary number （1234）p . there P It's an experience value ： 131 Or is it 13331.
The third step ： And then put the top P The base number is converted to Decimal numbers . then mod A number 264. To ensure that there is no conflict .
（1 * P3 + 2 * P2 + 3 * P 1 + 4 * P 0） mod （264）.
Here it maps to hash Values are guaranteed not to conflict , Therefore, there is no need to consider the way of conflict handling .

【 Be careful 】：

1. Characters cannot be mapped to 0
   2. Suppose the character is good enough , There is no conflict , Generally speaking , p take 131、13331 yes ;q take 2⁶⁴ when , There is little conflict .

3.2 String hash Calculation derivation

With the prefix string calculated above hash value , We can calculate the hash value , How to do it?

for instance ： Requirements for joining L-R In this section hash value .

Because what is known is the prefix hash value ,h[R] 、h[L - 1] We all know .
We regard this paragraph as P Binary number , So the left side is high , The right is low .

The calculation formula is given in the figure

In some topics , It can only be processed with string hash , use kmp It's not as good as this method , So he must know

3.3 String hash application example

Here is a related example

subject ：
Given a length of n String , Re given m A asked , Each query contains four integers l1,r1,l2,r2, Please judge [l1,r1] and [l2,r2] Whether the strings and substrings contained in these two intervals are exactly the same .
The string contains only uppercase and lowercase English letters and numbers .
Input format
The first line contains integers n and m, Represents the length of the string and the number of queries .
The second line contains a length of n String , The string contains only uppercase and lowercase English letters and numbers .
Next m That's ok , Each line contains four integers l1,r1,l2,r2, Indicates the two intervals involved in a query .
Be careful , The position of the string is from 1 Numbered starting .
Output format
Output a result for each query , If two string substrings are identical, output “Yes”, Otherwise output “No”.
Each result takes up one line .
Data range
1≤n,m≤105

sample input ：
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2

sample output ：
Yes
No
Yes

3.4 String hash code implementation

Code：

#include <iostream>
using namespace std;

typedef unsigned long long ULL;
const int N = 100010, P = 131;  //  there P  It's experience  131 , perhaps 13331

int n,m;
char str[N];
//  Here we use unsigned long long  Storage is equivalent to mod 2 ^ 64,  Because it will overflow if it exceeds 
ULL h[N], p[N];   // h[] Is to store the string hash value  p[]  Is stored p Subordinate  

ULL get(int l, int r)
{
    
    return h[r] - h[l -1] * p[r - l + 1];     //  Section hash  Formula 
}

int main()
{
    
    scanf("%d%d%s", &n, &m, str + 1);
    
    p[0] = 1;
    for(int i=1; i<=n; i++)
    {
    
        p[i] = p[i-1] * P;  // p Array save   The power of calculation 
        h[i] = h[i-1] * P +str[i];   //  Calculate the prefix of the string ,  The back is 0 Time   So just add str[i] That's it 
    }
    
    while(m -- )
    {
    
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        if(get(l1, r1) == get(l2, r2)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

Recommend a free open course of zero sound College , Personally, I think the teacher spoke well , Share with you ：Linux,Nginx,ZeroMQ,MySQL,Redis,fastdfs,MongoDB,ZK, Streaming media ,CDN,P2P,K8S,Docker,TCP/IP, coroutines ,DPDK Etc , Learn now