哈希表

哈希表：就是把一堆数据映射到从零到n

常见情景：0-10^9 映射到0 ~ 10^5

哈希表是期望算法

哈希函数：一般是取模

冲突：映射为同一个数了，解决冲突的方法，开放寻址发，拉链法ka

离散化是极其特殊的哈希方式，离散化是要保证顺序

在算法题中，一般实现，插入和查询两个操作

模板

一般哈希

(1) 拉链法
    int h[N], e[N], ne[N], idx;

    // 向哈希表中插入一个数
    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;
    }

(2) 开放寻址法
    int h[N];

    // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
    int find(int x)
    {
        int t = (x % N + N) % N;
        while (h[t] != null && h[t] != x)
        {
            t ++ ;
            if (t == N) t = 0;
        }
        return t;
    }

字符串哈希

核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

题目

AcWing

840 模拟散列表
841 字符串哈希

Ac840 模拟散列表

描述

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

“I x”，插入一个数x；

“Q x”，询问数x是否在集合中出现过；

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

解答

import java.io.*;
public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(reader.readLine());
		MyHashMap map = new MyHashMap();
		while(n-->0){
			String[] s = reader.readLine().split(" ");
            int x = Integer.parseInt(s[1]);
            if (s[0].equals("I")) map.insert(x);
            else {
                if (map.find(x)) System.out.println("Yes");
                else System.out.println("No");
            }
		}
		
	}
    
    static class MyHashMap{
		int N = 100003;
		int[] h = new int[N];
		int[] e = new int[N];
		int[] ne = new int[N];
		int idx = 0;
		
		private int hash(int x){
			return (x%N+N)%N;  //保证一定是正数
		}
		
		
		public void insert(int x){
			e[idx]=x;
			int hash = hash(x);
			ne[idx] = h[hash];   //h[k]是链表的最后节点
			h[hash] = idx++;
			
		}
        
        //
        public void insert1(int x){
        	e[idx] = x;
            int hash = hash(x);
            ne[idx] = h[hash];
            h[hash] = idx++;
   		}
		
		public boolean find(int x){
			int hash = hash(x);
			for(int i = h[hash];i>=0;i=ne[i]){
				if(e[i] == x) return true;
				else if(i==0) return false;
			}
			return false;
		}
		
	}

}

Ac841 字符串哈希

描述

给定一个长度为n的字符串，再给定m个询问，每个询问包含四个整数l1,r1,l2,r2l1,r1,l2,r2，请你判断[l1,r1l1,r1]和[l2,r2l2,r2]这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

字符串哈希：假定不会冲突

这里的h表示的啥?

假设s = abc

h[0] = 0

h[1] = a的hash值

h[2] = ab 的hash值

解答

import java.io.*;

class Main{
    static int N = 100010;
    static long[] p = new long[N];
    static long[] h = new long[N];
    static int b=131;
    static long mod = Long.MAX_VALUE;
    
    //关键
    static void init(String s){
        p[0]=1;
        
        char[] arr = s.toCharArray();
        for(int i=1;i<arr.length;i++){
            h[i] = (h[i-1]*b+arr[i-1])%mod;
            p[i] = p[i-1] * b;
        }
    }
    
    static long query(int l, int r){
        return h[r] - h[l-1] * p[r-l+1];
    }
    
        public static void main(String[] args) throws IOException{
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        String[] cur = in.readLine().split(" ");
        int n=Integer.parseInt(cur[0]);
        int m=Integer.parseInt(cur[1]);

        String s = in.readLine();
		
        init(s);
        
        while(m-->0){
            String[] arr=in.readLine().split(" ");
            int l1 = Integer.parseInt(arr[0]);
            int r1 = Integer.parseInt(arr[1]);
            int l2 = Integer.parseInt(arr[2]);
            int r2 = Integer.parseInt(arr[3]);

            if(query(l1, r1)==query(l2, r2)){
                System.out.println("Yes");
            }
            else{
                System.out.println("No");
            }
        }
        }	
}