地特四等申論題
107年
[統計] 資料處理概要
第 一 題
📖 題組：
二、有一資料表如下圖，共有八筆資料，第一欄是鍵值（key value）的二進位表示法（Binary representation），第二欄是姓氏資料。今要用雜湊（hash）的方式來將資料分成若干籃子（bucket），請回答下列有關雜湊的問題。 (一)假設雜湊函數（hashing function）是 key mod 4，亦即將 key 的值除以 4 之餘數值，即為雜湊函數值。假設每個籃子的容量最多可存三筆資料，請以上表之資料為例，將鍵值之二進位值轉換為十進位值，並將這些資料按所給的雜湊函數，區分為應有的籃子，並以此例說明什麼是靜態雜湊（static hashing）。（10 分） (二)假設每個籃子的容量最多可存二筆資料，請以上表鍵值之二進位表示法為例，用動態雜湊（dynamic hashing）的方法，將這八筆資料做 hash。（10 分）
二、有一資料表如下圖，共有八筆資料，第一欄是鍵值（key value）的二進位表示法（Binary representation），第二欄是姓氏資料。今要用雜湊（hash）的方式來將資料分成若干籃子（bucket），請回答下列有關雜湊的問題。 (一)假設雜湊函數（hashing function）是 key mod 4，亦即將 key 的值除以 4 之餘數值，即為雜湊函數值。假設每個籃子的容量最多可存三筆資料，請以上表之資料為例，將鍵值之二進位值轉換為十進位值，並將這些資料按所給的雜湊函數，區分為應有的籃子，並以此例說明什麼是靜態雜湊（static hashing）。（10 分） (二)假設每個籃子的容量最多可存二筆資料，請以上表鍵值之二進位表示法為例，用動態雜湊（dynamic hashing）的方法，將這八筆資料做 hash。（10 分）
📝 此題為申論題，共 2 小題
小題 (一)
假設雜湊函數（hashing function）是 key mod 4，亦即將 key 的值除以 4 之餘數值，即為雜湊函數值。假設每個籃子的容量最多可存三筆資料，請以上表之資料為例，將鍵值之二進位值轉換為十進位值，並將這些資料按所給的雜湊函數，區分為應有的籃子，並以此例說明什麼是靜態雜湊（static hashing）。（10 分）
思路引導 VIP
解題分三步：首先將二進位鍵值精確轉換為十進位；接著依據雜湊函數（key mod 4）算出對應的籃子編號，並注意每個籃子最多 3 筆容量的限制來放置資料；最後利用此例固定 4 個籃子且籃子 0 剛好存滿的現象，點出靜態雜湊「空間大小固定不變」的特性與溢位風險。
小題 (二)
假設每個籃子的容量最多可存二筆資料，請以上表鍵值之二進位表示法為例，用動態雜湊（dynamic hashing）的方法，將這八筆資料做 hash。（10 分）
思路引導 VIP
本題考查動態雜湊（Dynamic Hashing），最典型的代表為「可擴充雜湊（Extendible Hashing）」。解題關鍵在於設定全域深度（Global Depth）與區域深度（Local Depth），並依序插入資料。遇到容量溢位（大於 2 筆）時，若區域深度等於全域深度，則需擴充目錄；若小於，則僅分裂籃子。需主動宣告採用「前綴位元（Prefix）」做為索引依據，展示嚴謹的演算法邏輯。