算法 - 模拟散列表

题目：模拟散列表

问题描述：
维护一个集合，支持以下操作：

1. I x，插入一个数 x；
2. Q x，询问数 x 是否在集合中出现过。

进行 N 次操作，对于每个询问操作输出对应的结果。

输入格式：

• 第一行包含整数 N，表示操作数量。
• 接下来 N 行，每行包含一个操作指令，操作指令为 I x 或 Q x 中的一种。

输出格式：

• 对于每个询问指令 Q x，输出 Yes 或 No，表示 x 是否在集合中出现过。

数据范围：

• 1≤N≤10⁵
• −10⁹≤x≤10⁹

输入样例：

5
I 1
I 2
I 3
Q 2
Q 5

输出样例：

Yes
No

代码实现

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5 + 3;
int h[N], e[N], ne[N], idx, n, m;
char str;
void insert(int x)
{
	int k = ((x % N) + N) % N; //先对x取模映射到h数组里面
	e[idx] = x;         //先将x存进e数组
	ne[idx] = h[k];     //使刚插进来的数指向前面一个结点
	h[k] = idx++;       //使指针指向当前结点（h[k]可以理解成尾指针）
}
bool query(int x)
{
	int k = ((x % N) + N) % N;
	int c = h[k];
	while (c != -1) //如果不为-1就表示有数字插入了该节点，遍历这个拉链
	{
		if (e[c] == x)
		{
			return true;
		}
		c = ne[c];  
	}
	return false;
}
int main()
{
	cin >> n;
	memset(h, -1, sizeof h);
	for (int i = 1; i <= n; i++)
	{
		cin >> str;
		if (str == 'I')
		{
			cin >> m;
			insert(m);
		}
		if(str=='Q')
		{
			cin >> m;
			if (query(m))
			{
				cout << "Yes" << endl;
			}
			else
				cout << "No" << endl;
		}
	}
	return 0;
}

代码思路总结

1. 数据结构选择

• 使用拉链法来处理哈希冲突。拉链法是一种常见的哈希表实现方式，通过在哈希表的每个槽中维护一个链表来解决冲突。
• 定义了三个数组：
  • h[N]：哈希表数组，h[k] 存储哈希值为 k 的链表的头节点索引。
  • e[N]：存储实际的值（即插入的数 x）。
  • ne[N]：存储链表中下一个节点的索引。

2. 哈希函数

• 哈希函数使用取模运算：k = ((x % N) + N) % N。
  • 这个哈希函数将任意整数 x 映射到 [0, N-1] 的范围内。
  • 通过 (x % N) + N 确保结果为非负数，然后再取模 N，确保结果在合法范围内。

3. 插入操作 (insert)

• 插入操作的步骤如下：
  1. 计算哈希值 k，确定 x 应该插入到哪个槽。
  2. 将 x 存入 e[idx] 中。
  3. 将 ne[idx] 指向当前槽的头节点 h[k]，表示新插入的节点指向原来的头节点。
  4. 更新 h[k] 为当前节点的索引 idx，表示新插入的节点成为新的头节点。
  5. 增加 idx，为下一个插入操作做准备。

4. 查询操作 (query)

• 查询操作的步骤如下：
  1. 计算哈希值 k，确定 x 可能位于哪个槽。
  2. 从 h[k] 开始遍历链表，检查链表中是否存在值等于 x 的节点。
  3. 如果找到相等的值，返回 true；否则遍历完链表后返回 false。

5. 主函数 (main)

• 主函数的逻辑如下：
  1. 读取操作数量 n。
  2. 初始化哈希表 h，将所有槽的头节点索引设置为 -1，表示初始时链表为空。
  3. 循环处理每个操作：
     • 如果是插入操作 I x，调用 insert(x) 将 x 插入哈希表。
     • 如果是查询操作 Q x，调用 query(x) 检查 x 是否在哈希表中，并输出 Yes 或 No。

6. 复杂度分析

• 时间复杂度：
  • 插入和查询操作的平均时间复杂度为 O(1)，因为哈希表的每个槽的链表长度在理想情况下是常数级别。
  • 最坏情况下（所有元素都映射到同一个槽），时间复杂度为 O(n)。
• 空间复杂度：
  • 使用了三个数组 h[N]、e[N] 和 ne[N]，空间复杂度为 O(N)。

算法刷题记录