课程进度 65% · 第7/10章第7/10章 · 标签 1/2
— 1 —
哈希表原理与实现
哈希表通过哈希函数将关键码映射到数组下标，常用冲突解决有拉链法和开放寻址法：
cpp
1
// 拉链法哈希表
2
const int N = 10007;
3
vector<pair<int,int>> hashTable[N];
4
void insert(int key, int val) {
5
int h = key % N;
6
for (auto& p : hashTable[h]) if (p.first == key) { p.second = val; return; }
7
hashTable[h].push_back({key, val});
8
}
9
int find(int key) {
10
int h = key % N;
11
for (auto& p : hashTable[h]) if (p.first == key) return p.second;
12
return -1;
13
}
cpp
1
// 开放寻址法哈希表
2
const int N = 10007;
3
int keyArr[N], valArr[N];
4
bool used[N];
5
void insert(int key, int val) {
6
int h = key % N;
7
while (used[h] && keyArr[h] != key) h = (h + 1) % N;
8
keyArr[h] = key; valArr[h] = val; used[h] = true;
9
}
10
int find(int key) {
11
int h = key % N;
12
while (used[h]) {
13
if (keyArr[h] == key) return valArr[h];
14
h = (h + 1) % N;
15
}
16
return -1;
17
}
— 2 —
STL哈希容器用法
C++ STL提供了高效的哈希容器：
cpp
1
2
3
unordered_map<int, string> mp;
4
mp[1] = "one";
5
mp.count(2); // 判断key是否存在
6
unordered_set<int> st;
7
st.insert(3);
8
st.count(3); // 判断元素是否存在
拉链法开放寻址unordered_mapunordered_set哈希