第20课：冲突与解决
进度 0/24
💥
冲突与解决
撞柜不可怕，化解冲突有妙招！
📖知识引入
💥什么是冲突
两个不同的键算出同一个下标，如11%10和21%10都指向1号柜
📿链地址法
每个格子挂一条小链表，撞柜的元素排队住一起，查找时顺链比对
🎯开放寻址法
撞了就往后找下一个空位：1号被占住2号，2号不行去3号
📉负载因子
元素数÷格子数，比值越高冲突越频繁，快满时该扩容了
💡
链地址法实现简单又稳定，是竞赛与工程中最常用的冲突解决方案
🔍链地址法示意图与代码
// table[i] 存一个 vector，撞柜元素挂成小链
vector<pair<int, string>> table[10];
void insert(int key, string val) {
int h = key % 10; // 哈希定位
table[h].push_back({key, val}); // 撞柜就挂链尾
}
string find(int key) {
int h = key % 10;
for (auto& p : table[h]) // 只在冲突链里找
if (p.first == key) return p.second;
return "未找到";
}
// 11 和 21 都映射到 1 号柜，挂在同一条链上撞柜元素挂成链，定位后小范围查找，冲突轻松化解
🎯小测验
第1题：哈希冲突指的是？
第2题：链地址法如何处理冲突？
第3题：负载因子越高意味着？
📝本课知识点
- ✓冲突=不同键同下标
- ✓链地址法挂链最常用
- ✓负载因子高就该扩容
第20课完成！继续探索下一课吧 🚀