前面的文章分析了开地址法的其中一种:线性探测再散列,这篇文章来讲开地址法的第二种:二次探测再散列
(二)、二次探测再散列
为改善“堆积”问题,减少为完成搜索所需的平均探查次数,可使用二次探测法。
通过某一个散列函数对表项的关键码 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.