算法-哈希表

哈希表

存储结构： 1拉链法 2开放寻址法
哈希处理：在哈希表中一般只有添加和查找
哈希表的作用：将一个较大的空间映射成从0-N h(x)映射（0,10^5)
如何映射
x mod 10^5 将所有数取余保存在0 - 10^5里面(取模的数一般用质数)

• 快速求一个质数

for(int i = 1e5; ; i++)
{
    bool flag = true;
    for(int j = 2; j * j <= i; j++)
        if(i%j == 0)
        {
            flag = false;
            breakl
        }
    if(falg)
    {
        cout << i << endl;
        break;
    }
}

• 发生冲突使用拉链法在槽中接一个链子（链表）

//拉链法
#include <iostream>
#include <cstring>//memset()
using namespace std;
const int N = 100003;//必须是最大范围的质数，如果不是质数取余可能的零
int h[N],e[N],ne[N],idx;//h槽，e链表的值，ne链表的下标，idx当前链表值所在的下标
void insert(int x)
{
    int k = (x % N + N) % N;//将x映射到0 - N的范围中，防止是负数用N+N
    e[idx] = x;
    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);//初始化让链表下标指向-1
    while(n--)
    {
        char op;
        cin >> op;
        int x;
        if(op == 'I')
        {
            cin >> x;
            insert(x);
        }
        else
        {
            cin >> x;
            if(find(x)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }
    return 0;
}

• 开放寻址法（上厕所）当前槽有人去下一个槽知道找到没人的槽

开的空间需要是规定空间的二倍的质数