天天看点

散列表(四):冲突处理的方法之开地址法(二次探测再散列的实现)

前面的文章分析了开地址法的其中一种:线性探测再散列,这篇文章来讲开地址法的第二种:二次探测再散列

(二)、二次探测再散列

为改善“堆积”问题,减少为完成搜索所需的平均探查次数,可使用二次探测法。

通过某一个散列函数对表项的关键码 x 进行计算,得到桶号,它是一个非负整数。 

散列表(四):冲突处理的方法之开地址法(二次探测再散列的实现)

若设表的长度为TableSize = 23,则在线性探测再散列 举的例子中利用二次探查法所得到的散列结果如图所示。

散列表(四):冲突处理的方法之开地址法(二次探测再散列的实现)

比如轮到放置Blum 的时候,本来应该是位置1,已经被Burke 占据,接着探测 H0 + 1 = 2,,发现被Broad 占据,接着探测 H0 - 1 = 

0,发现空位于是放进去,探测次数为3。

下面来看具体代码实现,跟前面讲过的线性探测再散列 差不多,只是探测的方法不同,但使用的数据结构也有点不一样,此外还实

现了开裂,如果装载因子 a > 1/2; 则建立新表,将旧表内容拷贝过去,所以hash_t 结构体需要再保存一个size 成员,同样的原因,

为了将旧表内容拷贝过去,hash_node_t 结构体需要再保存 *key 和 *value 的size。

散列表(四):冲突处理的方法之开地址法(二次探测再散列的实现)

common.h:

hash.h:

hash.c:

main.c:

simba@ubuntu:~/Documents/code/struct_algorithm/search/hash_table/quardratic_probing$ ./main 

The hash table has allocate.

4568 BBBB 23

not found

The hash table has free.