09年自考《数据结构》各章要点二[10]

散列技术将结点按其关键字的散列地址存储到散列表的过程称为散列

散列函数的选择有两条标准简单和均匀

常见的散列函数构的造方法

·平方取中法hash=int((x^)%)

·除余法表长为mhash=x%m

·相乘取整法hash=int(m*(x*Aint(x*A));A=

·随机数法hash=random(x)

处理沖突的方法

开放定址法 一般形式为hi=(h(key)+di)%m≤i≤m开放定址法要求散列表的装填因子α≤

·开放定址法类型

·线性探查法address=(hash(x)+i)%m

·二次探查法address=(hash(x)+i^)%m

·双重散列法address=(hash(x)+i*hash(y))%m

·拉链法 是将所有关键字为同义词的结点链接在同一个单链表中

·拉链法的优点

·拉链法处理沖突简单且无堆积现象

·链表上的结点空间是动态申请的适于无法确定表长的情况

·拉链法中α可以大于结点较大时其指针域可忽略因此节省空间

·拉链法构造的散列表删除结点易实现

·拉链法也有缺点当结点规模较小时用拉链法中的指针域也要占用额外空间还是开放定址法省空间

[] [] [] [] [] [] [] [] [] [] [] []