Biu
哈希表按照存储方式而言分为两种实现方法：
开放寻址法（闭散列）拉链法（开散列）至于这两个的概念即定义可参考之前的博文：
[C++ 系列] 82. 详解哈希结构解决哈希冲突及模拟实现闭散列、开散列
其与离散化一样，都是将大值域小数量的数据进行映射的紧密存储，但是 离散化是一种特殊的哈希方式，它要求映射后数据保序。
在算法题目中，一般是仅有添加和查找两种操作，并不需要在哈希表中执行删除操作。如果真的需要删除，都是开一个数组，在待删除点处打一个标记。
哈希函数的模数一般取成一个质数，并且离 2 的整次幂，前后尽可能的远，这是个经验值，数学中可以证明。
主要还是一个单链表的操作，类似于这样的基础数据结构，还是得多多练习深刻掌握其原理。
并且图论所采用的稀疏图邻接表的存储的数据结构和这一模一样。
模板代码：
#include <iostream> #include <cstring> using namespace std; const int N = 1e5+3; // 大于10w的第一个质数 int h[N], e[N], ne[N], idx; void insert(int x) { int k = (x % N + N) % N; // 处理负数情况 e[idx] = x; ne[idx] = h[k]; h[k] = idx; idx ++; } bool find(int x) { int k = (x % N + N) % N; for (int i = h[k]; i != -1; i = ne[i]) if (e[i] == x) return true; return false; } int main() { memset(h, -1, sizeof h); // 清空所有槽，-1 代表空指针，该位置没元素 int n; cin >> n; while (n --) { char op[2]; int x; cin >> op >> x; if (op[0] == 'I') insert(x); else { if (find(x)) cout << "Yes" << endl; else cout << "No" << endl; } } return 0; }同一道题目。
开到题目数据范围的 2 到 3 倍，这样冲突率就很低了。具体就不讲概念了，我的 C++ 博文讲解的很详细。
// 开放寻址法 #include <iostream> #include <cstring> using namespace std; const int N = 2e5+3; // 大于20w的第一个质数 const int null = 0x3f3f3f3f; // 超越数据范围作为数据不在哈希表中的一个标记 int h[N]; // 如果x在哈希表存在则返回在哈希表中的位置 // 若不存在，则返回应该在哈希表中存放的位置 int find(int x) { int k = (x % N + N) % N; while (h[k] != null && h[k] != x) { // 如果哈希表该位置有人，并且不为x k ++; // 找下一个坑位 if (k == N) k = 0; // 找完了，从头开始 } return k; } int main() { memset(h, 0x3f, sizeof h); // 清空所有槽，-1 代表空指针，该位置没元素 int n; cin >> n; while (n --) { char op[2]; int x; cin >> op >> x; int k = find(x); if (op[0] == 'I') h[k] = x; else { if (h[k] != null) cout << "Yes" << endl; else cout << "No" << endl; } } return 0; }