作者panyasan (=w=)
看板Grad-ProbAsk
標題[理工] Hashing
時間Sat Feb 1 15:20:26 2020
https://i.imgur.com/K7FYwDE.jpg
想請問這題要怎麼想,看到有人說想成平均失敗搜尋次數不太了解為什麼
謝謝！
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.173.97.250 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1580541628.A.AC6.html
1F：→ DLHZ: 關鍵在於uniform02/01 15:38
2F：→ DLHZ: uniform所以想像每個slot都分到一樣多的key02/01 15:40
3F：推 ponwar87123: 那他給sequence用意在哪裡呢02/01 15:50
4F：→ DLHZ: 可能是出題上的失誤？如果以給定的算出來是2.402/01 16:05
所以如果不管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
5F：推 mistel: 為什麼只算平均失敗搜尋次數 @@？ 02/01 16:32
6F：→ mistel: 我是回原po 02/01 16:33
7F：→ panyasan: 因為13/5=2.6不是每個都找到最後一個,然後沒有找到的意 02/01 16:40
8F：→ panyasan: 思嗎 02/01 16:40
9F：推 mistel: 比較次數的期望值是這個意思嗎？ 02/01 16:47
10F：推 ponwar87123: 不好意思借我歪個樓，問一下有關hash的敘述 02/01 17:12
11F：→ ponwar87123: when hash chaining is used to resolve overflows, 02/01 17:12
12F：→ ponwar87123: the search for a key involves comparison with key 02/01 17:12
13F：→ ponwar87123: s that have different hash value 02/01 17:12
14F：→ ponwar87123: 是T or F 02/01 17:12
15F：推 mistel: false closed addressing 02/01 17:14
16F：推 ponwar87123: 錯在differfent hash value嗎 02/01 17:24
17F：→ DLHZ: 你誤會了 跟平均失敗沒什麼關係 02/01 18:28
18F：→ DLHZ: @pon 他說chaining了 要比一定是同樣的hash value 02/01 18:30
19F：推 ponwar87123: 好的 謝謝～ 02/01 18:36
20F：→ panyasan: 謝謝兩位大大！！ 02/01 20:12