普考申論題
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 小題
小題 (二)
假設每個籃子的容量最多可存二筆資料，請以上表鍵值之二進位表示法為例，用動態雜湊（dynamic hashing）的方法，將這八筆資料做 hash。（10 分）
思路引導 VIP
看到「動態雜湊（Dynamic Hashing）」，應直接聯想到最標準的「可延伸雜湊（Extendible Hashing）」，核心在於利用「全域深度（Global Depth, GD）」與「區域深度（Local Depth, LD）」來動態擴充目錄與籃子。本題承接第一小題除以4（即取最後2位元）的概念，故採用鍵值「最右側位元（LSB）」作為目錄的索引位元進行推導。
小題 (一)
假設雜湊函數（hashing function）是 key mod 4，亦即將 key 的值除以 4 之餘數值，即為雜湊函數值。假設每個籃子的容量最多可存三筆資料，請以上表之資料為例，將鍵值之二進位值轉換為十進位值，並將這些資料按所給的雜湊函數，區分為應有的籃子，並以此例說明什麼是靜態雜湊（static hashing）。（10 分）
思路引導 VIP
考生應先精準將二進位鍵值轉換為十進位，接著依序代入雜湊函數 key mod 4 求得目標籃子編號。分配資料時務必注意各籃子「容量上限為3筆」的限制；最後，藉由本題「籃子總數與空間皆為固定值」的特徵，順勢帶出靜態雜湊的定義與潛在的溢位（Overflow）隱憂。