前面的文章分析了開位址法的其中一種:線性探測再散列,這篇文章來講開位址法的第二種:二次探測再散列
(二)、二次探測再散列
為改善“堆積”問題,減少為完成搜尋所需的平均探查次數,可使用二次探測法。
通過某一個散列函數對表項的關鍵碼 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.