民國109年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第75題
有一Hash Table 其 Hash 函數定義為 h1 (key)=key%11,其中%表示兩數相除後之餘數,當發生碰 撞(Collision)時採Doubl…
題目
有一Hash Table 其 Hash 函數定義為 h1 (key)=key%11,其中%表示兩數相除後之餘數,當發生碰 撞(Collision)時採Double Hashing 方式處理,其函數定義h(key, j)= (h1 (key) + j*h2(key) ) % 11, 其中j=0, 1, 2,..., 11; h2 (key)=1+(key%10) 。欲將26 放入Hash Table,在Hash Table 之探測順 序,那些是正確的?
- (1) 前8 個探測順序包括 1
- (2) 前8 個探測順序包括 5
- (3) 前8 個探測順序包括 7
- (4) 前8 個探測順序包括 9
官方答案
(3) 前8 個探測順序包括 7、(4) 前8 個探測順序包括 9
解析
計算探測序：h1(26)=26%11=4，h2(26)=1+(26%10)=1+6=7。雙重雜湊公式 h(26,j)=(4+7j)%11。依序得 j=0→4，j=1→0，j=2→7，j=3→3，j=4→10，j=5→6，j=6→2，j=7→9，j=8→5，j=9→1。前8個探測（j=0~7）為 4,0,7,3,10,6,2,9，包含 7 與 9，故選項3、4正確；1 與 5 分別出現在第9、8次，不在前8次內，故選項1、2錯誤。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。