【25. 哈希表】

模拟散列表

概述

• 哈希表又称散列表，一般由Hash函数（散列函数）与链表结构共同实现。

用途

• 添加元素
• 通过遍历来查找相应元素。（之所以用哈希是因为它的时间复杂度接近O(1)）

思路

• 将一个比较复杂的数据结构映射到下标从0~N的容易维护的值域内。因为值域比较简单、范围小、就会产生不同的原始值信息被Hash函数映射为相同的值，因此要处理这种冲突。
• 处理冲突的办法有俩种：拉链法和开放寻址法（蹲坑法）

哈希表与离散化区别

• 之前离散化也是通过映射的方法，将比较大的数的值映射成比较小的数。
• 离散化是一种特殊的哈希方式，这里是一般意义的哈希方式。
• 离散化有一个重要特点是需要保序。Hash这个函数需要单调递增。

拉链法

步骤

• H(x) = X mod P。这里的P是一个比较大的数，但不能超过题目规定的N
• 处理冲突

处理冲突主要通过数组，下面拉一个链表的方式，所以简称拉链法

当几个原始值，通过Hash函数映射到同一个值时，我们就把它们依次挂载到该值下面的链表上。

为了减少冲突次数，这里mod的那个数一般值质数

找到大于100000的质数

 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;
        }
    }
运行结果是100003

代码

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

const int N = 100003;
int h[N], e[N], ne[N];   //h[N]表示槽，e[]和ne[]表示链表，我们需要将链表放到槽上。
int idx;

void insert(int x)
{
    int k = (x % N + N) % N;   //哈希函数将x映射到从0~N之间的一个数，防止出现负数所以+N，%N；
                               //c++中如果是负数 那他取模也是负的 所以 加N 再 %N 就一定是一个正数
    e[idx] = x;                //这就是单链表，插入数
    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));   //清空槽，空指针用-1表示
    
    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;
}

开放寻址法

• 开放寻址法一般开 数据范围的 2~3倍, 这样大概率就没有冲突了
• 拉链法中的N 是最接近最大范围（10的5次方的质数） 开放寻址法中，一般需要开固定槽的两到三倍（防止冲突，故选择2*10的五次方最近的质数

（只有这样开，不冲突的概率为99.99）

步骤

代码

#include <iostream>
#include <cstring>
using namespace std;
                      
const int N = 200003；  //开坑位的时候，一般是2~3倍，此时不会导致溢出
null = 0x3f3f3f3f;     //约定一个标志，如果数组中的某个数等于这个数时，说明这个位置上没有人。（用一个数表示这个位置是空的）
int h[N];               //开放寻址法，只需要一个数组。蹲坑法


int find(int x)  //如果x在哈希表中已经存在吗，就返回的是x所在的位置，如果x在哈希表中不存在，返回的是它应该存储的位置
{
    int k =(x % N + N) % N;  //哈希函数将x映射到从0~N之间的一个数，防止出现负数所以+N，%N；
    while (h[k] != null && h[k] != x)
    {
        k ++;
        if (k == N) k = 0;           //如果没找到，就从头找
    }
    return k;
    
}

int main()
{
    int n ;
    scanf("%d", &n);
    memset(h, 0x3f, sizeof(h));   //按字节进行memset(不是按数),h是一个int型数组，一共有4个字节，每个字节都是0x3f
                                  //因此每个数是4个0x3f，int有4个字节，把每个字节都变成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