-
2018-08-11 22:24:55
将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组。散列函数为: H(key) = (key*3) MOD 7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。
(1) 请画出所构造的散列表;
(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。一、查找成功平均长度
- 通过公式计算出存放的位置,如果该位置已经有数字了,往后找到一个空的放下。
- 存放示意图
存放位置 0 1 2 3 4 5 6 7 8 9 存放数字 7 14 8 11 30 18 9 - 查找时候,一次找到的查找长度为1,否则多移动一格查找长度加一。如下表
存放位置 0 1 2 3 4 5 6 7 8 9 存放数字 7 14 8 11 30 18 9 查找长度 1 2 1 1 1 3 3 - 由此可得查找成功的平均查找长度为:(1+1+1+1+3+3+2)/7 = 12/7
二、查找不成功平均长度
存放位置 0 1 2 3 4 5 6 7 8 9 存放数字 7 14 8 11 30 18 9 接下来讨论不成功的情况,由上表,计算查找不成功的次数就直接找关键字到第一个地址上关键字为空的距离即可, 但根据哈希函数地址为MOD7,因此初始只可能在0~6的位置。等概率情况下,查找0~6位置查找失败的查找次数为:
看地址0,到第一个关键字为空的地址2的距离为3,因此查找不成功的次数为3.
地址1, 到第一个关键为空的地址2的距离为2,因此查找不成功的次数为2.
地址2, 到第一个关键为空的地址2的距离为1,因此查找不成功的次数为1.
地址3,到第一个关键为空的地址4的距离为2,因此查找不成功的次数为2.
地址4,到第一个关键为空的地址4的距离为1,因此查找不成功的次数为1.
地址5,到第一个关键为空的地址2(注意不是地址9,因为初始只可能在0~6之间(因为只有7个数),因此循环回去)的距离为5,因此查找不成功的次数为5.
地址6,到第一个关键为空的地址2(注意不是地址9,因为初始只可能在0~6之间,因此循环回去)的距离为4,因此查找不成功的次数为4.
因此查找不成功的次数表如下表所示
存放位置 0 1 2 3 4 5 6 7 8 9 存放数字 7 14 8 11 30 18 9 查找不成功长度 3 2 1 2 1 5 4 - 所以查找不成功平均长度:(3+2+1+2+1+5+4)/ 7 = 18/7。
更多相关内容 -
哈希表平均查找长度
2021-12-26 18:48:41(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。 一、查找成功平均长度 通过公式计算出存放的位置,如果该位置已经有数字了,往后找到一个空的放下。 存放示意图 存放位置0123456789存放数字714&...将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组。散列函数为: H(key) = (key*3) MOD 7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。
(1) 请画出所构造的散列表;
(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。一、查找成功平均长度
- 通过公式计算出存放的位置,如果该位置已经有数字了,往后找到一个空的放下。
- 存放示意图
存放位置 0 1 2 3 4 5 6 7 8 9 存放数字 7 14 8 11 30 18 9 - 查找时候,一次找到的查找长度为1,否则多移动一格查找长度加一。如下表
存放位置 0 1 2 3 4 5 6 7 8 9 存放数字 7 14 8 11 30 18 9 查找长度 1 2 1 1 1 3 3 - 由此可得查找成功的平均查找长度为:(1+1+1+1+3+3+2)/7 = 12/7
二、查找不成功平均长度
存放位置 0 1 2 3 4 5 6 7 8 9 存放数字 7 14 8 11 30 18 9 接下来讨论不成功的情况,由上表,计算查找不成功的次数就直接找关键字到第一个地址上关键字为空的距离即可, 但根据哈希函数地址为MOD7,因此初始只可能在06的位置。等概率情况下,查找06位置查找失败的查找次数为:
看地址0,到第一个关键字为空的地址2的距离为3,因此查找不成功的次数为3.
地址1, 到第一个关键为空的地址2的距离为2,因此查找不成功的次数为2.
地址2, 到第一个关键为空的地址2的距离为1,因此查找不成功的次数为1.
地址3,到第一个关键为空的地址4的距离为2,因此查找不成功的次数为2.
地址4,到第一个关键为空的地址4的距离为1,因此查找不成功的次数为1.
地址5,到第一个关键为空的地址2(注意不是地址9,因为初始只可能在0~6之间(因为只有7个数),因此循环回去)的距离为5,因此查找不成功的次数为5.
地址6,到第一个关键为空的地址2(注意不是地址9,因为初始只可能在0~6之间,因此循环回去)的距离为4,因此查找不成功的次数为4.
因此查找不成功的次数表如下表所示
存放位置 0 1 2 3 4 5 6 7 8 9 存放数字 7 14 8 11 30 18 9 查找不成功长度 3 2 1 2 1 5 4 - 所以查找不成功平均长度:(3+2+1+2+1+5+4)/ 7 = 18/7。
个人总结的有关考研数据结构中平均查找长度ASL的三种计算小技巧:
-
顺序查找法的平均查找长度为:(n+1)/2
-
散列表的查找成功和查找不成功的平均查找长度
技巧(线性探测法和链地址法):
① 查找成功时的比较次数是基于关键字计算的;查找不成功时的比较次数是基于Hash函数计算得到的地址计算的。
②查找成功的计算只有一种情况;查找不成功的计算有两种情况,关键是看题目中是否含有(只将与关键字的比较计算在内)
若没有,查找过程中遇到空位置,则证明查找失败;若有,则查找过程中只需比较关键字即可。注意:①查找成功是除关键字的个数;②查找不成功是除mod后的数值
-
折半查找成功和查找不成功的平均查找长度:
以折半查找的方式,将逐个查找出来的数值建立判定树,根据判定树求查找成功和查找不成功的平均查找长度。
注意:①查找成功是除关键字个数;②查找不成功是除关键字个数加1
个人的理解就是这样,希望能够帮到部分同在考研的研友们!
线性探测再散列
例如 哈希函数为: H(key) = key %13,key 为关键字,采用开放地址法中的线性探测再散列解决冲突,依次输入
11 个关键字,16,74,60,43,54,90,46,31,29,88,77,构造哈希表
如图,例如 16%13=3,将16放入3号位置,29%13 = 3,将29放入3号位置,而此时3号位已经有元素。
就顺着表往后放,直到6号没有元素,29放入6号。
二次探测再散列
例如 哈希函数为: H(key) = key %13,key 为关键字,采用开放地址法中的二次探测再散列解决冲突,依次输入
10 个关键字,36,21,45,17,29,55,35,61,40,78,构造哈希表
对于29%13=3,将29放入3号位置, 55%13=3,此时3号位置已经有元素,
则查找 3 + 1^2 = 4,有元素
查找 3 - 1^2 = 2 ,没有则放入,如果还有元素则查找3 + 2^2, 3-2^2… 3+k^2, 3 - k^2。
ASL(Average Search Length),即平均查找长度,在查找运算中,由于所费时间在关键字的比较上,所以把平均需要和待查找值比较的关键字次数称为平均查找长度。
它的定义是这样的:
其中n为查找表中元素个数,Pi为查找第i个元素的概率,通常假设每个元素查找概率相同,Pi=1/n,Ci是找到第i个元素的比较次数。
当然,有查找成功,就有查找不成功,即要查找元素不在查找表中。针对不同查找方式的查找成功与不成功,我接下来会说,这也是一我一开始有点乱的地方。
一个算法的ASL越大,说明时间性能差,反之,时间性能好,这也是显而易见的。
- 在_顺序查找(Sequence Search)_表中,查找方式为从头扫到尾,找到待查找元素即查找成功,若到尾部没有找到,说明查找失败。所以说,Ci(第i个元素的比较次数)在于这个元素在查找表中的位置,如第0号元素就需要比较一次,第一号元素比较2次…第n号元素要比较n+1次。所以Ci=i;所以
可以看出,顺序查找方法查找成功的平均 比较次数约为表长的一半。**当待查找元素不在查找表中时,也就是扫描整个表都没有找到,即比较了n次,查找失败**
-
折半查找(Binary Search),首先待查找表是有序表,这是折半查找的要求。在折半查找中,用二叉树描述查找过程,查找区间中间位置作为根,左子表为左子树,右子表为右子树,,因为这颗树也被成为判定树(decision tree)或比较树(Comparison tree)。查找方式为(找k),先与树根结点进行比较,若k小于根,则转向左子树继续比较,若k大于根,则转向右子树,递归进行上述过程,直到查找成功或查找失败。在n个元素的折半查找判定树中,由于关键字序列是用树构建的,所以查找路径实际为树中从根节点到被查结点的一条路径,因为比较次数刚好为该元素在树中的层数。所以
Pi为查找k的概率,level(Ki)为k对应内部结点的层次。而在这样的判定树中,会有n+!种查找失败的情况,因为将判定树构建为完全二叉树,又有n+1个外部结点(用Ei(0<=i<=n)表示),查找失败,即为从根结点到某个外部结点也没有找到,比较次数为该内部结点的结点数个数之和,所以
,qi表示查找属于Ei中关键字的概率,level(Ui)表示Ei对应外部结点的层次。所以,在一颗有n个结点判定树中,总数
,所以判定树高度为
的满二叉树,第i层上结点个数为
,查找该层上的结点需要进行i次比较,因此,在等概率情况下ASL为
看个例子会更好理解。
-
例:给11个数据元素有序表(2,3,10,15,20,25,28,29,30,35,40)采用折半查找。则ASL成功和不成功分别是多少?
-
首先画出判定树,
-
查找成功时总会找到途中某个内部结点,所以成功时的平均查找长度为
即25查找一次,成功,10,30要查找2次,成功,2,15,28,35要查找3次,成功,3,20,29,40要查找4次,成功。 而不成功的平均查找长度为
,为什么这么算呢,因为内部结点都能查找成功,而查找不成功的就是那些空的外部结点,所以到查询到2的左孩子,15的左孩子,28的左孩子,35的左孩子,3的左右孩子,20的左右孩子,29的左右孩子,40的左右孩子时,都是查找不成功的时候。如我要找1,比25小,转向左子树,比较一次,比10小,转左子树,2次,比2 小,转左子树,3次,此时2无左子树,所以失败。所以
。
-
哈希表中的ASL 查找成功的平均查找长度是指查找到哈希表中已有关键字的平均探测次数。而查找不成功的平均查找长度是指在哈希表中找不到待查的元素,最后找到空位置元素的探测次数平均值。
-
例:散列表长度为13,地址空间为0~12,散列函数H(k) =K mod 13,关键字序列{19,14,23,01,68,20,84,27,55,11,10,79} 所以线性探测结果为:
-
各位可以手动算一下,加深理解~
根据探测次数,
当然成功的很好理解,12个元素,每个元素的探测次数之和除以12就行。而不成功的计算是这样的。散列表长度为13,根据定义,假设待查关键字不在散列表中,要一直找到空元素才算查找失败。
如H[0]为空,与待查找元素不等,不成功,比较一次,H[1],此时H[1]的元素与原本放在H[1]的元素不等**(假设不在散列表在之中,但也不是空的**),继续向后比,与H[2]比也不等,继续向后,一直到H[12],也不等,继续向后时,回到H[0],为空,也不等,查找失败,总计比较13次,然后计算第二号元素,一样的比较,一直把每个位置都统计一遍,从而得出ASL不成功的.
-
探究如何计算哈希表查找成功、失败时的平均查找长度(附实例)
2021-06-06 18:57:27对于查找成功时的平均查找长度,书上有明确的定义: 而题目设定条件都是在等概率下查找,所以ASL=(C0+C1+...+Cn)*1/n. 这就说明了查找成功是针对关键字查找的,最后除以关键字的总个数。 我们来看一道书上的例题...对于查找成功时的平均查找长度,书上有明确的定义:
而题目设定条件都是在等概率下查找,所以ASL=(C0+C1+...+Cn)*1/n.
这就说明了查找成功是针对关键字查找的,最后除以关键字的总个数。
我们来看一道书上的例题:
构建出来的哈希表有八个元素,针对这八个元素的比较次数,得出ASLsuccess=(1+1+1+2+1+2+1+2)/8=11/8.而查找失败时的平均查找长度,却是针对位置的查找。
为什么呢,因为如果我们要查找表中的元素,那么一定可以找到,所以讨论查找失败就没有意义。我们讨论查找失败,一定是针对表中没有的元素在这张表中查找,才有查找失败的意义。所以,针对上图的哈希表,我们将待查找关键字X代入哈希函数,我们设定X与这张表中的关键字都不相同:
当H(X)=3X mod 11=0时,因为散列地址为0的位置没有关键字,所以查找1次就失败了;
当H(X)=3X mod 11=1时,因为散列地址为1的位置有关键字4,X与4不等,所以按照线性探测法向后探测1,散列地址为2的位置没有关键字,所以查找失败,一共查找了2次;
当H(X)=3X mod 11=2时,同0;
当H(X)=3X mod 11=3时,因为散列地址为3的位置有关键字12,X与12不等,所以向后线性探测,散列地址为4的位置有关键字49,还不等,继续探测,因为X与表中的关键字都不等,所以直到散列地址为10没有关键字,才查找失败,这次一共查找了8次;
…以此类推综上所述,我们可以得出结论:
失败查找次数就是该位置向后探测到第一个没有关键字的地址位置之间的距离
而求平均数的除数,是模的大小
因为失败查找次数是针对位置查找,因为模为11,所以查找的位置(哈希函数的值)为0-10(共11个),针对这11个位置进行查找,而与表的长度无关。
理清了思路,我们来看看链地址法表示的哈希表:
成功时的平均查找长度很好求,针对表中的每个关键字:有五个关键字找一次:4,12,49,13,32;三个关键字找两次:38,24,21.失败时的平均查找长度针对位置来查找:
等于0时,只有空指针域,查找1次;
等于1时,带一个结点,所以查找2次找到空指针;
…
等于4时,带两个节点,所以查找3次找到空指针;
…
综上所述,我们可以总结:失败查找次数就是当前位置所带的结点个数+1
使用链地址法查找时无二次聚集现象(二次聚集:处理冲突过程中发生的两个第一个散列地址不同的记录争夺同一个后继散列地址的现象)
除数也是模的大小
你学会了吗?
-
面试常见考题:哈希表平均查找长度
2019-06-30 12:18:17哈希表(又名为是散列表) 散列是一个用于唯一标识对象并在一些预先计算的唯一索引(称为“密钥”)存储每个对象的过程。因此,对象以“键值”对的形式存储,这些项的集合被称为“字典”。可以使用该键值搜索每个...哈希表(又名为是散列表)
散列是一个用于唯一标识对象并在一些预先计算的唯一索引(称为“密钥”)存储每个对象的过程。因此,对象以“键值”对的形式存储,这些项的集合被称为“字典”。可以使用该键值搜索每个对象。有多种不同的基于哈希的数据结构,但最常用的数据结构是哈希表。哈希表通常使用数组实现。
哈希数据结构的性能取决于以下三个因素:
哈希函数
哈希表的大小
碰撞处理方法
下图展示了如何在数组中映射哈希。该数组的索引是通过哈希函数计算的。
今天主要讲一下哈希表平均查找长度ASL计算,也是常见面试题之一
题目:关键字序列为:{30,25,80,63,52,48},哈希函数为H(k)=k%7,哈希表的长度为7,用线性探测和链地址法处理冲突,分别计算等概率情况下查找成功的平均查找长度。注:没给哈希表长度,给出装填因子时,可求哈希表长度,
可根据此公式装填因子=元素个数/表长推:表长=元素个数/装填因子。线性探测法(通过数组保存)
H(30)=30%7=2
H(25)=25%7=4
H(80)=80%7=3,和30冲突,往后移一位:4,又与25冲突,继续后移一位:5
H(63)=63%7=0
H(52)=52%7=3,后移三位为6
H(48)=48%7=6,与52冲突,后移一位为0,再后移一位为1
结果为:
30 ——2
25——4
80——5
63——7
52——6
48——1
平均查找长度:查找次数和/数组个数
(1+1+3+1+4+3)/6=2.2链地址法 (以链表形式存储)
取模后值相同的在同一个链表中,即
0——63
1
2
3——30——80——52
4——25
5
6——48
等概率下查找成功的平均查找长度为:
ASL=(14+21+3*1)/6=1.5 -
哈希表等查找成功和查找不成功的平均查找长度(线性探测法+链地址法)
2022-03-05 20:50:33最近刷面试题遇到哈希表求平均查找长度的题,已经忘了,来记录下 Question1: 将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组,散列函数为:  ... -
待填入哈希表的人名共有30个,取平均查找长度的上限为2。哈希函数采用除留余数法构造,用线性探测再散列法...
2020-06-27 13:46:341)设计几个不同的哈希函数,比较他们的地址冲突率(可以用更大的名字集合做实验)。...(3)在哈希函数确定的前提下尝试各种不同处理冲突的方法,考察平均查找长度的变化和造好的哈希表中关键字的聚集性。 -
题目4:通讯录的制作 设计任务: 针对你所在班集体中的“人名”,设计一个哈希表,使得平均查找长度不超过R...
2020-01-07 14:05:37针对你所在班集体中的“人名”,设计一个哈希表,使得平均查找长度不超过R,完成相应的建表和查找过程。 设计要求: 1.每个人的信息至少包括姓名,电话,地址。至少包括对通讯录的创建,添加和按姓名查找等功能。 ... -
如何计算哈希表查找失败时的平均查找长度
2020-04-30 18:20:011.请回答采用线性探测再散列和链地址法处理冲突构建的哈希表中,查找失败时的平均查找长度如何计算? 例:已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为:H(key)=keyMOD13,哈希表长为m=15,设每个记录... -
哈希表查找——等概率情况下查找成功和查找不成功的平均查找长度的计算
2020-11-28 21:49:49最近复习数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时不太理解,不知道到底是怎么计算出来的。看了几篇博客后终于知道如何计算了,总结如下。 例题: 将关键字序列(7、8、30、11、... -
Hash表平均查找长度ASL计算
2019-04-09 21:06:30ASL 指的是平均查找时间 关键字序列:(7、8、30、11、18、9、14) 散列函数: H(Key) = (key x 3) MOD 7 装载因子: 0.7 处理冲突: 线性探测再散列法 查找成功的 ASL 计算方法: 因为现在的数据是 7 个,填充因子... -
创建哈希表、查找及计算平均查找长度
2018-07-08 10:11:58#include<stdio.h> #include<malloc.h> #include<stdlib.h> typedef struct //元素类型定义 ...typedef struct //哈希表类型定义 { DataType *data; int l... -
【hash表】hash表平均查找长度(ASL)
2019-08-28 14:00:41hash 表在处理 collision 的时候有... 本文记录使用开链法的情况下,Hash 表查找成功和查找不成功的平均查找长度(ASL - ),其他方法同理。 首先开链法是指,每一个表格元素维护一个list,hash function... -
C语言:哈希表的建立,查找,计算查找成功与不成功的平均查找长度
2019-03-30 17:28:14关于什么是哈希表,定义网上太多了,大家可以自行搜索,本文主要讲代码的实现 由于网上大部分是采用链地址法处理冲突,所以刚开使代码总卡着没法运行 在与哈希表的初始化 初始化方法可以自行选择,不初始化,没法... -
C语言设计哈希表实现图书查找
2020-10-26 20:19:01C语言设计哈希表实现图书查找系统,完成相应的建表和查表程序。...3) 分别采用线性法、随机法、溢出法解决冲突,比较不同方法的冲突率,计算不同方法的平均查找长度。 4) 查找并显示给定图书编码的记录。 -
哈希表查找不成功时的平均查找长度计算和查找成功时的ASL
2020-02-01 09:11:27哈希表查找不成功时的平均查找长度计算和查找成功时的ASL 例如: 关键字集合 { 19, 01, 23, 14, 55, 68, 11, 82, 36 } 设定哈希函数 H(key) = key MOD 11 ( 表长=11 ) 查找成功次数: 1 1 2 1 3 6 2 5 1 ... -
哈希表平均查找长度问题
2017-05-22 05:00:39哈希表的平均查找长度可以为0吗,老师上课说可以,说是不用比较,但我感觉至少也要1啊 -
哈希表查找——成功和不成功时的平均查找长度
2018-08-12 10:27:22哈希表查找——成功和不成功时的平均查找长度 以下求解过程是按照“计算机统考的计算方法”,不同的老师、教材在“处理冲突”上可能会有不同的方法,所以最主要的是掌握原理即可,对于考研的朋友最好掌握统考... -
C语言实现构造哈希表,计算等概率的情况查找成功与不成功的平均查找长度
2020-04-23 19:15:46编程实现:构造哈希表:在地址空间为0~12,对以下关键字序列:(Jan,Feb,Apr,May,Jun,Jul,Aug,Sep,Oct)建哈希表,并且求出等概率情况下查找成功与不成功的平均查找长度。 实现代码: typedef struct HashTable{ ... -
哈希表 计算失败平均查找长度
2016-02-09 15:31:12 这个失败的长度是怎么计算出来的? 分子是怎么来的? 请大家具体讲讲~ -
哈希表查找不成功平均长度例子
2020-04-30 16:08:40等概率情况下查找不成功的平均查找长度: 接下来讨论不成功的情况, 看表2,计算查找不成功的次数就直接找关键字到第一个地址上关键字为空的距离即可, 但根据哈希函数地址为MOD7,因此初始只可能在06的位置。等概率... -
哈希表应用 设计哈希表实现图书查找系统,完成相应的建表和查表程序。c语言课设
2022-01-02 12:51:24哈希表应用 设计哈希表实现图书查找系统,完成相应的建表和查表程序。...(3)分别采用线性法、随机法、溢出法解决冲突,比较不同方法的冲突率,计算不同方法的平均查找长度。 (4)查找并显示给定图书编码的记录。 -
关于ASL(平均查找长度)的简单总结
2021-05-23 09:12:15ASL(Average Search Length),即平均查找长度,在查找运算中,由于所费时间在关键字的比较上,所以把平均需要和待查找值比较的关键字次数成为平均查找长度。它的定义是这样的:其中n为查找表中元素个数,Pi为查找第i... -
Hash表的平均查找长度ASL计算方法
2019-07-11 10:13:24ASL指的是 平均查找时间 关键字序列:(7、8、30、11、18、9、14) 散列函数: H(Key) = (key x 3) MOD 7 装载因子(用来计算表长的): 0.7 处理冲突: 线性探测再散列法 查找成功的ASL计算方法: 因为现在的数据是... -
哈希表的设计与实现【课程设计
2021-07-20 17:01:32可以插入、查找、删除并显示给定用户名的记录,并计算查找长度, 哈希表保存到文件中,并能从文件中读取数据。 测试数据:取某个单位电话号码簿中的30个记录。 提高要求: (1)将电话号码薄以文件形式保存到盘上,... -
哈希表:线性探测法和链地址法求查找成功与不成功的平均查找长度
2020-07-03 00:24:32哈希表:线性探测法和链地址法求查找成功与不成功的平均查找 -
设计构造哈希表的完整算法,求出平均查找长度.doc
2021-10-07 19:50:01设计构造哈希表的完整算法,求出平均查找长度.doc -
【数据结构】哈希表——线性探测法、链地址法、查找成功、查找不成功的平均长度
2021-04-12 14:08:57它通过把关键码值映射到哈希表中的一个位置来访问记录,以加快查找的速度。这个映射函数就做散列函数,存放记录的数组叫做散列表。 2、散列存储的基本思路 以数据中每个元素的关键字K为自变量,通过散列函数H(k)...