基础数据结构第十期 哈希表（数组+STL）

前言：

哈希表是一种非常重要的数据结构，希望大家都能够熟练掌握！！！

一、哈希表的基本内容

哈希表（Hash Table），也被称为哈希映射（Hash Map）或字典（Dictionary），是一种常见的数据结构，用于高效地存储和检索数据。它利用哈希函数（Hash Function）将关键码（Key）映射到存储位置，从而实现快速的查找、插入和删除操作。哈希表的基本思想是将关键码通过哈希函数转换成一个固定长度的哈希值（Hash Value），然后将该哈希值作为索引来访问数组（或者称为哈希桶）中的特定位置。这样，可以通过哈希函数直接计算出元素的存储位置，从而快速定位到所需的数据。

在C++中底层使用了哈希表的有unordered_map、unordered_set这两个STL的容器。

unordered_map:

unordered_map底层存储的是<key,value>键值对，可以通过key快速的索引到value，在unordered_map内部因为是数据是通过映射存入哈希桶内的，所以对unordered_map进行遍历得到的是一个无序的序列。

unordered_set:

unordered_set和set的使用是一样的，但是底层的存储方式是不同的，set使用的是红黑树，unordered_set底层使用的是哈希桶，进行查找的时间复杂度是常数次，但是底层的数据是无序的。

二、使用步骤

1.模拟散列表：

AC代码：

数组：

//哈希表
//开放寻址法
#include <iostream>
#include <cstring>
using namespace std;
const int N = 200003, null = 0x3f3f3f3f;
//0x3f3f3f3f是个大于1e9的数,一定不在x的范围内
int h[N];

//核心操作find
//如果x在哈希表中存在,那么返回x在哈希表中的位置,
//如果x在哈希表中不存在,那么返回x应该在哈希表中存储的位置
int find(int x) {
	int k = (x % N + N) % N;

//当前位置不等于空,也就是坑位上有人,并且这个坑位上的人不等于x,那就应该去看下一个坑位
	while (h[k] != null && h[k] != x) {
		k++;
		if (k == N)//说明已经看完了最后一个坑位
			k = 0;//就循环看第一个坑位
	}
	return k;
}

int main() {
	int n;
	scanf("%d", &n);
	memset(h, 0x3f, sizeof h);//数组初始化,把h数组初始化成0x3f
	while (n--) {
		char op[2];
		int x;
		scanf("%s%d", op, &x);
		int k = find(x);
		if (*op == 'I')
			h[k] = x;
		else {
			if (h[k] != null)
				puts("Yes");
			else
				puts("No");
		}
	}
	return 0;
}

STL：

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
vector<int>v;
int n,x;
char c;
int main()
{
	cin>>n;
	while(n--){
		cin>>c>>x;
		if(c=='I'){
			v.push_back(x);
		}
		if(c=='Q'){
		 if(count(v.begin(),v.end(),x))cout<<"Yes"<<endl;
			else cout<<"No"<<endl;
		}
	}
	return 0;
}

2.字符串哈希：

AC代码：

//快速判断两个字符串是否相等,可以用字符串前缀哈希这个做法
#include <iostream>
using namespace std;
typedef unsigned long long ULL;
const int  N = 100010, P = 131;
//p一般取131或13331,代表P进制
int  n, m;
char str[N];
ULL h[N], p[N];
//h数组表示某一个值前缀哈希值
//p数组用来表示乘了p的多少次方

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

int main() {
	scanf("%d%d%s", &n, &m, str + 1);
	p[0] = 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;
		scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
		if (get(l1, r1) == get(l2, r2))
			puts("Yes");
		else
			puts("No");
	}

	return 0;
}

总结

哈希表真的十分的重要，希望我们都能够熟练的掌握，感谢大家的观看，谢谢大家！！！