[考題] 資訊處理 資料結構

[Neal121 (想像)]

題目：

假設輸入的資料是：7341.3123.1673.4919.4304.9179.1369，

使用的雜湊函數是 f(x) = x mod 10，x是輸入的資料，而雜湊表格的大小有10個位置，

編號從 0 ~ 9 ，每一位置只能儲存一筆資料，請分別回答下列問題：

(4)當溢位處理方法使用雙重雜湊(double hashing)時，

   第二個雜湊函數是  g(x) = 7-(x mod 7)，

   請寫出雜湊表格的內容。


From 95年高考



王老師解法：


(4) 表格內容如下： 9179無法找到 bucket存放。


表格編號   0     1     2     3     4     5     6     7     8     9

         1673  7341        3123  4304  1369                    4919




疑問：

1673為什麼會擺在表格0呢？

1673 mod 7 = 0，

g(1673) = 7- 0 = 7，

應該是放在7號桶子吧？！


麻煩各位解答了！








    [考題] 國考歷屆考題與考題觀念討論(書裡看到的選這個)請附上想法、出處

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.136.249.145
※ 文章網址: http://www.ptt.cc/bbs/Examination/M.1400922049.A.5C0.html
推 WCFEI:我想是因為他沒碰撞 有破撞才會用到第2的function
1763 有跟 3123碰撞阿！需要用g(x)在雜湊一次，不是嗎？

推 keieykdx:為什麼9179不能放呀@@
推 flydragon198:9179第二次的位置已經被放了，所以沒辦法放
9179是因為碰撞後用g(x)在雜湊發現還是碰撞，所以就沒位置放了

推 WCFEI:抱歉是我看錯了 不過7-(9179%7)不是=5嗎
→ WCFEI:高點的解答http://ppt.cc/f-3b
沒錯，所以這樣的話應該是

      0     1     2     3     4     5     6     7     8     9

          7341        3123  4304  9179        1673        4919

1369 會跟 4919 碰撞後用g(x)在雜湊一次，

然後與 3123 碰撞，所以沒位置。

這樣對嗎？  麻煩各位大師了。

推 panda555:怪哉  你有看王志強的版本嗎? 她的第2個HF是增量
→ panda555:不過  我有點忘了 你的算法是依照  洪毅教的嗎?
我最上面那個版本是王老師課本上的解答，

W大有提供王老師寫的解答 (又跟課本上不一樣，不過還是覺得怪怪的，

最下面的版本是我修改完後覺得沒問題的版本，

請問您覺得怎麼改會比較好呢？

推 kinglord:1673會在0是因為第一次在3碰撞後 用g(x)算出7表示要從3往
→ kinglord:往下數7格放
原來如此！感謝指導
※ 編輯: Neal121 (220.136.233.101), 06/01/2014 11:17:45
推 Sarturn:假設double hashing擺放rule是用g(x)的值,那1369該放2?