高考申論題
106年
[資訊處理] 資料結構
第 三 題
📖 題組：
請依序將 17, 23, 36, 13, 38, 11, 52, 44, 25, 35, 2, 18, 21 儲存至下列 13 桶（buckets）× 1 槽（slots）的雜湊表（hashing table）。請以各小題所設定的雜湊函式（hashing function）將資料依序存入並顯示最後的雜湊表。 （一）雜湊函式 F(x) = x mod 13，碰撞時，採取「線性探測法」（open addressing with linear probing）來放入資料。請顯示最後的雜湊表。（5 分） （二）雜湊函式 F(x) = x mod 13，碰撞時，採取「二次方探測法」（open addressing with quadratic probing）來放入資料。請顯示最後的雜湊表。（5 分） （三）雜湊函式 F1(x) = x mod 13，碰撞時，採取「雙探測法」（open addressing with double hashing）來放入資料，第二雜湊函式為 F2(x) = 7－(x mod 7)。請顯示最後的雜湊表。（5 分） （四）若雜湊表夠大（例如 slots = 2 或更大）但資料量多時，針對三種碰撞時所採取的處理方式，請說明那一種方式較能有效率的儲存或搜尋資料？請說明那一種處理方式效率最差？（5 分）
請依序將 17, 23, 36, 13, 38, 11, 52, 44, 25, 35, 2, 18, 21 儲存至下列 13 桶（buckets）× 1 槽（slots）的雜湊表（hashing table）。請以各小題所設定的雜湊函式（hashing function）將資料依序存入並顯示最後的雜湊表。 （一）雜湊函式 F(x) = x mod 13，碰撞時，採取「線性探測法」（open addressing with linear probing）來放入資料。請顯示最後的雜湊表。（5 分） （二）雜湊函式 F(x) = x mod 13，碰撞時，採取「二次方探測法」（open addressing with quadratic probing）來放入資料。請顯示最後的雜湊表。（5 分） （三）雜湊函式 F1(x) = x mod 13，碰撞時，採取「雙探測法」（open addressing with double hashing）來放入資料，第二雜湊函式為 F2(x) = 7－(x mod 7)。請顯示最後的雜湊表。（5 分） （四）若雜湊表夠大（例如 slots = 2 或更大）但資料量多時，針對三種碰撞時所採取的處理方式，請說明那一種方式較能有效率的儲存或搜尋資料？請說明那一種處理方式效率最差？（5 分）
📝 此題為申論題，共 4 小題
小題 (三)
雜湊函式 F1(x) = x mod 13，碰撞時，採取「雙探測法」（open addressing with double hashing）來放入資料，第二雜湊函式為 F2(x) = 7－(x mod 7)。請顯示最後的雜湊表。（5 分）
思路引導 VIP
雙重探測法的核心在於當第一個雜湊位置 F1(x) 發生碰撞時，使用第二個雜湊函數 F2(x) 作為探測的步長。公式為：H(x, i) = (F1(x) + i * F2(x)) mod 13，其中 i 遞增直到找到空位，依序代入數字並仔細記錄佔用的桶位即可得出正解。
小題 (一)
雜湊函式 F(x) = x mod 13，碰撞時，採取「線性探測法」（open addressing with linear probing）來放入資料。請顯示最後的雜湊表。（5 分）
思路引導 VIP
本題重點在於運用模除求出雜湊位址，並在使用「線性探測法」時，遇到碰撞即往後尋找下一個空位。若超過雜湊表最大索引，則從頭（Index 0）繼續尋找，需仔細追蹤每一個資料放入時的索引狀態。
小題 (二)
雜湊函式 F(x) = x mod 13，碰撞時，採取「二次方探測法」（open addressing with quadratic probing）來放入資料。請顯示最後的雜湊表。（5 分）
思路引導 VIP
本題測試雜湊表的碰撞處理機制。看到「二次方探測法」，應立即聯想到碰撞時的探測公式：H_i = (F(x) + i^2) mod 13，亦即當發生碰撞時，依序往後加上 1^2, 2^2, 3^2... 的位移量，直到找到空槽位為止。計算時需謹慎逐步推導，避免因為一個槽位填錯導致後續連鎖錯誤。
小題 (四)
若雜湊表夠大（例如 slots = 2 或更大）但資料量多時，針對三種碰撞時所採取的處理方式，請說明那一種方式較能有效率的儲存或搜尋資料？請說明那一種處理方式效率最差？（5 分）
思路引導 VIP
評估雜湊表碰撞處理機制的效率，核心在於「聚集（Clustering）」現象的嚴重程度。考生應直指線性探測法易產生「主聚集」導致效率最差，而雙探測法能同時解決主、次聚集，使資料分佈最均勻、效率最佳。
雜湊碰撞處理技術
💡 利用探測公式解決雜湊表位址衝突，並優化資料分佈均勻度。
| 比較維度 | 線性探測 (Linear) | VS | 雙雜湊 (Double) |
|---|---|---|---|
| 探測公式 | (H(x)+i) mod M | — | (F1(x)+i*F2(x)) mod M |
| 步長變化 | 固定步長 (1) | — | 依 F2(x) 動態決定步長 |
| 聚簇問題 | 嚴重一級聚簇 | — | 無聚簇問題，分佈均勻 |
| 搜尋效率 | 最差（需多次探測） | — | 最佳（探測次數最少） |
💬雙雜湊透過第二雜湊函數分散碰撞位址，效率與空間利用率皆優於線性探測。
