PAT甲级1145 Hashing - Average Search Time (25分) 二次探测法知识点讲解

超、凢脫俗 2023-07-05 10:19 1阅读 0赞

这道题需要额外补充的知识点是Quadratic probing和Average Search Time。题目都没有解释，需要知识储备，所以当年不知道这道题是难倒了多少人。

题目链接：[https://pintia.cn/problem-sets/994805342720868352/problems/994805343236767744][https_pintia.cn_problem-sets_994805342720868352_problems_994805343236767744]

# Quadratic probing （二次探测法） #

简而言之，探测间隔为平方数。

处理冲突的函数为 H(key)=(key+i\*i)%TSize   \{i=1,2,3,...\}

本题的哈希函数为H(key)=key%TSize，也就是说，大小为5的数组，数字10放在第0位，因为10%5=0。

如果第0位已经有人了，处理冲突的办法就是10+1\*1=11，11%5=1，去找第1位。

如果第1位已经有人了，处理冲突的办法就是10+2\*2=14，14%5=4，去找第4位。

如果第4位已经有人了，处理冲突的办法就是10+3\*3=19，19%5=4，去找第4位。

这个时候肯定是不行的了，要说 10* cannot be inserted.*

# Average Search Time （平均查找时间） #

题目给出了计算的公式：查找的次数 / 查找的元素个数。

注意：

1.每次查找还是要按二次探测法来查找，不是挨个找，而且上面公式的那个i的范围是0到TSize。

所以查找的总次数=【每次查找不同取值j的个数】的和。

2.查找失败的标志是理应插入的位置上为0，不是别的数（否则就是碰撞）或者自己（否则就是查找成功）

所以查找时需要判断v\[pos\]==0，是的话要跳出查找，并且这个过程对查找次数的贡献也是跟查找成功的过程一样。

liuchuo的代码写得很过关，直接参考她的就行：

[https://www.liuchuo.net/archives/4671][https_www.liuchuo.net_archives_4671]

知乎上也有这个问题的讨论：

[https://www.zhihu.com/question/289072558][https_www.zhihu.com_question_289072558]

[https_pintia.cn_problem-sets_994805342720868352_problems_994805343236767744]: https://pintia.cn/problem-sets/994805342720868352/problems/994805343236767744
[https_www.liuchuo.net_archives_4671]: https://www.liuchuo.net/archives/4671
[https_www.zhihu.com_question_289072558]: https://www.zhihu.com/question/289072558

发表评论取消回复

表情：

评论列表（有 0 条评论，1人围观）

还没有评论，来说两句吧...

相关阅读

相关 PAT（甲级）1078 Hashing (25point(s))

题目题目链接思路先判断原题hash位置有没有被占用，如果被占用，就进行二次平方探查；代码#include <iostream>#include <str...

阳光穿透心脏的1/2处/ 2024年05月08日 05:59/ 0 赞/ 120 阅读

相关 PAT 甲级 1075 PAT Judge (25 分) 铭记

1075 PAT Judge (25 分) The ranklist of PAT is generated from the status list, which sh

本是古典何须时尚/ 2024年02月19日 21:33/ 0 赞/ 134 阅读

相关 PAT 甲级 1003 Emergency (25 分)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

红太狼/ 2023年08月17日 16:03/ 0 赞/ 151 阅读

相关 PAT1145 Hashing - Average Search Time

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

旧城等待，/ 2023年07月24日 15:59/ 0 赞/ 61 阅读

相关 PAT甲级1145 Hashing - Average Search Time (25分) 二次探测法知识点讲解

这道题需要额外补充的知识点是Quadratic probing和Average Search Time。题目都没有解释，需要知识储备，所以当年不知道这道题是难倒了多少人。题

超、凢脫俗/ 2023年07月05日 10:19/ 0 赞/ 2 阅读

相关 1145. Hashing - Average Search Time (25)

The task of this problem is simple: insert a sequence of distinct positive integers into

r囧r小猫/ 2022年05月28日 08:29/ 0 赞/ 147 阅读

相关 PAT甲级 - 1003 Emergency （25 分）

题目链接：[（PAT甲级）1003 Emergency （25 分）][PAT_1003 Emergency _25] As an emergency rescue team

太过爱你忘了你带给我的痛/ 2022年03月19日 16:26/ 0 赞/ 268 阅读

相关 (PAT 1145) Hashing - Average Search Time (哈希表冲突处理)

The task of this problem is simple: insert a sequence of distinct positive integers into

曾经终败给现在/ 2022年03月18日 06:43/ 0 赞/ 212 阅读

相关 PAT甲级 - 1010 Radix （25 分）

题目链接：[PAT甲级 - 1010 Radix （25 分）][PAT_ - 1010 Radix _25] Given a pair of positive intege

╰半橙微兮°/ 2022年03月18日 04:48/ 0 赞/ 282 阅读

相关 1145 Hashing - Average Search Time (25 分) 建立Hash表并输出平均查询次数

The task of this problem is simple: insert a sequence of distinct positive integers into

红太狼/ 2021年10月30日 07:58/ 0 赞/ 312 阅读