$ \huge 链地址法 $

• 关于$ \space mod \space $运算

在数学中的模运算的结果均为正数，公式：$\color{red}{a \% b = a - \lfloor a/b \rfloor * b}$，如 -10 % 3 = 2。
但是在 $C++$ 中却并非如此，而是正数取模是正数，负数取模是负数，即-10 % 3 = -1，若想得到$2$，需$+3$

• $ hash地址的范围 $

地址范围尽量取质数

$ 求质数 $

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

$ 代码 $

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

const int N = 1e5 + 3;

int h[N], e[N], ne[N], idx;
// h[] 既是 hash 的映射，又存的头结点下标
// e[] 存元素
// ne[] 对应 e[] 的 next 下标

int n;

void insert(int x)
{
    int k = ((x % 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()
{
    scanf("%d", &n);
    char op[2];
    int t;
    
    memset(h, -1, sizeof h);
    while(n -- )
    {
        scanf("%s%d", op, &t);
        if (*op == 'I') insert(t);
        else {
            if (find(t))    puts("Yes");
            else    puts("No");
        }
            
    }
    return 0;
}

$ \huge 开放寻址法 $

$memset(h, 0x3f, sizeof h);$

1. memset是按字节来初始化的，int中有四个字节，初始化成0x3f就是将每个字节都初始化成0x3f，所以每个int就是 0x3f3f3f3f
2. 数组长度一般开到个数上限的2-3倍。

在算法竞赛中，我们常常需要用到设置一个常量用来代表“无穷大”。

比如对于int类型的数，有的人会采用INT_MAX，即0x7fffffff作为无穷大。但是以INT_MAX为无穷大常常面临一个问题，即加一个其他的数会溢出。

而这种情况在动态规划，或者其他一些递推的算法中常常出现，很有可能导致算法出问题。

所以在算法竞赛中，我们常采用0x3f3f3f3f来作为无穷大。0x3f3f3f3f主要有如下好处：

0x3f3f3f3f的十进制为1061109567，和INT_MAX一个数量级，即10^9数量级，而一般场合下的数据都是小于10^9的。
0x3f3f3f3f * 2 = 2122219134，无穷大相加依然不会溢出。
可以使用memset(array, 0x3f, sizeof(array))来为数组设初值为0x3f3f3f3f，因为这个数的每个字节都是0x3f。

$ while \space (h[k]\space !=\space null\space \&\& \space h[k]\space !=\space x\space ) $

• 为什么不会发生死循环？答：我们开的范围是个数上限的几倍，说白了就是根本装不满，一定会有$null$的位置

#include <iostream>
#include <cstring>

using namespace std;

const int N = 2e5 + 3;

#define null 0x3f3f3f3f

int h[N];

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 main()
{
    int n;
    scanf("%d", &n);
    
    memset(h, 0x3f, sizeof h);
    
    char op[2];
    int x;
    while(n -- )
    {
        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;
}

练习：模拟散列表