数据结构检索（查找）之入土攻略（三）
接上一篇《数据结构检索（查找）之入土攻略（二）》：https://blog.****.net/wydyd110/article/details/82144549
目录
5.1.2 平方探测法（Quadratic Probing）
5 冲突排解
目前，世间还没有十全十美的散列函数，还不能做到完全避免冲突，就跟我们无法保证每天都大便通畅。既然冲突不能避免，那么当务之急是要考虑如何处理它。
5.1 开放地址法（Open Addressing）
当你看上了一个女神，却发现她有男朋友了，这时候你要怎么办？换一个女神经去喜欢啊，天涯何处无芳草，何必单恋一枝花呢？这其实就是开放地址法对于冲突的处理方式。
开放定址法：一旦产生了冲突（该地址已有其它元素），就按某种规则去寻找另一空地址。
5.1.1线性探测法（Linear Probing）
线性探测法：以增量序列 1，2，……，（TableSize -1）循环试探下一个存储地址。
47 / 11 = 4 ......3 7 / 11 = 0......7 其他同理
分析：
成功平均查找长度（查找表中关键词的平均查找比较次数，冲突次数加1）
ASLs = （1+7+1+1+2+1+4+2+4）/ 9 = 23/9 ≈ 2.56
（11一找就找到了，所以查找了1次，其他同理）
不成功平均查找长度 （不在散列表中的关键词的平均查找次数）ASLu = （3+2+1+2+1+1+1+9+8+7+6）/ 11 = 41/11 ≈ 3.73
（当要查找的关键词的散列值为0，按照线性探测法，需要查找比较3次，才能确定该关键词不在散列表中）
（当要查找的关键词的散列值为1，按照线性探测法，需要查找比较2次，才能确定该关键词不在散列表中）
（当要查找的关键词的散列值为2，按照线性探测法，需要查找比较1次，才能确定该关键词不在散列表中）
其他同理
分析：
（表中8-25省略不写）
ASLs：表中关键词的平均查找比较次数
ASL s= （1+1+1+1+1+2+5+3）/ 8 = 15/8 ≈ 1.87
ASLu：不在散列表中的关键词的平均查找次数（不成功）
根据H(key)值分为26种情况：H值为0,1,2,…,25
ASL u= （9+8+7+6+5+4+3+2+1*18）/ 26 = 62/26 ≈ 2.38
5.1.2 平方探测法（Quadratic Probing）
5.1.3 双散列探测法（Double Hashing）
（引用自《大话数据结构》）
（引用自张铭的《数据结构与算法》）
5.1.4 再散列（Rehashing）
5.2 链地址法
随便问十个程序员他的女朋友是谁，有九个回答是新垣结衣，由此可以意淫出一个新恒结衣身后吊着一长串屌丝程序员的画面。大家一起手拉手共同守护同一个老婆也是可以的对吧。这就引出了另一种冲突解决方法：
分离链接法：将相应位置上冲突的所有关键词存储在同一个单链表中。
不管多累，为了老婆要努力学下去哦。
（引用自《大话数据结构》）
6 散列表的性能分析
数据结构检索（查找）之入土攻略到此倒一段落，然鹅，我已经学到了虚脱