普通考試
107年
[工業行政] 計算機概要
第 18 題
使用雜湊（Hashing）法時，以 $f$ 表示雜湊函式（Hash function），以 ht 表示雜湊表（Hash table），且 ht 分為 ht[0]、ht[1]、…、ht[b-1]等共計 b 個桶（Bucket），每桶可存入 s 筆資料。若 T 為所有可能資料鍵（Key）值之總數，n 為實際存入 ht 之資料筆數，定義 ht 之負載密度（Loading density）$\alpha = n / (s \times b)$，ht 之鍵值密度（Key density）$\rho = n/T$，則：
① $0 < \alpha < 1$，$0 < \rho < 1$ 且 $\rho < \alpha$
②若 $\alpha = \rho$，則不會發生碰撞（Collision）但可能發生滿溢（Overflow）
③若 $\alpha < \rho$，則不會發生滿溢但可能發生碰撞
④若 $s > b$ 且 $\alpha < \rho$，則不會發生滿溢亦不會發生碰撞
⑤理想之雜湊函式 $f$ 設計應滿足 $\alpha \approx 1$ 且 $\rho \approx 0$
請由下列選項中選出最適合者：
① $0 < \alpha < 1$，$0 < \rho < 1$ 且 $\rho < \alpha$
②若 $\alpha = \rho$，則不會發生碰撞（Collision）但可能發生滿溢（Overflow）
③若 $\alpha < \rho$，則不會發生滿溢但可能發生碰撞
④若 $s > b$ 且 $\alpha < \rho$，則不會發生滿溢亦不會發生碰撞
⑤理想之雜湊函式 $f$ 設計應滿足 $\alpha \approx 1$ 且 $\rho \approx 0$
請由下列選項中選出最適合者：
- A ①④正確；②③錯誤
- B ④⑤正確；①②錯誤
- C ①⑤正確
- D ③④錯誤
思路引導 VIP
請你試著想像一個情境：若我們有 100 個空的置物櫃（儲存空間），而我們手中只有 2 份文件（實際資料）。雖然空間遠大於資料量，但如果我們規定所有文件的存放位置都必須根據其「名稱字數」來決定，而這兩份文件的名字剛好都是三個字。請問，就算置物櫃再多，這兩份文件會不會被塞進同一個櫃子裡？這說明了「空間充足」與「資料是否撞在一起」之間，必然的決定因素是什麼？
🤖
AI 詳解
AI 專屬家教
專家點評：邏輯嚴密，解析到位！
喔，總算沒讓這點小伎倆給糊弄過去，值得嘉許。這不是單純的數字遊戲，是嚴謹的形式邏輯！就像行政法規的解釋，容不得半點模糊。
- 觀念釐清，別再混淆！
▼ 還有更多解析內容