《数据结构（C语言描述）（第2版）》教学课件7-09哈希函数冲突解决方法1

1、2016数据结构Data structure讲授：贺宁哈希函数冲突解决方法-1常州信息职业技术学院0203解决哈希冲突的方法 在使用哈希函数构造哈希表时，一旦发生冲突，应有较好的解决冲突的方法。解决冲突的方法有很多，这里只介绍开放定址法和拉链法，前者是将所有结点均存放在哈希表T0n-1中；后者通常是将互为同义词的结点链成一个单链表，而将此链表的头指针放在哈希表T0n-1中。1、开放定址法 线性探查法 二次（平方）探查法 线性补偿探查法2、拉链法04开放定址法一般形式 由关键字key得到的哈希地址H(key)一旦产生了冲突，即该地址已经存放了数据元素，就去寻找下一个空的哈希地址，只要哈希表足够大

2、，空的哈希地址总能找到，并将数据元素存入。H(Key) 开放定址法的一般形式 Hi=(H(key)+di)%n（1in-1） 其中：H(key)为冲突的哈希地址，di为增量序列，n为表长。 即按照将已发生冲突的哈希地址加上一个增量的方法寻找下一个空的哈希地址，依据增量序列不同的选取方法得到不同的解决冲突的方法。05线性探查法 将哈希表T0n-1看成是一个循环向量，若初始探查的地址为d（即H(key)=d），则最长的探查序列为：d,d+1,d+2,n-1,0,1,d-1。即探查时从地址d开始，首先探查Td，然后依次探查Td+1 直到Tn-1，此后又循环到T0直到Td-1为止。 探查过程终止于三种

3、情况： 若当前探查的单元为空，对于构造哈希表则将key写入其中，对于查找则表示查找失败； 若当前探查的单元中含有key，对于构造表则表示该记录已存入哈希表，对于查找则查找成功； 若探查到Td-1时仍未发现空单元也未找到key，对于构造表则此时表满，对于查找表示查找失败。06线性探查法 设关键字集合为47,18,29,11,16,95,22,8,3，哈希表表长为11，哈希函数为H(key)=key mod 11。采用线性探查法构造哈希表及在哈希表中查找过程如下： 构造哈希表：依次按哈希函数将关键字记录放入哈希表，47的地址为3，18的地址为7，29的地址也为7，与关键字18发生冲突，按线性探查法

4、，探查地址为8（8=7+1）的单元，由于地址为8的单元为空，所以将29放入，同样关键字95、8均需线性探查三次找到地址为9和10的空单元将其放入，关键字3需线性探查两次找到地址为4的空单元将其放入。按线性探查法构造的哈希表如下图所示。图示 线性探查法构造的哈希表07二次（平方）探查法 将哈希表T0n-1看成是一个循环向量，若初始探查的地址为d（即H(key)=d），则探查序列为：d,d+12,d-12,d+22,d-22,。即探查时从地址d开始，首先探查Td，然后依次探查Td+1, Td-1,Td+4,Td-4等等。 探查过程终止于三种情况： 若当前探查的单元为空，对于构造哈希表则将key写入其中，对于查找则表示查找失败； 若当前探查的单元中含有key，对于构造表则表示该记录已存入哈希表，对于查找则查找成功； 若探查到Td-1时仍未发现空单元也未找到key，对于构造表则此时表满，对于查找表示查找失败。08二次（平方）探查法设关键字集合为47,18,29,11,16,95,22,8,3，哈希表表长为11，哈希函数为H(key)=key mod 11。采用二次探查法构造哈希表及在哈希表中查找过程如下：构造哈希表：依次按哈希函数将关键字记录放入哈希表，其中关键字29需按二次探查法，探查两次得到地址为8的单元，将29放入，同样关键字95、需探查三次找到地