天天看點

散清單(四):沖突處理的方法之開位址法(二次探測再散列的實作)

前面的文章分析了開位址法的其中一種:線性探測再散列,這篇文章來講開位址法的第二種:二次探測再散列

(二)、二次探測再散列

為改善“堆積”問題,減少為完成搜尋所需的平均探查次數,可使用二次探測法。

通過某一個散列函數對表項的關鍵碼 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.