[25. Hash table]

Simulation hash table

summary

• Hashtable also called Hash table , Generally by Hash function （ Hash function ） And Linked list Structure together .

purpose

• Additive elements
• Find the corresponding element through history .（ Hash is used because its time complexity is close to O(1)）

Ideas

• Compare a Complex data structures Map to subscript from 0~N Within the easy to maintain value range . Because the value range is relatively simple 、 Small scope 、 It will produce Different raw value information is Hash Function maps to the same value , So deal with this conflict .
• There are two ways to deal with conflicts ： Zipper method and Open addressing （ Squatting method ）

The difference between hash table and discretization

• Previously, discretization is also through the method of mapping , Map the value of a larger number to a smaller number .
• Discretization is a special hash method , Here is the hash method in the general sense .
• An important feature of discretization is the need Keep the order .Hash This function needs Monotone increasing .

Zipper method

step

• H(x) = X mod P. there P Is a relatively large number , But it cannot exceed the specified N
• Handling conflicts

The main way to deal with conflicts is through arrays , Next, pull a linked list , So it's called zipper method for short

When several original values , adopt Hash When a function maps to the same value , We will mount them to the linked list under the value in turn .

To reduce the number of conflicts , here mod The number of is generally a prime number

Find greater than 100000 The prime number of

 for (int i = 100000;; i ++)
    {
    
        bool flag = true;
       
        for ( int j = 2; j < i; j ++)
        {
    
            if (i %j == 0)
            {
    
                flag = false;
                break;
            }
        }
        if (flag)
        {
    
            cout << i << endl;
            break;
        }
    }
 The result of the operation is 100003

Code

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

const int N = 100003;
int h[N], e[N], ne[N];   //h[N] It means groove ,e[] and ne[] Represents a linked list , We need to put the linked list on the slot .
int idx;

void insert(int x)
{
    
    int k = (x % N + N) % N;   // The hash function will x Map to from 0~N A number between , Prevent negative numbers, so +N,%N;
                               //c++ If it's negative   Then his modulus is also negative   therefore   Add N  Again  %N  It must be a positive number 
    e[idx] = x;                // This is the single chain list , Number of inserts 
    ne[idx] = h[k];
    h[k] = idx;
    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 ;
    scanf("%d", &n);
    memset(h, -1, sizeof(h));   // Empty the tank , For empty finger needle -1 Express 
    
    while (n --)
    {
    
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        
        if (op[0] == 'I') insert(x);
        else
        {
    
            if (find(x)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

Open addressing

• Open addressing is generally open Data range 2~3 times , So there is no conflict in the probability
• Zipper method N Is the closest to the maximum range （10 Of 5 Prime number to the power ） In open addressing , It usually needs to be opened Two to three times the fixed slot （ To prevent conflict , So choose 2*10 The nearest prime number to the fifth power of

（ Only in this way , The probability of no conflict is 99.99）

step

Code

#include <iostream>
#include <cstring>
using namespace std;
                      
const int N = 200003;  // When opening the pit , It's usually 2~3 times , At this time, it will not cause overflow 
null = 0x3f3f3f3f;     // Agree on a sign , If a number in the array is equal to this number , It means that there is no one in this position .（ Use a number to indicate that this position is empty ）
int h[N];               // Open addressing , Just need an array . Squatting method 


int find(int x)  // If x Does it already exist in the hash table , Just return x Where it is , If x Does not exist in the hash table , It returns the location where it should be stored 
{
    
    int k =(x % N + N) % N;  // The hash function will x Map to from 0~N A number between , Prevent negative numbers, so +N,%N;
    while (h[k] != null && h[k] != x)
    {
    
        k ++;
        if (k == N) k = 0;           // If not , Just look from the beginning 
    }
    return k;
    
}

int main()
{
    
    int n ;
    scanf("%d", &n);
    memset(h, 0x3f, sizeof(h));   // By byte memset( Not by number ),h It's a int Type of the array , Altogether 4 Bytes , Every byte is 0x3f
                                  // So each number is 4 individual 0x3f,int Yes 4 Bytes , Turn every byte into 3f
    while (n --)
    {
    
        char op[2];
        int x;
        scanf("%s%d", 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;
}

   // cout << 0x3f << endl; 63

   // cout << 0x3f3f3f3f <<endl; 1061109567