-
哈希表平均查找长度
2017-08-13 10:53:31题目:关键字序列为:{38,25,74,63,52,48},哈希函数为H(k)=k%7,哈希表的长度为7,用线性探测和链地址法处理冲突,分别计算等概率情况下查找成功的平均查找长度。注:没给哈希表长度,给出装填因子时,可求哈希...题目:关键字序列为:{38,25,74,63,52,48},哈希函数为H(k)=k%7,哈希表的长度为7,用线性探测和链地址法处理冲突,分别计算等概率情况下查找成功的平均查找长度。
注:没给哈希表长度,给出装填因子时,可求哈希表长度,
可根据此公式装填因子=元素个数/表长推:表长=元素个数/装填因子。线性探测法
由上构造的哈希表如下:
等概率下查找成功的平均查找长度为:
ASL=(1+3+1+1+2+4)/6=2链地址法
由上构造的哈希表如下:
等概率下查找成功的平均查找长度为:
ASL=(1*4+2*2)/6=1.3 -
哈希表的平均查找长度
2017-08-03 15:34:17查找成功时的平均查找长度 查找不成功时的平均查找长度 http://www.doc88.com/p-903238204265.html查找成功时的平均查找长度
查找不成功时的平均查找长度
http://www.doc88.com/p-903238204265.html
-
哈希表查找 平均查找长度 解析
2012-05-03 15:23:12哈希表的装填因子 α 的定义如下: α = 哈希表中元素个数 / 哈希表的长度 ...手工计算等概率情况下查找 成功 的平均查找长度公式 规则如下: ASLsucc= 其中 Ci 为置入每哈希表的装填因子 α 的定义如下:
α = 哈希表中元素个数 / 哈希表的长度
α 可描述哈希表的装满程度。显然,α 越小,发生冲突的可能性越小,而 α 越大,发生冲突的可能性也越大。
手工计算等概率情况下查找 成功 的平均查找长度公式
规则如下:
ASLsucc=
其中 Ci 为置入每个元素时所需的比较次数
例如:已知一组关键字序列(19,14,23,01,68,20,84,27,55,11,10,79)按哈希函数H(key)=key % 13 和线性探测处理冲突构造所得哈希表ht[0..15],如图1所示比较次数:1 2 1 4 3 1 1 3 9 1 1 3
查找19时,通过计算H(19)= 6,ht[6].key非空且值为19查找成功,则查找关键字19 ,仅需要计算1次地址就可以找到;
查找14时,通过计算H(14)= 1,ht[1].key非空且值为14查找成功,则查找关键字19 ,仅需要计算1次地址就可以找到;
查找23时,通过计算H(23)=10,ht[10].key非空且值为23查找成功,则查找关键字23 ,仅需要计算1次地址就可以找到;
同样,查找关键字68,20,11,均需要计算一次地址就可以找到;
查找关键字01时,通过计算H(01)=1,ht[1].key非空且值为14≠01,则找第一次冲突处理后的地址H1=(1+1)% 13=2,此时,ht[2].key非空且值为01,查找成功因此查找关键字01时,需要计算2次地址才可以找到;
查找关键字55时,通过计算H(55)=3,ht[3].key非空且值为68≠55,则找第一次冲突处理后的地址H1=(3+1)% 13=4,此时,ht[4].key非空且值为27≠55,则找第二次冲突后处理地址H2=(3+2)% 13=5, ht[5].key非空且值为55查找成功,因此查找关键字27时,需要计算3次地址才能找到,同理,查找关键字10,84均需要计算3次地址才能找到;
查找关键字27时,通过计算H(27)=1,ht[1].key非空且值为14≠27,则找第一次冲突处理后的地址H1=(1+1)% 13=2,此时,ht[2].key非空且值为01≠27,则找第二次冲突后处理地址H2=(1+2)% 13=3, ht[3].key非空且值为68≠27,则找第三次冲突后处理地址H3=(1+3)% 13=4,ht[4].key非空且值为27,查找成功,因此查找关键字27时,需要计算4次地址才可以找到;
根据上面的方法,查找关键字79时,通过计算H(79)=1,ht[1].key非空且值为14≠79,则找第一次冲突处理后的地址H1=(1+1)% 13=2,此时,ht[2].key非空且值为01≠79,则找第二次冲突后处理地址H2=(1+2)% 13=3, ht[3].key非空且值为68≠79,则找第三次冲突后处理地址H3=(1+3)% 13=4,ht[4].key非空且值为27≠79,则找第四次冲突后处理地址H4=(1+4)% 13=5,ht[5].key非空且值为55≠79,则找第五次冲突后处理地址H5=(1+5)% 13=6,ht[6].key非空且值为19≠79则找第六次冲突后处理地址H6=(1+6)% 13=7,ht[7].key非空且值为20≠79,则找第七次冲突后处理地址H7=(1+7)% 13=8,ht[8].key非空且值为84≠79,则找第八次冲突后处理地址H8=(1+8)% 13=9,ht[9].key非空且值为79,查找成功,因此查找关键字79时,需要计算9次地址才可以找到。
据此计算公式,对如图8.27的哈希表,采用线性探测再散列法处理冲突, 计算出在等概率查找的情况下其查找成功的平均查找长度为:
ASL(12)=
=2.5
为便于计算, 在图8.27哈希表下方加注圆圈, 圆圈内表示的是有冲突时的计算次数, 如
代表需要一次地址计算就可找到的关键字有6个,依此类推,即可得到计算结果。
同理据此公式, 对采用链地址法处理冲突的哈希表例图8.26, 计算出在等概率情况下其查找成功的平均查找长度为:
ASL(12)succ=
手工计算在等概率情况下查找 不成功 的平均查找长度公式
查找不成功的情况:(1) 遇到空单元
(2) 按解决冲突的方法完全探测一遍后仍未找到。0 -> r-1 个不成功查找的入口,从每个入口进入后,直到确定查找不成功为止,其关键字的比较次数就是与该入口对应的不成功查找长度。
规则如下:
ASLunsucc=
其中Ci为函数取值为 i 时确定查找不成功时比较次数
据此计算公式,对如图8.27的哈希表,采用线性探测再散列法处理冲突, 计算出在等概率查找的情况下其查找不成功的平均查找长度为:
ASL(13)=
=6
同理据此公式,对采用链地址法处理冲突的哈希表例图8.26, 计算出在等概率情况下其查找不成功的平均查找长度为:
ASL(13)unsucc=
链地址法:
-
哈希表查找——成功和不成功时的平均查找长度
2017-09-17 13:27:21哈希表查找——成功和不成功时的平均查找长度 以下求解过程是按照“计算机统考的计算方法”,不同的老师、教材在“处理冲突”上可能会有不同的方法,所以最主要的是掌握原理即可,对于考研的朋友最好掌握统考...哈希表查找——成功和不成功时的平均查找长度
以下求解过程是按照“计算机统考的计算方法”,不同的老师、教材在“处理冲突”上可能会有不同的方法,所以最主要的是掌握原理即可,对于考研的朋友最好掌握统考真题的解题方法。
题目
例子:(2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题第一题)
将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组。散列函数为: H(key) = (keyx3) MOD 7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。 (1) 请画出所构造的散列表; (2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。
1.散列表:
α = 表中填入的记录数/哈希表长度 ==> 哈希表长度 = 7/0.7 = 10
H(7) = (7x3) MOD 7 = 0 H(8) = (8x3) MOD 7 = 3 H(30) = (30x3) MOD 7 = 6
H(11) = (11x3) MOD 7 = 5 H(18) = (18x3) MOD 7 = 5 H(9) = (9x3) MOD 7 = 6
H(14) = (14x3) MOD 7 = 0
按关键字序列顺序依次向哈希表中填入,发生冲突后按照“线性探测”探测到第一个空位置填入。
0 1 2 3 4 5 6 7 8 9 7 14 8 11 30 18 9 2.查找长度:
2.1 查找成功的平均查找长度
(待查找的数字肯定在散列表中才会查找成功)
查找数字A的长度 = 需要和散列表中的数比较的次数;
步骤: 比如 查找数字:8
则 H(8) = (8x3) MOD 7 = 3
哈希表中地址3处的数字为8,进行了第一次比较:8 = 8,则查找成功,查找长度为1;
比如查找数字:14
则 H(14) = (14x3) MOD 7 = 0
哈希表中地址0处的数字为7,进行第一次比较:7≠14
哈希表中地址1处的数字为14,进行第二次比较:14=14 ,则查找成功,查找长度为2。 由此可得到如下数据:【2016年12月26日修改,多谢@一楼的朋友指正】
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
2.2查找不成功的平均查找长度
(待查找的数字肯定不在散列表中)
【解题的关键之处】根据哈希函数地址为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(比较到地址6,再循环回去)需要比较5次,因此查找不成功的次数为5.
地址6,到第一个关键字为空的地址2(比较到地址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哈希表——线性探测法、链地址法、查找成功、查找不成功的平均长度
四、哈希表的装填因子
装填因子 = (哈希表中的记录数) / (哈希表的长度)
装填因子是哈希表装满程度的标记因子。值越大,填入表中的数据元素越多,产生冲突的可能性越大。
五、不同处理冲突的平均查找长度
例:
假设散列表的长度是13,三列函数为H(K) = k % 13,给定的关键字序列为{32, 14, 23, 01, 42, 20, 45, 27, 55, 24, 10, 53}。分别画出用线性探测法和拉链法解决冲突时构造的哈希表,并求出在等概率情况下,这两种方法的查找成功和查找不成功的平均查找长度。
(1)线性探测法:
查找成功时的查找次数等于插入元素时的比较次数,查找成功的平均查找长度为:ASL = (1+2+1+4+3+1+1+3+9+1+1+3)/12 = 2.5
查找成功时的查找次数:第n个位置不成功时的比较次数为:第n个位置到第1个没有数据位置的距离:如第0个位置取值为1,第11个位置取值为3,第12个位置取值2
查找不成功的平均查找次数为:
ASL = (1+13+12+11+10+9+8+7+6+5+4+3 + 2)/ 13 = 91/13
哈希表查找不成功怎么计算? 解答:先建好表,然后可以算出每个位置不成功时的比较次数之和,再除以表空间个数!
例如:散列函数为hash(x)=x MOD 11,用线性探测,建立了哈希表之后,如何求查找不成功时的平均查找长度!?
地址:0 1 2 3 4 5 6 7 8 9 10 数据:33 1 13 12 34 38 27 22 - - - 成功次数:1 1 1 3 4 1 2 8 不成功次数:9 8 7 6 5 4 3 2 1 1 1
查找成功时的平均查找长度:ASL=(1+1+1+3+4+1+2+8)/8 =47/8 查找不成功时的平均查找长度:ASL=(9+8+7+6+5+4+3+2+1+1+1)/11
说明:
第n个位置不成功时的比较次数为,第n个位置到第1个没有数据位置的距离。
如:第0个位置到第1个没有数据位置(8)的距离为9!
(1) 开放定址法地址: 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(2)链地址法
java中的hashMap就是这样一种链表+数组的数据结构,查找方法很简单,先利用散列函数(一般是取余数的方法)定位数组具体哪个点,比如1就是余数为1的点的链表中,然后再遍历链表查找具体数值的位置,如,果是53,那就在链表的第四位置,需要查找四次;同理,27就需要查找3次!
查找成功时的平均查找长度:
ASL = (1*6+2*4+3*1+4*1)/12 = 7/4
查找不成功时的平均查找长度:
ASL = (4+2+2+1+2+1)/13
注意:查找成功时,分母为哈希表元素个数,查找不成功时,分母为哈希表长度。
-
哈希表查找不成功平均长度例子
2020-04-30 16:08:40等概率情况下查找不成功的平均查找长度: 接下来讨论不成功的情况, 看表2,计算查找不成功的次数就直接找关键字到第一个地址上关键字为空的距离即可, 但根据哈希函数地址为MOD7,因此初始只可能在06的位置。等概率... -
哈希表查找不成功时的平均查找长度
2012-09-25 13:29:01哈希表查找不成功时的平均查找长度 哈希表查找不成功时的平均查找长度(zz)哈希表查找不成功怎么计算?解答:先建好表,然后可以算出每个位置不成功时的比较次数之和,再除以表空间个数! 例如:散列函数为hash(x)=... -
哈希表查找 的 平均长度
2018-08-11 22:24:55将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。...(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。 一、查找成功平均长度 通过公式计算出存放的位置,如果该位置已经... -
哈希表查找不成功的平均查找长度
2017-05-27 10:40:521.查找失败的情况:哈希表中不存在这个元素才会查找失败 2.查找失败的判定;见书 3.因为所查找的数是不确定的,因此可以取遍哈希函数的所有取值,而每一个取值相当于入口,从入口开始查找,当满足失败判定时,确认... -
哈希表查找不成功时的平均查找长度计算和查找成功时的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 ... -
哈希表(等概率情况下)查找成功与查找不成功的平均查找长度
2018-09-23 17:38:52继续小结,做到一道求 哈希表查找成功与查找不成功 情况下平均查找长度的计算问题,迷惑了好一会,在这里总结下来: 首先,你要明白的是平均查找长度求的是期望,那么你就按照求期望的方法来求平均查找长 -
哈希表查找——等概率情况下查找成功和查找不成功的平均查找长度的计算
2020-11-28 21:49:49最近复习数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时不太理解,不知道到底是怎么计算出来的。看了几篇博客后终于知道如何计算了,总结如下。 例题: 将关键字序列(7、8、30、11、... -
哈希表等概率情况下查找成功和查找不成功的平均查找长度的计算
2016-09-02 22:55:25哈希表等概率情况下查找成功和查找不成功的平均查找长度的计算 最近复习了下数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时比较迷茫,不知道到底是怎么计算出来的。现在通过查阅...
-
2021-03-04
-
详解事物以及事务的ACID
-
HTML5游戏_基于DOM平台跳跃小游戏开发_9.按键监听
-
基于SSM实现的房屋租赁系统【附源码】(毕设)
-
IET_LaTeX模板.zip
-
r7 5800h和i7 1165g7参数对比差距大不大
-
Docker学习四《使用容器》
-
多肽、instanceof
-
【STM32F429】第6章 ThreadX操作系统移植(IAR)
-
MusicRecorder:录制音乐作品的移动应用程序-源码
-
R数据分析:交叉滞后模型非专业解释
-
最新版linux redis-6.2.1.tar.gz
-
MySQL 索引
-
intro-component-with-signup-form-源码
-
Shell编程语言
-
时空压缩算法-动力节点
-
au-fhir-base:供澳大利亚使用的配置文件-源码
-
OnlineClass-源码
-
频出利好,ZT交易所ZTB最佳时间来了!
-
Oracle_11g_Linux到Linux_DataGuard部署