文档介绍：哈希表与哈希函数2哈希表与哈希函数(2)2010-11-1016::(1)冲突不同的关键字值,具有相同的哈希地址,因而被映射到同一表位置上。该现象称为冲突(Collision)或碰撞。【例】上图中的k2?k5,但h(k2)=h(k5),故k2和K5所在的结点的存储地址相同。(2)安全避免冲突的条件如何避免冲突发生,则取决于哈希函数的构造。使散列地址均匀地分布在哈希表的整个地址区间内,这样可以避免或减少发生冲突。哈希函数的构造,与关键字的长度、哈希表的大小、关键字的实际取值状况等许多因素有关,而且有的因素事前不能确定。所以,避免冲突这并非是件容易做到的事。(3)冲突不可能完全避免由于关键字的值域往往比哈希表的个数大的多,所以哈希函数是一种压缩映射,碰撞是难免的。【例】存贮100个学生记录,尽管安排120个地址空间,但由于学生名假设不超过10个英文字母的理论个数超过2610,要找到一个哈希函数把100个任意的学生名映射成[0,119]内的不同整数,实际上是不可能的。问题在于一旦发生了冲突应如何处理。,但实际上发生冲突的可能性仍是存在的。当关键字值域远大于哈希表的长度,而且事先并不知道关键字的具体取值时。冲突就难免会发生。另外,当关键字的实际取值大于哈希表的长度时,而且表中已装满了记录,如果插入一个新记录,不仅发生冲突,而且还会发生溢出。因此,处理冲突和溢出是哈希技术中的两个重要问题。1、开放定址法用开放定址法解决冲突的做法是:当冲突发生时,使用某种探查亦称探测技术在散列表中形成一个探查测序列。沿此序列逐个单元地查找,直到找到给定的关键字,或者碰到一个开放的地址即该地址单元为空为止(若要插入,在探。查找时探查到开放查到开放的地址,则可将待插入的新结点存人该地址单元)的地址则表明表中无待查的关键字,即查找失败。?用开放定址法建立散列表时,建表前须将表中所有单元更严格地说,是指单元中存储的关键字置空。?空单元的表示与具体的应用相关。按照形成探查序列的方法不同,可将开放定址法区分为线性探查法、线性补偿探测法、随机探测等。(1)线性探查法(LinearProbing)该方法的基本思想是:将散列表T[-1]看成是一个循环向量,若初始探查的地址为d(即h(key)=d),则最长的探查序列为:d,d+l,d+2,…,m-1,0,1,…,d-1即探查时从地址d开始,首先探查T[d],然后依次探查T[d+1],…,直到T[m-1],此后又循环到T[0],T[1],…,直到探查到T[d-1]为止。探查过程终止于三种情况:若当前探查的单元为空,则表示查找失败(若是插入则将key写入其中);若当前探查的单元中含有key,则查找成功,但对于插入意味着失败;-1]时仍未发现空单元也未找到key,则无论是查找还是插入若探查到T[d均意味着失败此时表满。利用开放地址法的一般形式,线性探查法的探查序列为:hi=(h(key)+i)%m0?i?m-1//即di=i用线性探测法处理冲突,思路清晰,算法简单,但存在下列缺点:?处理溢出需另编程序。一般可另外设立一个溢出表,专门用来存放上述哈希表中放不下的记录。此溢出表最简单的结构是顺序表,查找方法可用顺序查找。?按上述算法建立起来的哈希表,删除工作非常困难。假如要从哈希表HT