处理冲突的方法

一、开放定址法（开地址法）
基本思想：有冲突时就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将数据元素存入
除留余数法：Hi=(Hash(key)+di) mod m (di为增量序列)
常用方法：
①线性探测法：di为1，2，…m-1线性序列
②二次探测法：di为12，-12，22，-22，…，q2二次序列
③伪随机探测法：di为伪随机数序列
二、链地址法（拉链法）
基本思想：相同散列地址的记录链成一单链表，m个散列地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构
链地址法建立散列表步骤：
①取数据元素的关键字key，计算其散列函数值（地址），若该地址对应的链表为空，则将该元素插入此链表
否则执行②解决冲突
②根据选择的冲突处理方法，计算关键字key的下一个存储地址，若该地址对应的链表为不为空，则利用链表的前插法或后插法将该元素插入此链表
优点：①非同义词不会冲突，无“聚集”现象
②链表上结点空间动态申请，更适合于表长不确定的情况
散列表的查找效率分析：
使用平均查找长度ASL来衡量查找算法，ASL取决于
①散列函数
②处理冲突的方法
③散列表的装填因子α
α越大，表中记录数越多，说明表装的越满，发生冲突的可能性越大，查找时比较次数就越多
结论：
①散列表技术具有很好的平均性能，优于一些传统的技术
②链地址法优于开地址法
③除留余数法作散列函数优于其他类型函数