[課業] 106高考-資料結構 第五題第三小題

106高考-資料結構 第五題第三小題 考選部 http://wwwc.moex.gov.tw/ExamQuesFiles/Question/106/106090_26050.pdf 高點參考答案 https://goo.gl/GLp3B2 題目 請依序將17, 23, 36, 13, 38, 11, 52, 44, 25, 35, 2, 18, 21 儲存至下列13 桶（buckets）× 1 槽（slots）的雜湊表（hashing table） 。請以各小題所設定的雜湊函式（hashing function） 將資料依序存入並顯示最後的雜湊表。 (三) 雜湊函式F1(x) = x mod 13，碰撞時，採取「雙探測法」（open addressing with double hashing）來放入資料，第二雜湊函式為F2(x) = 7-(x mod 7) 。請顯示最後的雜湊表。 各位好　我有兩個地方不懂　 1. 第(三)小題 第一個雜湊函數是F1(x) = x mod 13 ,第二個雜湊函數是F2(x) = 7-(x mod 7) 當發生第一次碰撞時 是用x代入F2(x) = 7-(x mod 7)嗎? 還是用x mod 13的結果 代入F2(x) = 7-(x mod 7)? 2. 使用雙雜湊函式 若發生第二次碰撞時 該怎麼處理？是用linear probing嗎? 還是? 高點那個答案不知道怎麼算出來的? 謝謝 ----------------------------------------------------------------- 有人回信問怎麼算的 我算一下前面幾個就好 後面算法都一樣 我就省略了 17 mod 13 = 4 23 mod 13 = 10 36 mod 13 = 10 <-- 碰撞, 7-(36 mod 7) = 6 所以 (10+6k) mod 13,k=1,2,3... <-- 這邊你要 (36+6k) mod 13 也是可以,意思一樣 k=1, 16 mod 13 = 3 13 mod 13 = 0 38 mod 13 = 12 11 mod 13 = 11 52 mod 13 = 0 <-- 碰撞, 7-(52 mod 7) = 4 所以 (0+4k) mod 13,k=1,2,3... k=1, 4 mod 13 = 4 <-- 碰撞 k=2, 8 mod 13 = 8 44 mod 13 = 5 . . . -- 謝謝 若增量是n 表示持續+kn(k=1,2,3...) 直到找到空的slot為止嗎? 感謝
※ 批踢踢實業坊(ptt.cc), 來自: 60.251.182.4
※ 文章網址: https://www.ptt.cc/bbs/Examination/M.1510024568.A.FC5.html

推 alan0204: 第二次是增量 11/07 13:10

→ a828203: 是的，找到為止... 11/07 19:17