[理工] Hashing

看板Grad-ProbAsk作者 (=w=)時間4年前 (2020/02/01 15:20), 4年前編輯推噓7(7推 0噓 13→)
留言20則, 4人參與, 4年前最新討論串1/1
https://i.imgur.com/K7FYwDE.jpg
想請問這題要怎麼想,看到有人說想成平均失敗搜尋次數不太了解為什麼 謝謝！ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.173.97.250 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1580541628.A.AC6.html
→
02/01 15:38, 4年前 , 1F
關鍵在於uniform
02/01 15:38, 1F
→
02/01 15:40, 4年前 , 2F
uniform所以想像每個slot都分到一樣多的key
02/01 15:40, 2F
推
02/01 15:50, 4年前 , 3F
那他給sequence用意在哪裡呢
02/01 15:50, 3F
→
02/01 16:05, 4年前 , 4F
可能是出題上的失誤？如果以給定的算出來是2.4
02/01 16:05, 4F
所以如果不管sequence。expected number of key comparison只看平均失敗搜尋次數就 好,是因為搜尋機乎都是失敗的嗎 ※ 編輯: panyasan (1.173.97.250 臺灣), 02/01/2020 16:22:28 ※ 編輯: panyasan (1.173.97.250 臺灣), 02/01/2020 16:24:06
推
02/01 16:32, 4年前 , 5F
為什麼只算平均失敗搜尋次數 @@？
02/01 16:32, 5F
→
02/01 16:33, 4年前 , 6F
我是回原po
02/01 16:33, 6F
→
02/01 16:40, 4年前 , 7F
因為13/5=2.6不是每個都找到最後一個,然後沒有找到的意
02/01 16:40, 7F
→
02/01 16:40, 4年前 , 8F
思嗎
02/01 16:40, 8F
推
02/01 16:47, 4年前 , 9F
比較次數的期望值是這個意思嗎？
02/01 16:47, 9F
推
02/01 17:12, 4年前 , 10F
不好意思借我歪個樓，問一下有關hash的敘述
02/01 17:12, 10F
→
02/01 17:12, 4年前 , 11F
when hash chaining is used to resolve overflows,
02/01 17:12, 11F
→
02/01 17:12, 4年前 , 12F
the search for a key involves comparison with key
02/01 17:12, 12F
→
02/01 17:12, 4年前 , 13F
s that have different hash value
02/01 17:12, 13F
→
02/01 17:12, 4年前 , 14F
是T or F
02/01 17:12, 14F
推
02/01 17:14, 4年前 , 15F
false closed addressing
02/01 17:14, 15F
推
02/01 17:24, 4年前 , 16F
錯在differfent hash value嗎
02/01 17:24, 16F
→
02/01 18:28, 4年前 , 17F
你誤會了 跟平均失敗沒什麼關係
02/01 18:28, 17F
→
02/01 18:30, 4年前 , 18F
@pon 他說chaining了 要比一定是同樣的hash value
02/01 18:30, 18F
推
02/01 18:36, 4年前 , 19F
好的 謝謝～
02/01 18:36, 19F
→
02/01 20:12, 4年前 , 20F
謝謝兩位大大！！
02/01 20:12, 20F
‣ 更多 panyasan 的文章
文章代碼(AID): #1UDIQyh6 (Grad-ProbAsk)