闭散列方法(开放寻址法)

当两个不同的关键字,他们的查找序列(寻址序列)的地址接近的时候,
再往后续查找的序列重叠可能性大的话,就容易发生聚集.

改进方法:

a.线性探查法,容易产生聚集序列d(i)=(d(0)+i*c)%M   (一般都写这种)
b.二次探查法,产生聚集的问题不大,但易产生二级聚集问题.
    d(2i - 1) = (d(0) + i^2) % M
    d(2i) = (d(0) - d^2) % M
c.随机探查法,易产生二级聚集问题,其原因在于每次随机序列不变
区别:
聚集:两个关键字映射到两个不同的位置,后续探查序列有交集的问题
二级聚集:两个关键字映射到同一个位置的话,那么后续探查序列都一样的问题,
    其原因在于只跟下标有关,跟数值无关
d.双散列探查法,前三种只跟下标有关,导致后面的序列都是固定的,
因此双散列还与数值有关,加一个有关于数值的哈希函数,因此可以减少聚集概率

补充:哈希表一般不进行删除操作,要删除也就在对应位置上打个标记,如果删除的多了,就直接把所有元素重新哈希一遍即可

#include <iostream>
#include <cstring>
#include <algorithm>
#define N 200003
#define null 0x3f3f3f3f  //正无穷
using namespace std;

int n;
int h[N];

int find(int x)
{
    //注意这种写法跟笔试有区别,别混淆,数学上写法不需要+N
    int t = (x % N + N) % N;
    while (h[t] != null && h[t] != x)
        t = (t + 1) % N;
    return t;
}

int main()
{
    memset(h, 0x3f, sizeof h);  //按字节来初始化,每个int是4哥字节,也就处理成了0x3f3f3f3f
    scanf("%d", &n);
    while (n -- )
    {
        char op[2];
        int x;
        scanf("%s%d",op,&x);
        if(*op == 'I')  h[find(x)] = x;
        else
        {
            if(h[find(x)] == null)  puts("No");
            else    puts("Yes");
        }
    }
     return 0;
}

笔试补充：

1. 在笔试里存储效率指的是空间，查找效率指的是时间；
2. 存储的越稀疏，冲突的概率越低，效率越高，所以装载因子越小越好
3. 存储效率是指存储的元素除以数组总长度
4. 散列函数会影响堆积，堆积不影响散列函数，而堆积会影响平均查找长度
5. 如果问查找失败的平均查找长度且是线性探测法，看%n当中的n是几，然后直接从起始位置找到n后面则查找失败，一般都是每一种余数出现的概率都是一样的，然后对于每一种余数来求就可以了，