試題詳解

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）α = n /（s × b），ht 之鍵 值密度（Key density）ρ = n/T，則： ①0＜α＜1，0＜ρ＜1 且 ρ＜α ②若 α＝ρ，則不會發生碰撞（Collision）但可能發生滿溢（Overflow） ③若 α＜ρ，則不會發生滿溢但可能發生碰撞 ④若 s＞b 且 α＜ρ，則不會發生滿溢亦不會發生碰撞 ⑤理想之雜湊函式 f 設計應滿足 α ≈ 1 且 ρ ≈ 0 請由下列選項中選出最適合者：
(A)①④正確；②③錯誤
(B)④⑤正確；①②錯誤
(C)①⑤正確
(D)③④錯誤