[理工] Hashing panyasan PTT批踢踢實業坊

[理工] Hashing

作者: panyasan (=w=) 2020-02-01 15:20:26

https://i.imgur.com/K7FYwDE.jpg
想請問這題要怎麼想,看到有人說想成平均失敗搜尋次數不太了解為什麼
謝謝！

作者: DLHZ ( ) 2020-02-01 15:38:00

關鍵在於uniformuniform所以想像每個slot都分到一樣多的key

作者: ponwar87123 (干我屁事喔北七) 2020-02-01 15:50:00

那他給sequence用意在哪裡呢

作者: DLHZ ( ) 2020-02-01 16:05:00

可能是出題上的失誤？如果以給定的算出來是2.4

作者: mistel (Mistel) 2020-02-01 16:32:00

為什麼只算平均失敗搜尋次數 @@？我是回原po

作者: panyasan (=w=) 2020-02-01 16:40:00

因為13/5=2.6不是每個都找到最後一個,然後沒有找到的意思嗎

作者: mistel (Mistel) 2020-02-01 16:47:00

比較次數的期望值是這個意思嗎？

作者: ponwar87123 (干我屁事喔北七) 2020-02-01 17:12:00

不好意思借我歪個樓，問一下有關hash的敘述when hash chaining is used to resolve overflows,the search for a key involves comparison with keys that have different hash value是T or F

作者: mistel (Mistel) 2020-02-01 17:14:00

false closed addressing

作者: ponwar87123 (干我屁事喔北七) 2020-02-01 17:24:00

錯在differfent hash value嗎

作者: DLHZ ( ) 2020-02-01 18:28:00

你誤會了跟平均失敗沒什麼關係@pon 他說chaining了要比一定是同樣的hash value

作者: ponwar87123 (干我屁事喔北七) 2020-02-01 18:36:00

好的謝謝～

作者: panyasan (=w=) 2020-02-01 20:12:00

謝謝兩位大大！！

繼續閱讀

[理工] 離散一題，以及test_and_setponwar87123 [理工] 108台聯電子一題duncan1315 [理工] 計組 p. 110lucy35 [理工] 108 交大 OS 7 10mimi9672 [理工] ［計系］交大108 14 15zaqxsw2230 [理工] 線性代數代數eigenvector是否獨立ponwar87123 [理工] 計組-cache miss計算ponwar87123 [理工] 102台聯計組vanness1257 [理工] 108 交大計系題組Aoepop [理工] 計組 101 交大lucy35