哈希表与集合
掌握哈希表原理、STL用法及高频应用
70%
🔑 哈希表原理与实现
🧰 STL哈希容器用法
🌟 典型应用与例题
💡 练习题与参考答案
哈希表原理与实现
哈希表通过哈希函数将关键码映射到数组下标，常用冲突解决有拉链法和开放寻址法：
// 拉链法哈希表
const int N = 10007;
vector<pair<int,int>> hashTable[N];
void insert(int key, int val) {
int h = key % N;
for (auto& p : hashTable[h]) if (p.first == key) { p.second = val; return; }
hashTable[h].push_back({key, val});
}
int find(int key) {
int h = key % N;
for (auto& p : hashTable[h]) if (p.first == key) return p.second;
return -1;
}// 开放寻址法哈希表
const int N = 10007;
int keyArr[N], valArr[N];
bool used[N];
void insert(int key, int val) {
int h = key % N;
while (used[h] && keyArr[h] != key) h = (h + 1) % N;
keyArr[h] = key; valArr[h] = val; used[h] = true;
}
int find(int key) {
int h = key % N;
while (used[h]) {
if (keyArr[h] == key) return valArr[h];
h = (h + 1) % N;
}
return -1;
}