哈希（Hash）

哈希表（期望算法）

在算法题中，涉及哈希表的题目一般只要求添加和访问元素

哈希中模的取值尽可能是质数且里2的整数次幂尽可能远

哈希表的存储结构分为：

1. 开放寻址法
2. 拉链法

开放寻址法

只开一个一维数组，但大小一般是题目要求范围的2-3倍

#include<iostream>
#include <cmath>
#include <cstring>

const int N = 200003,empty = 0x3f3f3f3f;
int h[N], e[N], next[N], idx = 0;
int getMode(int a)
{
	for(int i = a;;i++)
	{
		bool op = true;
		for(int j = 2;j<std::sqrt(a);j++)
		{
			if(!(i%j))
			{
				op = false;
				break;
			}
		}
		if (op) {
			return i;
		}
	}
}

int find(int x)
{
	int k = (x % N + N) % N;
	while(h[k]!=empty&&h[k]!=x)
	{
		k++;
		if (k == N) k = 0;
	}
	return k;
}
int main()
{
	//std::cout << getMode(200000);
	memset(h, 0x3f, sizeof h);
	int n,x;
	std::cin >> n;
	char op[2];
	while(n--)
	{
		std::cin >> op >> x;
		int k = find(x);
		if(*op == 'I')
		{
			h[k] = x;
		}else
		{
			if (h[k]!=empty)
				std::cout << "Yes\n";
			else
				std::cout << "No\n";
		}
	}
}

拉链法

使用一个数组去记录所有的哈希值

处理冲突的方式：

使用一个链去记录一个哈希值对应的所有数

#include<iostream>
#include <cmath>
#include <cstring>

const int N = 100003;
int h[N], e[N], next[N], idx = 0;
int getMode(int a)
{
	for(int i = a;;i++)
	{
		bool op = true;
		for(int j = 2;j<std::sqrt(a);j++)
		{
			if(!(i%j))
			{
				op = false;
				break;
			}
		}
		if (op) {
			return i;
		}
	}
}
void insert(int x)
{
	int k = (x % N+N)%N;    //这就是哈希公式
	e[idx] = x;
	next[idx] = h[k];
	h[k] = idx++;
}
bool find(int x)
{
	int k = (x % N + N) % N;
	for (int i = h[k]; i != -1; i = next[i])
		if (e[i] == x)
			return true;
	return false;
}
int main()
{
	std::memset(h, -1, sizeof h);
	int n,x;
	std::cin >> n;
	char op[2];
	while(n--)
	{
		std::cin >> op >> x;
		if(*op == 'I')
		{
			insert(x);
		}else
		{
			if (find(x))
				std::cout << "Yes\n";
			else
				std::cout << "No\n";
		}
	}
}

字符串哈希方式

举例：

对于字符串：”ABCABCDEYXCACWING”

H[0] = 0   
h[1] = "A"    //指的哈希值    
h[2] = "AB"    
h[3] = "ABC"    
h[4] = "ABCA"    
....

如何定义前缀的哈希值？

将字符串看成p进制的数，每一位的字母表示p进制的每一位数字，这样的话，将p[]转换为10进制的数，比如：

h[4] = 1 * p^3 + 2 * p^2 + 3 * p^1 + 1 * p^0

最后取哈希值时取一个较小的数Q，h[4] = （1 * p^3 + 2 * p^2 + 3 * p^1 + 1 * p^0）% Q

如此，我们就可以将字符串映射到0 ~ Q-1的数中

---

注意：一般情况下，我们不能将某一个数字映射成 0 因为例如我们将 A 映射到0，那么 AA, AAA,都将被映射到 0 中…..。 ***

那我们如何得知 l ~ r 的哈希值呢？

首先，进行预处理：h[i] = h[i - 1] * p + str[i];

那么hash[l~r] = h[r] - h[l] * p^(r-l+1)

#include <iostream>
const int N = 100010,P = 131;

using ULL = unsigned long long;

int n, m;
char str[N];
ULL h[N], p[N];
ULL get(int l,int r)
{
	return h[r] - h[l - 1] * p[r - l + 1];
}
int main()
{
	scanf("%d %d %s", &n, &m, str + 1);
	p[0] = 1;
	for (int i = 1; i <= n; ++i)
	{
		p[i] = p[i - 1] * P;
		h[i] = h[i - 1] * P + str[i];
	}
	while (m--)
	{
		int l1, r1, l2, r2;
		std::cin >> l1 >> r1 >> l2 >> r2;
		if (get(l1, r1) == get(l2, r2))
			std::cout << "Yes" << std::endl;
		else
			std::cout << "No" << std::endl;
	}
}

• 哈希
• hash
• 哈希函数
• 哈希表
• 字符串哈希