给定一组查找关键字(19,14,23,1,65,20,84,27,55,11,10,79) 哈希函数为：H(key)=key % 13, 哈希表长为m=15，设每个记录的查找概率相等。

短命女 2023-02-14 01:30 111阅读 0赞

给定一组查找关键字(19,14,23,1,65,20,84,27,55,11,10,79)

  1. 题目要求

哈希函数为：H(key)=key % 13, 哈希表长为m=15，设每个记录的查找概率相等。

  1. 请画出按照线性探测再散列处理冲突得到的哈希表（给出求解过程），并计算查找成功和查找失败时的平均查找长度各是多少。
  2. 请画出按照链地址法处理冲突得到的哈希表，并计算查找成功和查找失败时的平均查找长度各是多少。

  1. 解题思路

2.1 线性探测

  1. 哈希表长为m=15；
  2. 分别得到的结果进行线性探测散列排列：

在这里插入图片描述
冲突的关键字按照关键字的原始排序进行向后的推移
图中的冲突的关键字“1”他的现地址为1，但这个位置上已经被关键字“14”所占领，遇到了冲突，探测下一个位置2，位置2上没有关键字，放入即可；
在这里插入图片描述
关键字“84”在原始的关键字中排列在前，他现在的地址为6，但这个位置已经被关键字“19”占领，遇到了冲突，探测下一个地址7，但这个位置上也已经被关键字“20”占领，继续探测下一个地址8，位置8上没有关键字，放入即可；
在这里插入图片描述
在这里插入图片描述在这里插入图片描述在这里插入图片描述
循环执行，到了这一步所有的关键字都已经填入哈希表，散列表的构造已经完成
在这里插入图片描述
注：散列表的比较次数与关键字在哈希表中插入位置的次数有关，
查找成功的平均查找长度为：
ASL=（1+1+2+1+3+4+1+1+2+1+1+2）/12
在这里插入图片描述
查找不成功的平均查找长度为：
ASL=（10+9+8+7+6+5+4+3+2+1+2+3+4）/13

注意：
区别概念平均成功查找次数和平均不成功查找次数。
平均成功查找次数=每个关键词比较次数之和÷关键词的个数
平均不成功查找次数=每个位置不成功时的比较次数之和÷表长（所谓每个位置不成功时的比较次数就是在除余位置内，每个位置到第一个为空的比较次数。

2.2链式地址法：

在这里插入图片描述
成功时平均查找次数：（1X5+2X4+3X1+4X1）/12=5/3
失败时平均查找次数：（4+2+2+1+2+1）/11 =1

注意：链地址法成功时查找次数的分母是哈希表元素的个数，分子为纵向比较；
失败时，分母为哈希表的长度，分子为横向比较（几个）；

发表评论

表情：
评论列表 （有 0 条评论，111人围观）

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

相关阅读

    相关 哈希查找

    哈希查找是一种通过设计所存储数据元素 与其存放地址之间的映射关系（函数关系）来实现高效查找的方法。比如我需要查询一个数460，那么根据先前存储时所采取的映射关系就可以准确地得到

    左手的ㄟ右手左手的ㄟ右手/ 0 赞/ 27 阅读

    相关 详解哈希表查找

    哈希表查找 定义 基本概念 实现方法 1、定义 > 哈希表查找又叫散列表查找，通过查找关键字不需要比较就可以获得需要记录的存储位置，它是通过在记

    柔情只为你懂柔情只为你懂/ 0 赞/ 323 阅读

    相关 哈希表的查找

    引入哈希表 前面查找方法共同特点：通过将关键字值与给定值比较，来确定位置。效率取决比较次数。 理想的方法是：不需要比较，根据给定值能直接定位记录的存储位置。 这样，

    淡淡的烟草味﹌淡淡的烟草味﹌/ 0 赞/ 386 阅读