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

CC44.【C++ Cont】哈希表的模拟实现

article 2025/3/19 0:14:44

1.知识回顾

2.题目

3.线性探测法

无穷大为什么取0x3f3f3f3f?

不建议使用0xffffffff或者0x7fffffff

设置成0x3f3f3f3f的好处

1.便于设置内存

2.值的数量级

哈希函数以及处理哈希冲突

哈希函数hash_func的设计

添加元素

查找元素

main函数

4.链地址法

哈希函数以及处理哈希冲突

哈希函数

添加元素

查找元素

main函数

1.知识回顾

参见CC43.【C++ Cont】哈希表的简介文章

2.题目

题目描述：
维护一个数据结构,初始时为空.支持下面操作:
1 x 插入元素 x
2 x 查询 x 是否在数据结构中
现有n次操作,针对每次查询,输出是否在该数据结构中。
输入描述：
第一行一个整数n,表示查询次数
之后 n 行，第i行两个整数op和x ，分别表示第op个操作以及元素 x 。
测试用例：
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

下面使用两种方法来模拟实现:

3.线性探测法

模数的取法:最大数为10,因此找10*2==20(一般来说扩大两倍)后的质数:23,如果最大数为1e5,一般找+3后的1e5+3

则对于本题来说:创建一个有23个元素的数组hash_table,数组的每个int元素初始化为无穷大(一般取0x3f3f3f3f)

无穷大为什么取0x3f3f3f3f?

不建议使用0xffffffff或者0x7fffffff

按理来说,4字节的最大值应该是0xffffffff,但数组元素的类型为int,其取值为-2,147,483,648~2,147,483,647,其中2,147,483,647==0x7fffffff,那为什么无穷大不取0x7fffffff呢?

答:设置成0x7fffffff容易导致溢出的问题,可能会变成一个很小的负数,例如0x7fffffff+1用int类型表示,值为值为-2147483648,是一个很小的负数

设置成0x3f3f3f3f的好处

1.便于设置内存

一般来说设置数组元素的初始值是用for循环对每个元素单独设置,其实使用memset更快,因为0x3f3f3f3f是右4个0x3f组成的,便于设置内存空间,且速度比for循环快

测试两种方法的快慢:

#include <iostream>
#include <time.h>
using namespace std;
const int N = 9999999;
int hash[N];
int main()
{
	size_t beign1 = clock();
	for (int i = 0; i < N; i++)
		hash[i] = 0x3f3f3f3f;
	size_t end1 = clock();
	size_t beign2 = clock();
	memset(hash, 0x3f, sizeof(hash));
	size_t end2 = clock();
	cout <<"使用for循环设置所需要的时间" << end1 - beign1 <<"ms"<< endl;
	cout << "使用memset设置所需要的时间" << end2 - beign2 << "ms" << endl;
	return 0;
}

运行结果:

2.值的数量级

0x3f3f3f3f为1061109567,数量级为10的9次方级别的,而int类型的最大值2147483647也为10的9次方级别的,一般的数据不会大于10^9,且0x3f3f3f3f的两倍仍然小于int类型的最大值,无穷大加无穷大还是无穷大

数组初始化函数init

const int N=23,INF=0x3f3f3f3f;
int hash_table[N];
void init()
{
	memset(hash_table,0x3f,sizeof(hash_table));	
}

哈希函数以及处理哈希冲突

之前在CC43.【C++ Cont】哈希表的简介文章中讲过除留余数法:hash(key) = key % N

但key有可能是负数,取模之后会变成负数!!!负数补正的操作:加上模数,但是正数加上模数会变大.因此统一再取一次模,简称(模加模),即

hash(key) = (key % N + N) % N

哈希函数hash_func的设计

例如返回数data映射的位置,则有hash(data) = (data % N + N) % N

如果直接像下面这样写会有问题,没有办法解决哈希冲突

int hash_func(int data)
{
	return (data % N + N) % N;
}

改进:

//返回data映射的位置
int hash_func(int data)
{
	int id = (data % N + N) % N;//id<=N-1
	//h[id]!=INF找没有存过data的位置 
	//h[id]!=data找已经存过data的位置
	while (hash_table[id] != INF && hash_table[id] != data)
	{
		id++;//id<=N-1,id++最大为N,不可能超过N,不会有越界的风险
		if (id == N)//走到头了 
			id = 0;
	}
	return id;
}

注意while循环的条件!

添加元素

设添加元素data,显然要先找到data在哈希表中映射的位置,再为那个位置赋值

void insert(int data)
{
	int id = hash_func(data);
	hash_table[id] = data;
}

或者只写一行

hash_table[hash_func(data)]=data;

查找元素

bool find(int data)
{
	int id = hash_func(data);
	return hash_table[id] == data;
}

注:删除元素在这里不实现,比较麻烦

main函数

int main()
{
	init();//使用哈希表前一定要初始化
	int n;
	cin >> n;
	while (n--)
	{
		int op, x;
		cin >> op >> x;
		if (op == 1)
			insert(x);
		else if (find(x))
			cout << "yes" << endl;
		else
			cout << "no" << endl;
	}
	return 0;
}

运行结果:

4.链地址法

实现思想和C35.【C++ Cont】树的存储文章的链式前向星相同

mp[i]相当于头指针head[i]

哈希函数以及处理哈希冲突

哈希函数

int hash_func(int data)
{
	return (data % N + N) % N;//直接返回,不用像线性探测那样需要进一步处理
}

添加元素

void insert(int data)
{
	int id=hash_func(data);//对对应在head[id]
	//先将data放入链表中
	id++;
	val[id]=data;
	//执行头插
	next[id]=head[id];
	head[id]=id; 
}

查找元素

数字data,从链表的头head[id]开始向后查询即可

bool find(int data)
{
	int id=hash_func(data);//从链表的开头head[id]开始向后查询 
	for (int i=head[id];i;i=next[i])
		if (val[i]==data)
			return true;
			
	return false;
}