[理工] [DS] 關於hashing 的 overflow

看板Grad-ProbAsk作者 (AG)時間15年前 (2011/01/26 16:34), 編輯推噓3(3推 0噓 14→)
留言17則, 6人參與, 最新討論串1/1
附個題目 http://www.lib.ntu.edu.tw/exam/graduate/97/97420.pdf 台大96 軟體設計 第二題 想請問一下如果說 今天hash處理 overflow 的機制是 rehashing, 那在rehashing的時候又該怎麼處理?! 可以利用chain 或者是 liner probing 嗎? 謝謝 :) -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.114.123.111
推
01/26 17:47, , 1F
Rehashing提供一系列hashing function H1,H2,...,Hm
01/26 17:47, 1F
→
01/26 17:49, , 2F
若發生overflow用H2,再發生overflow用H3.以此類推
01/26 17:49, 2F
→
01/26 17:49, , 3F
直到有空bucket or 全部函數用完為止
01/26 17:49, 3F
→
01/26 17:50, , 4F
其他overflow處理方式也一樣 再發生就在用一次該方式
01/26 17:50, 4F
→
01/26 19:49, , 5F
我遇到的問題是只有兩個hash fucntion
01/26 19:49, 5F
→
01/26 19:49, , 6F
那這樣overflow之後該怎麼辦呢?
01/26 19:49, 6F
推
01/26 19:52, , 7F
有題目嗎?!
01/26 19:52, 7F
附在上面嚕~ ※ 編輯: christianSK 來自: 140.114.123.116 (01/26 19:55)
→
01/26 22:53, , 8F
double hash table定義: h(i,k)=(h1(k)+ih2(k))
01/26 22:53, 8F
→
01/26 22:55, , 9F
i表示嘗試第幾次 k表示data
01/26 22:55, 9F
→
01/26 22:57, , 10F
簡單來說就是當用h1(k)發生collison時,h1(k)就去跳躍一
01/26 22:57, 10F
→
01/26 22:58, , 11F
h2(k),之後把整個結果再帶入h1 function
01/26 22:58, 11F
推
01/26 23:00, , 12F
之後如果又發生碰撞 i=1,2,3...依次帶入直到找到空的
01/26 23:00, 12F
→
01/26 23:03, , 13F
那請問如果 h1 + i*h2 超過size的話是怎麼處理?
01/26 23:03, 13F
→
01/26 23:06, , 14F
a大第一行最後要加個 mod m 吧
01/26 23:06, 14F
→
01/26 23:07, , 15F
抱歉那行定義是h(i,k)=(h1(k)+ih2(k))mod m 少打了...
01/26 23:07, 15F
→
01/26 23:09, , 16F
了解了~ 謝謝幾位 :)
01/26 23:09, 16F
→
09/11 14:10, , 17F
Rehashing提供 https://daxiv.com
09/11 14:10, 17F
‣ 更多 christianSK 的文章
文章代碼(AID): #1DFzoSnc (Grad-ProbAsk)