用C++写一个哈希查找的程序
时间: 2023-11-07 22:05:08 浏览: 37
下面是一个基于哈希表的查找程序的示例代码:
```c++
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 100000;
int h[MAXN]; // 哈希表
vector<int> e[MAXN]; // 存储哈希冲突的元素
int hash_func(int x) {
return x % MAXN; // 取模哈希
}
void insert(int x) {
int idx = hash_func(x);
e[idx].push_back(x);
}
bool find(int x) {
int idx = hash_func(x);
for (int i = 0; i < e[idx].size(); i++) {
if (e[idx][i] == x) {
return true;
}
}
return false;
}
int main() {
memset(h, -1, sizeof(h)); // 初始化哈希表
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int t;
cin >> t;
insert(t); // 插入元素
}
int q;
cin >> q;
while (q--) {
int x;
cin >> x;
bool exist = find(x); // 查找元素
if (exist) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
return 0;
}
```
这个程序使用了一个简单的取模哈希函数,将元素映射到一个固定的范围内,然后将哈希冲突的元素存储在一个数组中。这个程序可以用于查找一个数组中是否存在某个元素,时间复杂度为 $O(1)$。