11-散列表

算法思想

散列表

• 散列表是可以根据键直接访问存储位置的数据结构

哈希函数

• 除留余数法： h(k) = k mod m
• m 的选取原则：m 选取一个素数，且远离 2 的幂，以避免模式化冲突

算法模板

拉链法

import java.util.*;
public class Main {
    // 临近100000的最大素数
    static int N = 100003;
    // e[i]存储第 i 个节点的数值
    static int[] e = new int[N],
    // ne[i]存储第 i 个节点的下一个节点的索引
        ne = new int[N],
    // h[i] 存储第 i 个拉链的头结点的下一个节点的索引
    // 头结点是个虚拟节点（并不存在），空节点的索引为 -1
        h = new int[N];
    static int idx;


    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Arrays.fill(h, -1);
        
        while(n -- > 0)
        {
            String s = sc.next();
            int x = sc.nextInt();
            if(s.equals("I")) insert(x);
            else
            {
                String res = (find(x)) ? "Yes" : "No";
                System.out.println(res);
            }
        }
    }
    
    public static void insert(int x)
    {
        // k = x % N
        // 在数学运算中，k 一定为正数
        // 在Java运算中，k 可能为负数
        // 为确保 k 为正数，执行 + N % N 操作
        int k = (x % N + N) % N;
        e[idx] = x;
        ne[idx] = h[k];
        h[k] = idx ++;
    }
    
    public static boolean 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;
    }
}

开放寻址法

import java.util.*;

public class Main {
    // 极端情况下，所有数值都映射到数组 h 的最后一个位置
    // N > 2 * maxN，确保不会出问题
    static int N = 200003;
    static int[] h = new int[N];
    // 节点值为 NULL 表示节点为空节点
    // NULL > 1e9 
    static int NULL = 0x3f3f3f3f;

    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        Arrays.fill(h, NULL);
        
        while(n -- > 0)
        {
            String op = in.next();
            int x = in.nextInt();
            
            if(op.equals("I")) h[find(x)] = x;
            else
            {
                var res = (h[find(x)] != NULL) ? "Yes" : "No";
                System.out.println(res);
            }
        }
    }
    // 若找不到，则返回可以存放 x 的正确位置    
    static 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;
    }
}