hash线性探测开放定址法解决冲突

阳光穿透心脏的1/2处 2022-06-02 02:05 310阅读 0赞

一，利用线性探测法构造散列表(用除余法来得出散列地址，用开放地址法解决同义词问题)  题目：已知一组关键字为(26，36，41，38，44，15，68，12，06，51)，用除余法构造散列函数，用线性探查法解决冲突构造这组关键字的散列表。

解答:为了减少冲突，通常令装填因子α

由除余法的散列函数计算出的上述关键字序列的散列地址为(0，10，2，12，5，2，3，12，6，12)。

前5个关键字插入时，其相应的地址均为开放地址，故将它们直接插入T\[0\]，T\[10)，T\[2\]，T\[12\]和T\[5\]中。 当插入第6个关键字15时，其散列地址2(即h(15)=15％13=2)已被关键字41(15和41互为同义词)占用。故探查h1=(2+1)％13=3，此地址开放，所以将15放入T\[3\]中。 当插入第7个关键字68时，其散列地址3已被非同义词15先占用，故将其插入到T\[4\]中。  当插入第8个关键字12时，散列地址12已被同义词38占用，故探查hl=(12+1)％13=0，而T\[0\]亦被26占用，再探查h2=(12+2)％13=1，此地址开放，可将12插入其中。

类似地，第9个关键字06直接插入T\[6\]中；而最后一个关键字51插人时，因探查的地址12，0，1，…，6均非空，故51插入T\[7\]中。

二、题目：

已知一个线性表(38，25，74，63，52，48)，假定采用h(k)=k%6计算散列地址进行散列存储，若用线性探测的开放定址法处理冲突，则在该散列表上进行查找的平均查找长度为（）。

A. 1.5 B. 1.7 C. 2 D. 2.3 2、

解题过程：

(1)计算h(k)： 38%6 = 2 25%6 = 1 74%6 = 2 63%6 = 3 52%6 = 4 48%6 = 0

(2)定址：  把不冲突的和冲突的全部列出来即可 地址： 0 1 2 3 4 5

1、线性表第1个元素（38）： 38（第1 次不冲突）

2、线性表第2个元素（25）： 25（第1次不冲突）

3、线性表第3个元素（74）： 74（第1 次冲突，地址 + 1）

4、线性表第3个元素（74）： 74（第2 次不冲突）

5、线性表第4个元素（63）： 63（第1 次冲突，地址 + 1）

6、线性表第4个元素（63）： 63（第2 次不冲突）

7、线性表第5个元素（52）： 52（第1 次冲突，地址 + 1）

8、线性表第5个元素（52）： 52（第2 次不冲突）

9、线性表第6个元素（48）： 48（第1次不冲突）

经过上述定址过程，线性表中的各个元素都有了唯一的地址。

2.3、结果 线性表中的 6 个元素，经过9次定址， 在该散列表上进行查找的平均查找长度为：9/6 = 1.5, 答案选：A

三、哈希表查找不成功怎么计算？

解答：先建好表，然后可以算出每个位置不成功时的比较次数之和，再除以表空间个数！

例如：散列函数为hash(x)=x MOD 13，用线性探测，建立了哈希表之后，如何求查找不成功时的平均查找长度！？

地址： 0 1 2 3 4 5 6 7 8 9 10 11 12

数据： 39 12 28 15 42 44 6 25 － － 36 － 38

成功次数： 1 3 1 2 2 1 1 9 1 1

不成功次数： 9 8 7 6 5 4 3 2 1 1 2 1 10

查找成功时的平均查找长度:ASL=(1+3+1+2+2+1+1+9+1+1)/10 =2.2

查找不成功时的平均查找长度:ASL=(9+8+7+6+5+4+3+2+1+1+2+1+10)/13=4.54

发表评论取消回复

表情：

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

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

相关阅读

相关 java基础：开放定址法解决哈希冲突代码示例

代码示例开放定址法是另一种常用的解决哈希冲突的方法，它通过在哈希表中的其他空槽中寻找可用位置来插入具有相同哈希码的元素。具体的位置选择规则可以有多种方式，包括线性探测、

分手后的思念是犯贱/ 2024年02月20日 11:51/ 0 赞/ 49 阅读

相关 java开放地址法和链地址法解决hash冲突

hashMap对各位小伙们来说，没有不知道的了，使用过的人想必或多或少的都了解一点hashMap的底层实现原理，总结来说就是，数组+链表，至于源码的实现，大家可参看源码，今天想

- 日理万妓/ 2023年10月18日 14:10/ 0 赞/ 122 阅读

相关 hash地址冲突与开放地址法

![format_png][] 慧能 ![format_png 1][] 一尘，国庆节过完了，还记得Hash函数吗？当然记得了，Hash函数就是将任意长度的输入转化成

小咪咪/ 2023年07月07日 05:53/ 0 赞/ 21 阅读

相关开放定址Hash法

开放定址Hash法 void get\_hash(int k, int d)\{ while(v\[k\]) k = (k + 1)%PRIME; hash\[k\] = d

╰半夏微凉°/ 2022年08月21日 02:19/ 0 赞/ 178 阅读

相关【除留余数法定义hash函数+线性探测法解决hash冲突】数据结构实验之查找七：线性之哈希表

Think: 1知识点：除留余数法定义hash函数+线性探测法解决hash冲突数据结构实验之查找七：线性之哈希表 Time Limit: 1000MS Memory

川长思鸟来/ 2022年06月03日 03:41/ 0 赞/ 236 阅读

相关 hash线性探测开放定址法解决冲突

一，利用线性探测法构造散列表(用除余法来得出散列地址，用开放地址法解决同义词问题) 题目：已知一组关键字为(26，36，41，38，44，15，68，12，06，51)，用除

阳光穿透心脏的1/2处/ 2022年06月02日 02:05/ 0 赞/ 311 阅读

相关散列函数线性探测法处理冲突

散列函数线性探测法处理冲突: ![这里写图片描述][70] include <iostream> using namespace std; typ

迈不过友情╰/ 2022年05月21日 12:23/ 0 赞/ 188 阅读

相关 hash解决冲突之---平方探测

数据结构实验之查找五：平方之哈希表 Time Limit: 400ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述给定的一组无重复

雨点打透心脏的1/2处/ 2022年05月16日 00:46/ 0 赞/ 465 阅读

相关 java 解决Hash(散列)冲突的四种方法--开放定址法(线性探测,二次探测,伪随机探测)、链地址法、再哈希、建立公共溢出区

一）哈希表简介非哈希表的特点：关键字在表中的位置和它之间不存在一个确定的关系，查找的过程为给定值一次和各个关键字进行比较，查找的效率取决于和给定值进行比较的次数。

女爷i/ 2021年12月12日 14:33/ 0 赞/ 354 阅读

相关 C++数据结构--.哈希表线性探测开放寻址法与独立表链地址法

1.哈希函数是个定位函数，它用键作为参数，返回表中的索引值 ![20130805133825875][] 2.线性探测开放寻址法 \调用哈希函数处理键得

电玩女神/ 2021年11月17日 02:38/ 0 赞/ 358 阅读