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

模拟散列表(算法题）

news 2025/5/10 10:49:50

在这里插入图片描述

#include <bits/stdc++.h>
using namespace std;// 哈希表的大小设置为200003（质数减少冲突概率）
const int N = 200003;
// 用0x3f3f3f3f表示空位，该值通常不在输入数据范围内
const int null = 0x3f3f3f3f;
int h[N]; // 哈希表数组，初始化为null/** 查找x在哈希表中的位置，若存在返回其索引，否则返回应插入的位置* 使用线性探测解决冲突*/
int find(int x)
{// 计算初始哈希值，处理负数情况：(x % N + N)确保结果非负// 例如：x=-5时，t = (-5 % 200003 + 200003) % 200003 = 199998int t = (x % N + N) % N;// 当当前位置非空且不等于x时，继续查找// 模拟：假设x=100，t=100，但h[100]已被占用，则t递增到101、102...直到找到空位或x的位置while (h[t] != x && h[t] != null) {t++; // 线性探测下一位置if (t == N)t = 0; // 循环到表头继续查找}// 返回找到的位置，可能是x的位置或可插入的空位return t;
}int main()
{// 初始化哈希表，所有位置设为nullmemset(h, 0x3f, sizeof(h));int n;cin >> n;string op;int x;while (n--) {cin >> op >> x; // 读取操作符和数值int t = find(x); // 查找x的位置if (op == "I") {// 插入操作：无论t位置是否已被占用，都存入x（覆盖旧值）// 例如：若x=100的t=100且h[100]为空，则直接插入；若冲突则存入后续位置h[t] = x;} else {// 查询操作：检查t位置是否为x// 例如：若h[t]==x则存在，否则不存在if (h[t] == null)cout << "No" << endl;elsecout << "Yes" << endl;}}return 0;
}