数据结构查找篇之散列查找
一、散列函数构造法
直接定地址
因为线性函数中，自变量和因变量是一一对应的。保证了不发生冲突
缺点：比较浪费空间
除留余数法
二、处理冲突方法
一般来讲，散列存储都会有不可避免的冲突问题，这个问题是肯定要解决的。
1、开放地址法
线性探测
如果冲突了，就顺序往后面填
二次探测
和顺序探测的策略不同，按照+1, -1, +2, -2…这种顺序探测下去
伪随机探测
如果冲突，就随机加一个伪随机数，再继续探测…直到最后不冲突为止
2、链地址法
简而言之，就是将散列表构造为一个邻接表。
每一个数据都可以挂在属于自己的key上面，感觉上就不存在冲突了，这种方法来的确实妙！
key相同的数据称为同义词
链地址查找的AsL：平均查找长度计算方法
三、查找总结
注意以下装填因子的概念，表明了这个表是否装的很满
散列查找的查找效率是最高的（比折半查找高），无冲突的时候能达到O(1)