当前位置： 首页 > article >正文

蓝桥杯备考：哈希表和unorderd_set

article 2025/1/29 10:02:35

哈希表的概念，哈希表是什么

哈希表，又叫散列表，是根据关键字进行访问的数据结构

哈希表建立了一种关键字和存储地址之间的映射关系，使每个关键字与结构中的唯一存储

位置相对应。在理想情况下，散列表中进行查找的时间复杂度是O（1），与元素数量无关

接下来我们用一个案例来说明：统计一下字符串“abcabcc"中，每一个字符出现的次数，字符串只包含小写字母

代码

#include <iostream>
using namespace std;

int a[26];

int main()
{
	string s;
	cin >> s; 
	for(auto e : s)
	{
		a[e-'a']++;
	}
	return 0;
}

这时候，我们的hash(key)也就是key-'a'

那么哈希冲突是啥呢？

哈希函数可能把两个或者两个以上的关键字映射到同一个存储位置上，这时候就是我们的哈希冲突，也叫散列冲突，起冲突的不同关键字称之为同义词

 第一种方法就是 创建一个1e9+10大小的数组，用hash(key)=key来存储哈希值

但是这种方法是行不通的，我们创建这么大的数组空间复杂度太高了

所以我们要选第二种方法，我们可以对每个数模上7来代表存储位置，这样的话我们只需要创建一个大小为7的数组就足够了 我们的哈希函数也就是hash(key) = key%7

1%7 = 1,   3%7 = 3    17%7 = 3   100000000%7 = 6   49%7 = 0 49%7 = 0

可以看到有两个关键字的存储位置都是3，这两个关键字就是同义字

哈希冲突是不可避免的，我们要做的不是消除哈希冲突，我们要做的是处理哈希冲突和创造好的哈希函数，

常见的哈希函数，以及怎么处理哈希冲突

哈希函数1：直接定址法

直接取关键字的某个线性函数值作为散列地址

比如hash(key) = key,hash(key) = a*key+b

我们之前的案例

统计一下字符串“abcabcc"中，每一个字符出现的次数，字符串只包含小写字母   

就是一种直接定址法

hash(key)=key-'a' 也就是1*key-'a' 是线性的

我们的直接定址法适合元素分布比较连续而不是很跳跃的，不然会很浪费我们的空间

哈希函数2：除留余数法

我们哈希冲突那里的案例，用的就是除留余数法，除留余数，顾名思义就是用key%M作为存储地址，我们的M尽量取成一个素数（减少哈希冲突），最好接近哈希表的大小

处理哈希冲突法1：线性探测法

这种方法就是，我们从发生哈希冲突的位置上依次向后探测，找到一个空位置把值放进去

如果走到表尾了，到下一个就回绕到表头

当我们用除留余数法适，我们的除数一般是选择原来数组长度的两倍附近的一个素数，因为如果我们只找一倍数组附近的素数的话，就显得很紧凑，一不小心的话我们的时间复杂度就会变成O（N），我们弄的大一点的话，我们查一个数的时候需要跳跃的格子相应的就会少

本题数组长度是8，2*8=16，16附近找一个素数，我们就找11吧为了更好看

hash(key)=key%11

INF指的就是我们不可能存到的值，可以当成无穷大

那么我们用线性探测法来进行一下我们的存储

19%11 = 8，我们放在8的位置    30%11 = 8 这时候就出现了哈希冲突，30就要从哈希冲突的位置向后探测，找空位置放进去

下一个元素是5，5%11 还是5，我们放在5的位置

36%11是3，我们放在3这个位置

13%11是2，我们放在2这个位置

20%11 是9，这时候又会发生哈希冲突，我们还是向后探测

21%11是10，再次发生哈希冲突，由于走到表尾我们会回绕会表头，所以

最后一个元素是12，12应该放在12%11 也就是1的位置

处理哈希冲突2 链地址法

我们还是取模数是11，这时候我们的数组每个位置存的就不是元素的值了而是一个一个的指针

我们把发生哈希冲突的值串在一起构成小的链表，这样做的弊端是如果我们发生哈希冲突的元素非常多，那么串在一起查找的时间复杂度就是O（N）了

19%11是8，我们挂在8下面 30%11是8，我们也挂在8下面，

接下来，我们继续算，5%11=5 挂在下标5下面，36%11就是3，挂在下标3下面，13%11就是2，挂在2下面

20%11就是9挂在9下面，21%11就是10，挂在10下面，12%11就是1，挂在1下面，24%11就是2，挂在2下面，96%11就是8放在8下面

模拟实现哈希表

方法1：线性探测法

我们先给出一个测试用例

12
1 1
1 2
1 3
1 4
1 5
2 2
1 6
2 5
1 7
2 8
2 4
2 10

#include <iostream>
#include <cstring>
using namespace std;
const int N = 23,INF = 0x3f3f3f3f;
int h[N];

void init()
{
	memset(h, 0x3f, sizeof(h));
}
int f(int x)
{
	int id = (x % N + N) % N;
	while (h[id] != INF && h[id] != x)
	{
		id++;
		if (id == N) id = 0;
	}
	return id;
}
void insert(int x)
{
	int id = f(x);
	h[id] = x;
}
bool find(int x)
{
	int id = f(x);
	return h[id] == x;
}

int main()
{
	init();
	int n; cin >> n;
	while (n--)
	{
		int op; cin >> op;
		int x; cin >> x;
		if (op == 1)
		{
			insert(x);
		}
		else if (op == 2)
		{
			if (find(x))cout << "yes" <<endl;
			else cout << "no" << endl;
		}
	}



	return 0;
}

方法2，链地址法

链地址法和我们的链式前向星是差不多的，我们就简单用代码来实现一下了。

#include <iostream>
using namespace std;
const int N = 23;

int h[N];//哈希表

int ne[N], id,e[N];

int f(int x)
{
	return (x % N + N) % N;

}
void insert(int x)
{
	int idx = f(x);
	id++;
	e[id] = x;
	ne[id] = h[idx];
	h[idx] = id;
	
}
bool find(int x)
{
	int idx = f(x);
	for (int i = h[idx]; i; i = ne[i])
	{
		if (e[i] == x)
			return true;
	}
	return false;
}
int main()
{
	int n; cin >> n;
	while (n--)
	{
		int op; cin >> op; int x; cin >> x;
		if (op == 1)
		{
			insert(x);
		}
		else
		{
			if (find(x)) cout << "yes" << endl;
			else cout << "no" << endl;
		}
	}






	return 0;
}

unordered_set和unordered_map

这个和我们set的用法是一样一样的，只不过我们set是有序的，unordered_set是无序的

只不过我们没有了lower_bound 和 upper_bound，然后哈希表查找和插入的时间复杂度都是O（1）而红黑树是O（logN），我们的有序set是红黑树实现的，我们的无序set是哈希表实现的

无序set测试

#include <iostream>
#include <unordered_set>


using namespace std;

int a[] = { 10,60,20,70,80,30,90,40,100,50 };
int main()
{

	unordered_set <int> mp;
	for (auto e : a)
	{
		mp.insert(e);
	}
	for (auto e : mp)
	{
		cout << e << " ";
	}
	cout << endl;

	if (mp.count(10)) cout << "10:yes" << endl;
	else cout << "10:no" << endl;
	if (mp.count(20)) cout << "20:yes" << endl;
	else cout << "20:no" << endl;
	if (mp.count(120)) cout << "120:yes" << endl;
	else cout << "120:no" << endl;
	cout << "删除后" << endl;
	mp.erase(10);
	if (mp.count(10)) cout << "10:yes" << endl;
	else cout << "10:no" << endl;





	return 0;
}

和set是一样的，不过多陈述，然后我们的无序map是经常用来实现图的数据结构的，因为它的插入和查找效率很高

#include <iostream>
#include <unordered_map>

using namespace std;


int main()
{
	unordered_map <int, vector<int>> edges;
	int n; cin >> n;
	int a, b;
	while (n--)
	{
		cin >> a >> b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}



	return 0;
}

哈希表算法题

1.哈希表模板题

#include <iostream>
#include <unordered_map>
using namespace std;


int main()
{
	unordered_map <string,int> mp;
	int T;cin>>T;
	while(T--)
	{
		int op;cin >> op;
		string t;
        int a;
		if(op == 1)
		{
			cin >> t >> a;
			mp[t] = a;
			cout << "OK" << endl;
		}
		else if(op == 2)
		{
		   cin >> t;
		   if(!mp.count(t)) cout << "Not found" << endl;
		   else cout << mp[t] << endl;
		   
		}
		else if(op == 3)
		{
			cin >> t;
			if(!mp.count(t)) cout << "Not found" << endl;
			else {
				mp.erase(t);
				cout << "Deleted successfully" << endl;
			}
		}
		else
		{
			cout << mp.size() << endl;
		}
	}
}

2.不重复数字

这道题我们用cin和cout过不了，我们换成scanf和printf就能过了，因为cin cout耗时多

#include <iostream>
#include <unordered_map>
using namespace std;

int main()
{
	int T;scanf("%d",&T);
	while(T--)
	{
		unordered_map <int,int> mp;
		int n;scanf("%d",&n);
		while(n--)
		{
			int t;scanf("%d",&t);
			if(!mp.count(t)) printf("%d ",t);
			mp[t]++; 
		}
		printf("\n");
	}
	
	
	return 0;
}

3.阅读理解

#include <iostream>
#include <unordered_map>
#include <set>
using namespace std;
unordered_map <string,set<int>> mp;

int main()
{
	int n;cin >> n;
	string t;
	int len;
    for(int i = 1;i<=n;i++)
    {
    	int tmp = i;
    	cin >> len;
    	while(len--)
    	{
    		cin >> t;
    		mp[t].insert(tmp);
		}
	}
	int m;cin >> m;
	while(m--)
	{
		cin >> t;
		for(auto e : mp[t])
		{
			cout << e << " ";
		}
		cout << endl;
	}
	
	
	
	return 0;
}

4.AB数对

这道题我们只要转换成A=B+C就行了，我们要做的就是把所有的数的出现次数都存在map里，然后我们只要找到符合B+C也就是A的出现次数的和就行了

#include <iostream>
#include <unordered_map>
typedef long long ll;
using namespace std;
const int N = 2e5+10;
ll a[N];
unordered_map <int,int> mp;
int main()
{
	int n;cin >> n;
	int c;cin >> c;
	for(int i = 1;i<=n;i++)
	{
		cin >> a[i];
		mp[a[i]]++;
	}
	ll ret = 0;
	for(int i = 1;i<=n;i++)
	{
		ret+=mp[a[i]+c];
	}
	cout << ret<< endl;
	
}

P3405 [USACO16DEC] Cities and States S

这道题比如我们看MI-FL  对应FL-MI，我们只要找到这种情况有多少对就行了

我们可以先把MIFL字符串存下来，当反过来的FLMI出现的时候，我们就计数器++就行了

#include <iostream>
#include <unordered_map>
using namespace std;
unordered_map <string,int> mp;

int main()
{
	int ret = 0;
	int n;cin >> n;
	string a,b;
	while(n--)
	{
		cin >> a >> b;
		a = a.substr(0,2);
		if(a==b) continue;
		ret+=mp[b+a];
		mp[a+b]++;
	}
	cout << ret << endl;
	
	return 0;
}


http://www.kler.cn/a/520979.html

相关文章：

  • 接口技术-第2次作业
  • Couchbase UI: Views
  • 游戏策划的分类
  • 可扩展架构：如何打造一个善变的柔性系统？
  • 顶刊JFR｜ROLO-SLAM：首个针对不平坦路面的车载Lidar SLAM系统
  • 苍穹外卖-day06
  • 算法每日双题精讲 —— 二分查找（寻找旋转排序数组中的最小值，点名）
  • ＜ OS 有关 ＞ 阿里云：轻量应用服务器 的使用 ：轻量化 阿里云 vpm 主机
  • 从单体应用到微服务的迁移过程
  • 基于LangGraph、Groq和Tavily打造可以调用外部搜索引擎工具的对话机器人（核心代码 万字详解）
  • 【Numpy核心编程攻略：Python数据处理、分析详解与科学计算】1.7 数组工厂：8种初始化方法性能横评
  • 5.1.2软件生存周期模型（二）
  • Linux初识：【冯诺依曼体系结构】【操作系统概念】【进程部分概念（进程状态）（进程优先级）（进程调度队列）】
  • Linux的基本指令（上）
  • 第28讲 程序是如何控制寄存器的
  • 从零到全栈开发
  • 在深度Linux (Deepin) 20中安装Nvidia驱动
  • MiniMax-01中Lightning Attention的由来（线性注意力进化史）
  • API接口设计模板
  • Zotero中使用Deepseek翻译
  • 基于Python的哔哩哔哩综合热门数据分析系统的设计与实现
  • 小程序开发实战：记录一天的 Bug 修复历程
  • 绘制决策树尝试2 内含添加环境变量步骤
  • AIGC时代下的Vue组件开发深度探索
  • Centos7系统php8编译安装ImageMagick/Imagick扩展教程整理
  • 数据结构课设——模糊查询汉字和其位置