有一筆資料的鍵值依序為32,17,85,16,51,60。使用除法雜湊函數
( )
mod 7
h k
k
來建立7 個桶(buckets)且每個桶只有一個槽(slot)的
雜湊表(hash table)。當發生碰撞(collision)與溢位問題時,
如果使用開放定址(open addressing)中的線性探測法(linear probing),
請寫出產生的雜湊表格。(5 分)而此方法的主要缺點為何?(5 分)
如果使用開放定址(open addressing)中的平方探測法(quadratic
probing),新的雜湊函數為:
,
mod 7
H k i
h k
i
,其中i 為目前
進行的探測次數。請寫出產生的雜湊表格。(10 分)
請說明何謂連結串列法(chaining)。(8 分)
請寫出使用連結串列法而產生的雜湊表格。(7 分)