散列冲突 查找 - 散列技术 - 处理冲突的方法（一）

查找 - 散列技术 - 处理冲突的方法（一）  

　　处理冲突的方法

　　通常有两类方法处理冲突 开放定址(Open Addressing)法和拉链(Chaining)法 前者是将所有结点均存放在散列表T[ m

　　 ]中;后者通常是将互为同义词的结点链成一个单链表 而将此链表的头指针放在散列表T[ m ]中

　　 开放定址法

　　( )开放地址法解决冲突的方法

　　用开放定址法解决冲突的做法是 当冲突发生时 使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列 沿此序列逐

　　个单元地查找 直到找到给定的关键字 或者碰到一个开放的地址(即该地址单元为空)为止(若要插入 在探查到开放的地址 则可

　　将待插入的新结点存人该地址单元) 查找时探查到开放的地址则表明表中无待查的关键字 即查找失败

　　注意

　　①用开放定址法建立散列表时 建表前须将表中所有单元(更严格地说 是指单元中存储的关键字)置空

　　②空单元的表示与具体的应用相关

　　【例】关键字均为非负数时 可用 来表示空单元 而关键字为字符串时 空单元应是空串

　　总之 应该用一个不会出现的关键字来表示空单元

　　( )开放地址法的一般形式

　　开放定址法的一般形式为 h i =(h(key)+d i )%m ≤i≤m

　　其中

　　①h(key)为散列函数 d i 为增量序列 m为表长

　　②h(key)是初始的探查位置 后续的探查位置依次是h l h … h m 即h(key) h l h … h m 形成了一

　　个探查序列

　　③若令开放地址一般形式的i从 开始 并令d = 则h =h(key) 则有

　　h i =(h(key)+d i )%m ≤i≤m

　　探查序列可简记为h i ( ≤i≤m )

　　( )开放地址法堆装填因子的要求

　　开放定址法要求散列表的装填因子α≤l 实用中取α为 到 之间的某个值为宜

　　( )形成探测序列的方法

　　按照形成探查序列的方法不同 可将开放定址法区分为线性探查法 二次探查法 双重散列法等

　　①线性探查法(Linear Probing)

　　该方法的基本思想是

　　将散列表T[ m ]看成是一个循环向量 若初始探查的地址为d(即h(key)=d) 则最长的探查序列为

　　d d+l d+ … m … d

　　即:探查时从地址d开始 首先探查T[d] 然后依次探查T[d+ ] … 直到T[m ] 此后又循环到T[ ] T[ ] … 直到探查到

　　T[d ]为止

　　探查过程终止于三种情况

　　( )若当前探查的单元为空 则表示查找失败(若是插入则将key写入其中);

　　( )若当前探查的单元中含有key 则查找成功 但对于插入意味着失败;

　　( )若探查到T[d ]时仍未发现空单元也未找到key 则无论是查找还是插入均意味着失败(此时表满)

　　利用开放地址法的一般形式 线性探查法的探查序列为