地特三等申論題
108年
[資訊處理] 資料結構
第 一 題
📖 題組：
將下列六個鍵值: 33, 72, 71, 55, 112, 109 存入大小為 19 的雜湊表（a hash table of size 19）。雜湊函數 h 為: h(key) = key mod 19。分別用下面兩種衝突處理方式（collision handler）： (一)間隔為 1（offset of 1）（12 分） (二)間隔為商（quotient-offset）（8 分） 請分別寫出兩個雜湊表；並在間隔為 1 的雜湊表上，標示出一次聚集（primary clustering）。
將下列六個鍵值: 33, 72, 71, 55, 112, 109 存入大小為 19 的雜湊表（a hash table of size 19）。雜湊函數 h 為: h(key) = key mod 19。分別用下面兩種衝突處理方式（collision handler）： (一)間隔為 1（offset of 1）（12 分） (二)間隔為商（quotient-offset）（8 分） 請分別寫出兩個雜湊表；並在間隔為 1 的雜湊表上，標示出一次聚集（primary clustering）。
📝 此題為申論題，共 2 小題
小題 (一)
間隔為 1（offset of 1）
思路引導 VIP
先計算各鍵值的初始雜湊值（取 19 的餘數），接著依序將鍵值放入表中；若發生衝突，以線性探測（往後加 1 並取餘數）尋找下一個空位。最後標示出由於連續佔用而產生的『一次聚集』（Primary Clustering）區段。
小題 (二)
間隔為商（quotient-offset）
思路引導 VIP
看到「間隔為商（quotient-offset）」，應立即想到它是雙重雜湊（Double Hashing）的一種，發生衝突時的探測步長為鍵值除以表格大小的商數（即 offset = key / 19）。解題時應先計算每個鍵值的初始雜湊值，並於衝突發生時計算 offset，依照 (h(key) + i * offset) mod 19 依序尋找下一個空位，務必將每個鍵值的計算步驟清晰列出。