【哈希表】模拟散列表「哈希表基础」

题目

840. 模拟散列表

---

维护一个集合，支持如下几种操作：

1. I x，插入一个数 $x$；
2. Q x，询问数 $x$ 是否在集合中出现过；

现在要进行 $N$ 次操作，对于每个询问操作输出对应的结果。

输入格式

第一行包含整数 $N$，表示操作数量。

接下来 $N$ 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。

输出格式

对于每个询问指令 Q x，输出一个询问结果，如果 $x$ 在集合中出现过，则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

$1 \le N \le 10^5$
$-10^9 \le x \le 10^9$

输入样例：

5
I 1
I 2
I 3
Q 2
Q 5

输出样例：

Yes
No

解题

方法一：开放寻址法

思路

哈希表的基本概念：https://gabrielxd.top/archives/learning-note-data-structures-and-algorithms#哈希表

在做算法题时，一般我们设计哈希时哈希函数使用取余法，处理哈希冲突的方式选择开放寻址 - 线性探测法或是链地址 - 拉链法。

取余法：把 x 对 N 取余，这样就可以把一个较大的数映射到 $[0, N-1]$ （为保证取余后的数是整数，可以先对 N 取余，然后加 N 再对 N 取余）。

处理哈希冲突选择线性探测法时，经验上我们一般把 N 取到数据范围的 $2 \sim 3$ 倍，且应是远离 $2$ 的幂的素数，这样可以尽可能的避免哈希冲突（具体原因可以自行了解），选取素数时可以参考的表格：素数选取表。线性探测法的具体步骤：

• 添加：
  • 首先通过哈希函数求出哈希值：int y = hash(x)。
  • 然后在哈希表中找到对应的位置(ht[y])，如果当前位置已经有其他的数了（!= x）就循环向后，直到找到第一个空位就放入 x 退出循环。
• 查询：
  • 依旧首先求出哈希值：int y = hash(x)。
  • 然后在哈希表中找到对应的位置(ht[y])，如果当前位置有数并且等于 x，那么就找到了 x，直接返回 true，否则循环向后，直到找到了空位就说明 x 不存在，退出循环，或者找到了 x，同上。

线性探测法的核心是一个 find() 函数：

int find(int x) {
    int y = (x % N + N) % N;
    while (h[y] != INF && h[y] != x) {
        if (++y == N) y = 0;
    }
    return y;
}

如果 x 存在于哈希表中，就返回 x 所在的位置，否则返回 x 应该在哈希表中存储的位置。

注意：

• 如果线性探测找到了哈希表末尾还没找到空位，应该从表头继续找。
• 哈希表中所有元素应该初始化为一个数据范围以外的数，一般取 0x3f3f3f3f，它比 $10^9$ 大并与其在同一数量级，取这个数还有一个好处是 C++ 中可以 memset(ht, 0x3f, sizeof(0x3f)); 这样很方便的初始化。

模版：哈希 - 一般哈希 - 开放寻址法

代码

#include <iostream>
#include <string.h>

using namespace std;

const int N = 391627, INF = 0x3f3f3f3f;
int h[N];
int n;

int find(int x) {
    int y = (x % N + N) % N;
    while (h[y] != INF && h[y] != x) {
        if (++y == N) y = 0;
    }
    return y;
}

int main() {
    memset(h, 0x3f, sizeof(h));
    scanf("%d\n", &n);
    while (n--) {
        char ope;
        int x;
        scanf("%c %d\n", &ope, &x);
        int k = find(x);
        if (ope == 'I') h[k] = x;
        else puts(h[k] == x ? "Yes" : "No");
    }
    
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    static final int N = 391627, INF = 0x3f3f3f3f;
    static int[] hash = new int[N];
    
    static int find(int x) {
        int y = (x % N + N) % N;
        while (hash[y] != INF && hash[y] != x) {
            ++y;
            if (y == N) y = 0;
        }
        return y;
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        for (int i = 0; i < N; ++i) hash[i] = INF;
        while (n-- > 0) {
            in.nextToken();
            char ope = in.sval.charAt(0);
            in.nextToken();
            int x = (int) in.nval;
            if (ope == 'I') hash[find(x)] = x;
            else System.out.println(hash[find(x)] == INF ? "No" : "Yes");
        }
    }
}

方法二：拉链法

思路

拉链法的原理是在哈希表中哈希冲突的地方拉一条链表用来存哈希值相同的数。

具体步骤：

• 插入：
  • 首先通过哈希函数求出哈希值：int y = hash(x)。
  • 然后类似于单链表向头节点前插入的方法，向 ht[y] 前面插入 x。
• 查找：
  • 依旧首先求出哈希值：int y = hash(x)。
  • 然后遍历该值指向的链表，在其中查找 x 是否存在。

代码

#include <iostream>
#include <string.h>

using namespace std;

const int N = 195677;
int ht[N], vals[N], nexts[N], idx;
int n;

void insert(int x) {
    int y = (x % N + N) % N;
    // 头插
    vals[idx] = x;
    nexts[idx] = ht[y];
    ht[y] = idx++;
}

bool find(int x) {
    int y = (x % N + N) % N;
    for (int i = ht[y]; i != -1; i = nexts[i]) {
        if (vals[i] == x) return true;
    }
    return false;
}

int main() {
    memset(ht, -1, sizeof(ht));
    scanf("%d\n", &n);
    while (n--) {
        char ope;
        int x;
        scanf("%c %d\n", &ope, &x);
        if (ope == 'I') insert(x);
        else puts(find(x) ? "Yes" : "No");
    }
    
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    static final int N = 195677;
    static int[] hash = new int[N], vals = new int[N], nexts = new int[N];
    static int idx;
    
    static void insert(int x) {
        int y = (x % N + N) % N;
        vals[idx] = x;
        nexts[idx] = hash[y];
        hash[y] = idx++;
    }
    
    static boolean find(int x) {
        int y = (x % N + N) % N;
        for (int i = hash[y]; i != -1; i = nexts[i]) {
            if (vals[i] == x) return true;
        }
        return false;
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        for (int i = 0; i < N; ++i) hash[i] = -1;
        while (n-- > 0) {
            in.nextToken();
            char ope = in.sval.charAt(0);
            in.nextToken();
            int x = (int) in.nval;
            if (ope == 'I') insert(x);
            else System.out.println(find(x) ? "Yes" : "No");
        }
    }
}