哈希表

哈希表

哈希表（Hash Table）是一种基于 键值对 存储的数据结构，通过一个哈希函数（Hash Function）将键映射到表中的一个位置，从而实现高效的数据存储与查找。哈希表的核心思想是利用数组的下标快速定位数据。

开放寻址法

#include <bits/stdc++.h>
using namespace std;

//找到一个大约是数组大小2~3倍的一个大质数
const int N = 200003, null = 0x3f3f3f3f;

int h[N];

int find(int x)
{
	//在c++中对负数取模会得到负数，所以在这里进行如下操作
	int t = (x % N + N) % N;
	//如果该位置为空或者找到了对应元素，那么退出循环
	while(h[t] != null && h[t] != x) 
	{
		t++;
		if (t == N) t = 0;
	}
	// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
	return t;
}

int main()
{
	memset(h, 0x3f, sizeof h);
	int n;
	cin >> n;
	while(n--){
		string op;
		int x;
		cin >> op >> x;
		if (op == "I") {
			//因为find函数返回下标，所以这个的意思就是把对应的合适位置赋值
			//实现插入功能
			h[find(x)] = x;
		} else {
			if (h[find(x)] == null) cout << "No" << endl;
			else cout << "Yes" << endl;
		}
	}
	return 0;
}

拉链法

#include <bits/stdc++.h>
using namespace std;

const int N = 100003;

int h[N], e[N], ne[N], idx;

void insert(int x)
{
	int k = (x % N + N) % N;
	//e[idx]: 存储具体的值，e[i] 表示索引 i 处存储的元素
	//ne[idx]: 存储下一个节点的索引，ne[i] 表示索引 i 节点的下一个节点
	//代码中的每个 h[i] 都可以看作是一个链表的头节点
	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;
}

int main()
{
	//将槽先清空 空指针一般用 -1 来表示
	memset(h, -1, sizeof h);
	int n;
	cin >> n;
	while(n--){
		string op;
		int x;
		cin >> op >> x;
		if (op == "I") {
			insert(x);
		} else {
			if (find(x)) {
				cout << "Yes" << endl;
			} else {
				cout << "No" << endl;
			}
		}
	}
	
	return 0;
}

字符串哈希

#include <iostream>
using namespace std;

typedef unsigned long long ULL;

const int N = 100010, P = 131;

int n, m;
string str;
ULL h[N], p[N];

ULL get(int l, int r)
{
	return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
    p[0] = 1;
	cin >> n >> m >> str;
	str = " " + str;
	for (int i = 1; i <= n; i++) {
		//初始化p数组
		p[i] = p[i - 1] * P;
		//前缀和求整个字符串的哈希值
        //这里可以看作提取整数的每一位并构造出逆序数的方法
		h[i] = h[i - 1] * P + str[i]; 
	}
	while(m--)
	{
		int l1, r1, l2, r2;
		cin >> l1 >> r1 >> l2 >> r2;
		if (get(l1, r1) == get(l2, r2)) {
			cout << "Yes" << endl;                                         
		} else {
			cout << "No" << endl;
		}
	} 

	return 0;
}

经典例题

匹配统计

https://www.luogu.com.cn/problem/P10479

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef unsigned long long ull;

const int N = 200010, P = 131;

int n, m, q;
string str1, str2;
map<int, int> cnt;
ull h1[N], h2[N], p[N];

ull get(ull h[], int l, int r) {
	return h[r] - h[l - 1] * p[r - l + 1];
}

// 判断len长度时匹不匹配，比较 str1 后缀和 str2 前缀的哈希值
bool check(int i, int len) {
	if (i + len - 1 > n) return false;
	return get(h1, i, i + len - 1) == get(h2, 1, len); 
}

signed main() {
	cin >> n >> m >> q;
	cin >> str1 >> str2;
	str1 = " " + str1;
	str2 = " " + str2;
	p[0] = 1;
	
	int len = max(n, m);
	for (int i = 1; i <= len; i++) {
		p[i] = p[i - 1] * P;
	}
	for (int i = 1; i <= n; i++) {
		h1[i] = h1[i - 1] * P + str1[i];
	}
	for (int i = 1; i <= m; i++) {
		h2[i] = h2[i - 1] * P + str2[i];
	}
	
	for (int i = 1; i <= n; i++) {
		int l = 0;
		int r = m;
		int ans = 0;
		while (l <= r) {
			int mid = (l + r) / 2;
			// 如果匹配，尝试更大的值
			if (check(i, mid)) {
				ans = mid;
				l = mid + 1;
			// 如果不匹配，尝试更小的值
			} else {
				r = mid - 1;
			}
		}
		cnt[ans]++;
	}
	
	while (q--) {
		int x;
		cin >> x;
		cout << cnt[x] << "\n";
	}
}