[理工] 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