处理冲突的方法2.docx

: .
处理冲突的方法
通常有两类方法处理冲突：开放定址(OpenAddressing)法和拉链(Cha即:探查时从地址d开始，首先探查T[d]，然后依次探查T[d+1]，…，直到T[m-1]，此后又循环到T[0]，T[1]，…，直到探查到T[d-1]为止。
探查过程终止于三种情况：
(1) 若当前探查的单元为空，则表示查找失败(若是插入则将key写入其中)；若当前探查的单元中含有key,则查找成功，但对于插入意味着失败；
若探查到T[d-1]时仍未发现空单元也未找到key,则无论是查找还是插入均意味着失败(此时表满)。
利用开放地址法的一般形式,线性探查法的探查序列为：
hi=(h(key)+i)%m0<iwm〃即di=i利用线性探测法构造散列表【】已知一组关键字为(26,36,41,38,44,15,68,12,06,51),用除余法构造散列函数,用线性探查法解决冲突构造这组关键字的散列表。
解答:为了减少冲突，通常令装填因子a
由除余法的散列函数计算出的上述关键字序列的散列地址为(0,10,2,12,5,2,3,12,6,12)。前5个关键字插入时，其相应的地址均为开放地址，故将它们直接插入T[0]，T[10)，T[2]，T[12]和T[5]中。
当插入第6个关键字15时，其散列地址2(即h(15)=15%13=2)已被关键字41(15和41互为同义词)占用。故探查h1=(2+1)%13=3，此地址开放，所以将15放入T[3]中。
当插入第7个关键字68时，其散列地址3已被非同义词15先占用，故将其插入到T[4]中。
当插入第8个关键字12时，散列地址12已被同义词38占用，故探查hl=(12+1)%13=0，而T[0]亦被26占用，再探查h2=(12+2)%13=1，此地址开放，可将12插入其中。
类似地，第9个关键字06直接插入T[6]中；而最后一个关键字51插人时，因探查的地址12，0，1，…，6均非空，故51插入T[7]中。
构造散列表的具体过程【参见动画演示】聚集或堆积现象用线性探查法解决冲突时，当表中i,i+1，…，i+k的位置上已有结点时，一个散列地址为i,i+1，…，i+k+1的结点都将插入在位置i+k+1上。把这种散列地址不同的结点争夺同一个后继散列地址的现象称为聚集或堆积(Clustering)。这将造成不是同义词的结点也处在同一个探查序列之中，从而增加了探查序列的长度，即增加了查找时间。若散列函数不好或装填因子过大，都会使堆积现象加剧。
【例】上例中，h(15)=2，h(68)=3,即卩15和68不是同义词。但由于处理15和同义词41的冲突时，15抢先占用了T[3]，这就使得插入68时，这两个本来不应该发生冲突的非同义词之间也会发生冲突。为了减少堆积的发生，不能像线性探查法那样探查一个顺序的地址序列(相当于顺序查找)，而应使探查序列跳跃式地散列在整个散列表中。
② 二次探查法(QuadraticProbing)
二次探查法的探查序列是：
hi=(h(key)+i*i)%m0<iwm〃即di=i2即探查序列为d=h(key)，d+12，d+22，…