知识点补充

哈希表是可以插入无序的，二离散化插入的必须是饱序的也就是有序的
哈希表两种写法：求存储下标：k = （x % N）N必须是质数
—拉链法
------就是找到下标之后如果有冲突，则以k为头，然后是单链表的方式存储
—开放地址法
------就是遇到冲突之后，下标k+1,直到找到空的

题目描述

插入一些值，然后查询这些值是否存在，插入的这些值的范围很大
1≤N≤1e5
−1e9≤x≤1e9

输入样例

5
I 1
I 2
I 3
Q 2
Q 5

输出样例

Yes
No

算法1

(拉链法) $O(1)$

因为值域很大，如果开个数组太大了，并且查找不方便，所以用到了哈希表，直接通过k=x%m来找到下标存储和查找，遇到冲突直接开放地址和拉链法就可以解决了，时间复杂度是O(1).真棒！

参考文献：y总

Java 代码

import java.util.Scanner;

/**
 * 哈希表
 * 解决：大的值域映射到小的范围 eg：1e-9 - 1e-5 可以解决查找问题
 *
 * 存储结构
 *      开放地址发
 *      拉链法
 * 字符串hash方式
 */
public class Main {
    // 拉链法
    static int N = 100003;// 大于100000的第一个最大质数 mod 之后的数
    static int[] h = new int[N];// hash表
    // 单链表
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int idx = 1;

    // 插入
    static void insert(int x){
        int k = (x % N + N) % N;// 求hash存储的下标 为什么+N %N 因为想把负数变成正数
        // 单链表的插入
        e[idx] = x;
        ne[idx] = h[k];
        h[k] = idx++;
    }

    // 查找
    static boolean find(int x){
        int k = (x % N + N) % N;
        for (int i = h[k]; i != 0; i = ne[i]){
            if (x == e[i]) return true;
        }
        return false;
    }


    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = Integer.parseInt(scan.nextLine());

        while (n-- > 0){
            String[] s = scan.nextLine().split(" ");
            int x = Integer.parseInt(s[1]);
            if ("I".equals(s[0])){
                insert(x);
            }else if ("Q".equals(s[0])){
                System.out.println(find(x) == true?"Yes":"No");
            }
        }
    }
}

算法2

(开放地址法) $O(1)$

blablabla

时间复杂度：$O(1)$

参考文献：y总

Java 代码

import java.util.Scanner;

/**
 * 哈希表
 * 解决：大的值域映射到小的范围 eg：1e-9 - 1e-5 可以解决查找问题
 *
 * 存储结构
 *      开放地址发
 *      拉链法
 * 字符串hash方式
 */
public class Main {
    // 开放地址法---蹲坑法
    // 经验值 N的范围是指定范围的2-3倍
    static int N = 200003;// 大于200000的第一个最大质数 mod 之后的数
    static int[] h = new int[N];
    static int kong = 0x3f3f3f3f;// h 的初始值

    // 返回查找的位置和插入的位置
    static int find(int x){
        int k = (x % N + N) % N;// 求x对应的hash下标
        // k等于kong 相当于下标k没有插入值 h[k] == x 找到了x对应的下标
        while (h[k] != kong && h[k] != x){
            k++;
            if (k == N) k = 0;// 如果查到结尾了 从头开始
        }
        return k;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = Integer.parseInt(scan.nextLine());
        for (int i = 0; i < N; i++) h[i] = kong;

        while (n-- > 0){
            String[] s = scan.nextLine().split(" ");
            int x = Integer.parseInt(s[1]);
            int k = find(x);
            if ("I".equals(s[0])){
                h[k] = x;
            }else if ("Q".equals(s[0])){
                if (h[k] != kong){
                    System.out.println("Yes");
                }else {
                    System.out.println("No");
                }
            }
        }
    }
}