|
处理沖突的方法 通常有两类方法处理沖突开放定址(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)则最长的探查序列为 dd+ld+…m…d 即:探查时从地址d开始首先探查T[d]然后依次探查T[d+]…直到T[m]此后又循环到T[]T[]…直到探查到 T[d]为止 探查过程终止于三种情况 ()若当前探查的单元为空则表示查找失败(若是插入则将key写入其中); ()若当前探查的单元中含有key则查找成功但对于插入意味着失败; ()若探查到T[d]时仍未发现空单元也未找到key则无论是查找还是插入均意味着失败(此时表满) 利用开放地址法的一般形式线性探查法的探查序列为 h i =(h(key)+i)%m ≤i≤m //即d i =i |
