第三课《撞车事故现场——哈希冲突》一、国王的邮箱系统出事故了1、上一课里我们认识了哈希函数。1智慧大臣发明了 魔法编号机规则hash x % 10;2例如18 → 8号邮箱 25 → 5号邮箱 42 → 2号邮箱3大家都顺利找到了自己的邮箱。国王高兴极了“这真是世界上最伟大的发明”2、可是第二天早上。邮局管理员慌慌张张跑进皇宫。大喊“不好了不好了”“邮箱撞车了”二、什么叫撞车1、管理员拿出记录本。居民18计算18 % 10得到8进入8号邮箱2、又来了一个居民28计算28 % 10得到8竟然也是8号邮箱3、第三位居民38计算38 % 10结果还是8号邮箱4、现在情况变成8号邮箱 ├── 18 ├── 28 └── 385、国王傻眼了“怎么回事”“为什么三个居民抢同一个邮箱”三、哈希冲突出现了这种现象有个专业名字哈希冲突Hash Collision1、定义非常简单两个不同的数据 经过哈希函数计算 得到同一个位置就叫哈希冲突2、例如18 → 8 28 → 8 38 → 8虽然18 ≠ 28 ≠ 38但是hash(18) hash(28) hash(38)3、这就是 哈希冲突四、为什么一定会冲突1、有的同学会问“汉克老师能不能设计一个永远不冲突的哈希函数”答案❌ 基本不可能。2、我们来看看。邮箱数量10个居民数量100个3、请问100个人 放进 10个邮箱会发生什么肯定有邮箱里不止一个人。例如邮箱1 住10个人 邮箱2 住8个人 邮箱3 住12个人这就像100只小兔子 塞进10个笼子总会有笼子里挤着好几只兔子。4、这就是数学里的鸽巢原理又叫抽屉原理5、简单说东西比位置多 冲突必然发生五、哈希表管理员怎么办国王问“邮箱撞车了怎么办”智慧大臣笑了“没关系。”“我们早就准备好了办法。”于是。哈希王国发明了两种解决方案。第一种方案拉链法六、拉链法登场1假设18 → 8 28 → 8 38 → 8都进入8号邮箱2那怎么办大臣说“不要赶走他们。”“让他们排队。”于是8号邮箱 18 ↓ 28 ↓ 38变成8号邮箱 | |--18 | |--28 | |--383就像 一个宿舍里面住了18 28 38三个人。4这种方法叫拉链法Chain5为什么叫拉链法因为像衣服拉链一样一个接一个连起来。七、查找过程1、现在找282、先算28 % 10得到8号邮箱3、进入8号邮箱18 28 384、依次检查18 不是 28 找到成功八、拉链法的优点1、优点✅ 简单✅ 好理解✅ 实际应用广泛2、C很多哈希表实现都用了类似思想。第二种方案开放寻址法九、停车场故事1、智慧大臣又发明另一种办法。1假设18进入8号邮箱2现在28也想进入8号邮箱3结果发现8号邮箱满了怎么办2、大臣说“向后找空位”1例如邮箱编号 0 1 2 3 4 5 6 7 8 ←18 9 ←空2于是28放到9号邮箱3再来38计算8号邮箱发现8满了 9满了继续找。找到0号邮箱于是38放进去。4结果0 ←38 8 ←18 9 ←283、这种方法叫开放寻址法Open Addressing意思就是原来的位置满了 继续找空位置十、生活中的理解1、拉链法像什么电影院。第8排坐满了。于是18 28 38都坐在同一排。2、开放寻址法像什么停车场。车位8满了。那就停9 停0 停1 ……一直找空车位。十一、为什么冲突越少越好1、假设8号邮箱 18 28 38 48 58 68 78 88 982、现在找98必须看18 28 38 48 58 68 78 88 98才能找到。3、原本O(1)的查找。慢慢变成O(n)了。4、所以优秀哈希函数的目标是让数据尽量均匀分散不要全挤在一起。十二、现实中的哈希表1、实际C中的unordered_map内部已经帮我们做好了✅ 哈希函数✅ 冲突处理✅ 自动扩容2、例如unordered_mapint,int mp; mp[18] 1; mp[28] 2; mp[38] 3;即使发生冲突。程序员也不用管。系统自动处理。十三、小试牛刀规则hash x % 10;计算下面数字会进入哪个邮箱第一题15计算15 % 10 5答案5号邮箱第二题25计算25 % 10 5答案5号邮箱发生了什么答案 哈希冲突第三题35计算35 % 10 5答案5号邮箱结果5号邮箱 15 25 35又发生冲突了。本课总结1、今天我们认识了哈希表最大的敌人 哈希冲突Hash Collision2、什么是冲突不同数据 得到相同邮箱例如18 → 8 28 → 8 38 → 83、为什么会冲突数据太多 邮箱太少根据抽屉原理冲突不可避免4、解决办法方法1拉链法8号邮箱 18 ↓ 28 ↓ 38方法2开放寻址法8号邮箱满了 去9号 9号满了 去0号5、魔法口诀哈希表很神奇 快速查找效率高。 不同数据同位置 这就叫做哈希冲突。 拉链法排队站 开放寻址找空房。 冲突越少越优秀 查找速度才够强下一课我们将正式进入 C 的真实哈希表世界《藏宝图仓库——认识 unordered_map》届时同学们将第一次使用真正的unordered_mapstring,int实现姓名→分数、学号→学生等超级实用的哈希表应用