hash的定义

  • Hash,一般翻译做散列、杂凑,或音译为哈希,是把任意长度的输入(又叫做预映射pre-image)通过散列算法变换成固定长度的输出,该输出就是散列值。 这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来确定唯一的输入值(简称hash冲突)。

  • Hash 通俗的来说 就是映射,y = f(x), 将 x 的值 通过映射函数映射到 y。通过hash,缩小空间。

  • image.png

Hash冲突

  • 就是 不同的输入通过hash函数,输出了相同的结果
  • 解决hash冲突的方法
    • 拉链法
      • 就是当 不同的输入得出相同的结果的时候,将这两个值通过链表连接起来,形成一条链。
      • image.png
    • 开放寻址法
      • 开放寻址法,就是当发现计算出来的hash值已经被使用,就寻找计算出的hash值右边的可用的空间直到找到。
      • image.png

题目了解 hash

  1. 模拟散列表

    • image.png

    • 题目链接:模拟散列表

    • 题目中 x 的数据范围很大,而且需要我很快的找到 x 是否存在,显然不可能一个个遍历。我们可以考虑通过hash,将x压缩到 一定的数据范围中。在通过hash查找该值是否存在

    • 拉链法解决冲突

      • 	#include <iostream>
        	#include <cstring>
        	using namespace std;
        
        	const int N = 1e5 + 3; // hash 值一般都是质数
        
        	int head[N], e[N], ne[N], idx;
        
        	void insert(int x) {
        	    int k = (x % N + N) % N; // hash函数
        
        	    // 拉链法解决冲突
        	    e[idx] = x;
        	    ne[idx] = head[k];
        	    head[k] = idx ++;
        	}
        
        	bool query(int x) {
        	    int k = (x % N + N) % N;
        
        	    for (int i = head[k]; i != -1; i = ne[i]) { // 遍历链表
        	        if (e[i] == x) return true;
        	    }
        	    return false;
        	}
        
        
        	int main() {
        	    int n;
        	    cin >> n;
        	    memset(head, -1, sizeof head); // 初始化为空
        	    while (n --) {
        	        string op;
        	        int x;
        	        cin >> op >> x;
        	        if (op == "I")
        	            insert(x);
        	        else
        	            cout << (query(x) ? "Yes\n":"No\n");
        
        	    }
        	    return 0;
        	}
        
    • 开放寻址法解决冲突

      • 	#include <iostream>
        	#include <cstring>
        	using namespace std;
        
        	const int N = 2e5 + 3; // hash 值一般都是质数, 注意需要开两倍
        
        	int head[N];
        
        	// 开放寻址法的重点,find函数,如果x存在返回 其hash值(位置),如果不存在返回 其 应该使用的hash值(位置)
        	int find(int x) {
        	    int k = (x % N + N) % N;
        
        	    while(head[k] != 0x3f3f3f3f && head[k] != x) {
        	        k ++;
        	        if (k == N) k = 0; // 循环
        	    }
        
        	    return k;
        	}
        
        
        	int main() {
        	    int n;
        	    cin >> n;
        	    memset(head, 0x3f, sizeof head); // 初始化为空
        	    while (n --) {
        	        string op;
        	        int x;
        	        cin >> op >> x;
        	        int k = find(x);
        	        if (op == "I"){
        	            head[k] = x;
        	        }
        	        else {
        	            cout << (head[k] == x ? "Yes\n":"No\n");
        	        }
        
        
        	    }
        	    return 0;
        	}
        
  2. 字符串 hash

    • 通过字符串hash,可以解决kmp无法解决的问题。

    • 字符串hash,本质是计算该字符串的前缀的hash值,然后以base进制计算其对应的hash值。通过比对字符串的hash值,可以判断该字符串是否相等。

    • image.png

    • 题目链接:字符串哈希

    • 题目分析:

      • 我们得快速判断 str[l1~r1] == str[l2~r2] 是否相等,所以需要把字符串进行hash,比对hash值
      • 				#include <iostream>
        	#include <cstring>
        	using namespace std;
        
        	const int N = 1e5 + 5, base = 131; // base 必须选择 131 或 1331 能尽可能的避免hash冲突
        	char str[N];
        	typedef unsigned long long ULL;
        
        	ULL h[N], p[N];
        
        
        
        	ULL find(int l, int r) { // 返回 str[l ~ r] 的hash值
        	    return h[r] - h[l - 1] * p[r - l + 1];
        	}
        
        	int main() {
        
        	    int n, m;
        	    cin >> n >> m;
        
        	    cin >> (str + 1);
        	    p[0] = 1;
        	    for (int i = 1; i <= n; ++ i) {
        	        p[i] = p[i - 1] * base; // 预处理 base 各个进制的值
        	        h[i] = h[i - 1] * base + str[i]; // 计算出字符串各个前缀的hash值
        	    }
        
        	    while (m --) {
        	        int l1,r1,l2,r2;
        	        cin >> l1 >> r1 >> l2 >> r2;
        
        	        ULL s1 = find(l1, r1);   
        	        ULL s2 = find(l2, r2);
        
        	        cout << (s1 == s2 ? "Yes\n":"No\n");
        	    }
        
        	    return  0;
        
        	}