作者iamhebe ( bbb)
站內Grad-ProbAsk
標題[理工] [資結] Hashing function overflow Quadratic
時間Mon Feb 14 10:09:57 2011
當 hashing function 發生 overflow 時
若選擇 Quadratic probing 為處理發方式
我看洪逸給的定義是
+
Address = ( H(x) - i^2 ) mod B , B 為 Bucket 數目
所以當overflow發生時
第一次 i = 1
Address = ( H(x) + i^2 ) mod B 若沒找到
則
Address = ( H(x) - i^2 ) mod B
然後交大99資結第2.題
給 h(X) = ( X mod 10 )
Quadratic probing F(i) = 2*i^2
當 overflow 發生時
第一次 i = 1
Address = ( h(X) + 2*i^2 ) mod 10
雖然題目好像只設計會發生一次 overflow
但我想問的是
如果還是發生overflow
那要找的位置是
Address = ( h(X) - 2*i^2 ) mod 10 依然代入 i = 1
還是
Address = ( h(X) + 2*i^2 ) mod 10 然後代入 i = 2
不懂的地方在於Quadratic probing
洪逸給的定義跟交大給的不一樣
是 Quadratic probing 本來就沒有明確定義
要看題目給的還是如何
所以想要弄清楚QQ
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.248.217.3
※ 編輯: iamhebe 來自: 111.248.217.3 (02/14 10:12)
1F：推 rnbjacky:洪兔給的是horo 上面的 +- 上下兩邊跑 不過這題都定義 02/14 10:38
2F：→ rnbjacky:+了 所以 就一直往下找應該就可以了(i =1.2.3...) 02/14 10:39
3F：→ rnbjacky:cormen書上定義就真的是一個二次方程式 i = 0.1.2... 02/14 10:40
4F：→ wolfswolfs:題目沒定義+啊 正常來說還是要+-兩邊跑 02/14 10:40
5F：→ rnbjacky:所以應該是由題目給定 沒特別講就用horo書上的方式去做囉 02/14 10:40
6F：→ wolfswolfs:這題過程是 89放9 18放8 49餘數9所以49+2*i^2 mod 10=1 02/14 10:41
7F：→ wolfswolfs:所以答案是C 02/14 10:41
8F：→ dy957:這題用哪個答案都一樣的樣子 02/14 10:49
9F：推 rnbjacky:請問wolfswolfs大 最後會把69放在哪個slot? 02/14 10:59
10F：→ rnbjacky:我是會放3 QQ 02/14 11:00
11F：→ wolfswolfs:我會放7耶0.0 02/14 11:15
12F：推 rnbjacky:恩恩 用 +-我也會放 7 只不過我用 i=1.2.3..去做offset 02/14 11:31
13F：→ rnbjacky:原po想問的應該是這個差別吧.... 02/14 11:32
14F：推 boy5548:這題應該要用+-下去跑吧 02/14 11:42
15F：推 koehie:那 58 呢 02/14 15:59
16F：→ xygod:58放0吧 02/14 16:14
17F：推 koehie:嗯 02/14 16:24