用途

通过把一个值域很大的范围（0~10^9）映射到一个比较小的范围（0~10^5）
支持添加一个数到集合中；
查询一个数是否在集合中出现；

冲突解决办法

1. 拉链法
2. 开放寻址法

易错点

1. 没有初始化，拉链法注意初始化所有槽位都是空、开放寻址法记得初始化成特殊值
2. hash取模的时候注意N取质数，拉链法取到数据范围最近的质数；开放寻址法取4倍空间的且最近的一个质数

模板代码

开放寻址法

const int N = 200003;
const int null = 0x3f3f3f3f;

int h[N];

void init()
{
    memset(h, 0x3f, sizeof(h));
}

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 insert(int x)
{
    int k = find(x);
    h[k] = x;
}

拉链法

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

void init()
{
    idx = 0;
    memset(h, -1, sizeof(h));
}

void insert(int x)
{
    int k = (x % N + 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;
}