某系統A 使用雜湊表（hash table）儲存不同的正整數鍵值，亦即不允許重 複鍵值，雜湊表有11 個儲存格，索引從0 開始，雜湊函數（hash functi…

題目

某系統A 使用雜湊表（hash table）儲存不同的正整數鍵值，亦即不允許重 複鍵值，雜湊表有11 個儲存格，索引從0 開始，雜湊函數（hash function） 為 ( ) A h k k mod ，其用平方探查法（quadraticprobing）處理碰撞（collision） 問題，探查序列為 ( ) ( ( ) ) 11( 0,1,2,...) A A ih k h k i mod i ，刪除資料時， 被刪除資料的位置標記為特殊符號DELETED。請回答下列問題： 給定一個空的雜湊表，依序插入下列鍵值22、1、13、24、35、46、7、 18，請畫出所有鍵值插入完成後的雜湊表狀態，並列出插入鍵值46 時 的完整探查過程。（10 分） 承上題，依序刪除鍵值24、13，畫出刪除後的雜湊表狀態。並說明為 什麼刪除鍵值時需用DELETED 標記，而不能將該鍵值所在的儲存格 恢復成「從未存放過鍵值」的空狀態。（5 分） 承上題，執行插入鍵值12，請列出插入時的探查過程、操作停止的理 由，並寫出12 最後插入那一個儲存格。插入時，DELETED 標記視為 可放入新鍵值的儲存格。請注意鍵值不能重覆。（5 分） 相較於系統A，考慮另一個採用平方探查法之系統，系統B 的表格大小 為8，索引亦從0 開始，雜湊函數 ( ) B h k 及探查序列 ( ) B ih k 分別定義為 ( ) B h k k mod 、 ( ) ( ( ) ) 8 ( 0,1,2,...) B B ih k h k i i mod i 。在非均 勻雜湊（non-uniform hashing）的情況下，也就是許多鍵值可能被分配 到相同或少數幾個初始雜湊位置時，那一個系統的雜湊表儲存格利用 率可能較高？並說明理由。（5 分）

參考解答（AI 生成，非官方）

• 一、插入完成後的雜湊表（hash table）狀態：依序插入22、1、13、24、35、46、7、18後，索引0至10的內容為：0:22、1:1、2:13、3:24、4:空、5:18、6:35、7:46、8:7、9:空、10:空。其中24、35、46、18均曾與其他鍵值碰撞，經平方探查法（quadratic probing）後才找到空位。
• 二、插入46的完整探查：h_A(46)=46 mod 11=2。i=0檢查索引2，已有13；i=1檢查2+1=3，已有24；i=2檢查2+4=6，已有35；i=3檢查2+9=11≡0，已有22；i=4檢查2+16=18≡7，索引7為空，故將46放入索引7。探查偏移依序為0、1、4、9、16。
• 三、刪除24與13後：將索引3的24及索引2的13標記為DELETED（刪除標記），表狀態為0:22、1:1、2:DELETED、3:DELETED、4:空、5:18、6:35、7:46、8:7、9:空、10:空。搜尋時DELETED仍須視為曾被占用，不可直接當成空白而跳過。
• 四、必須使用DELETED的理由：平方探查的搜尋會沿著固定探查序列前進；若把刪除格直接改回空白，後續鍵值（例如與13同為初始位置2的35、46）之搜尋可能在空白處提前停止，造成明明存在卻找不到的假陰性（false negative）。DELETED可保留探查鏈，插入時又可重複使用。
• 五、插入12的過程：h_A(12)=12 mod 11=1。i=0檢查索引1，已有1；i=1檢查1+1=2，該格為DELETED且表中無12，故將12放入索引2並停止。停止理由是遇到可重用的DELETED格，且已確認鍵值不重複；12最後插入索引2。
• 六、系統B的利用率比較：系統A較高。系統B大小為8，i^2 mod 8只會循環出現0、1、4，故同一初始位置的鍵值最多只能探查3個儲存格，非均勻雜湊（non-uniform hashing）時容易提前失敗；系統A大小11為質數，i=0至5的平方餘數共6個相異位置0、1、3、4、5、9，且表較大，非均勻時可容納更多同義字，利用率較高。

AI 依官方試題文字產生的參考解答，非考選部公告答案，內容僅供備考參考。

官方資料

• 官方試題 PDF