作者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/cn.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