-
哈希表查找——等概率情况下查找成功和查找不成功的平均查找长度的计算
2020-11-28 21:49:49最近复习数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时不太理解,不知道到底是怎么计算出来的。看了几篇博客后终于知道如何计算了,总结如下。 例题: 将关键字序列(7、8、30、11、...最近复习数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时不太理解,不知道到底是怎么计算出来的。看了几篇博客后终于知道如何计算了,总结如下。
例题:
将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组,散列函数为: H(key) = (keyx3) MOD 7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。
(1)请画出所构造的散列表。
(2)分别计算等概率情况下查找成功和查找不成功的平均查找长度。
(1)首先明确一个概念:装载因子。装载因子是指所有关键子填充哈希表后饱和的程度,它等于 填入表中的关键字总数/哈希表的长度。
根据题意,我们可以确定哈希表的长度为 L = 7/0.7 = 10;因此此题需要构建的哈希表是下标为0~9的一维数组。
这里采用线性探测再散列法处理冲突,构造散列表。
H(7) = (7x3) MOD 7 = 0,地址为0,因此放到散列表的数组下表为0的位置,这个位置上没有关键字,因此没有冲突可以直接填入;
H(8) = (8x3) MOD 7 = 3,地址是3,因此放到散列表的数组下表为3的位置,这个位置上没有关键字,因此没有冲突可以直接填入;
H(30) = (30x3) MOD 7 = 6,地址是6,因此放到散列表的数组下表为6的位置,这个位置上没有关键字,因此没有冲突可以直接填入;
H(11) = (11x3) MOD 7 = 5,地址是5,因此放到散列表的数组下表为5的位置,这个位置上没有关键字,因此没有冲突可以直接填入;
H(18) = (18x3) MOD 7 = 5,地址是5,因此放到散列表的数组下表为5的位置,但这个位置上已经有关键字11,遇到了冲突,此时我们根据线性探测再散列法来处理这个冲突,探测下一个位置6,6这个位置上已经存在关键字30则继续增加1,因此现在的新地址应为7,位置7上没有关键字,放入即可,到此冲突已经解决;
H(9) = (9x3) MOD 7 = 6,地址是6,因此放到散列表的数组下表为6的位置,但这个位置上已经有关键字30,遇到了冲突,探测下一个位置7,7这个位置上已经存在关键字18则继续增加1,因此现在的新地址应为8,位置8上没有关键字,放入即可;
H(14) = (14x3) MOD 7 = 0,地址是0,因此放到散列表的数组下表为0的位置,但这个位置上已经有关键字7,遇到了冲突,探测下一个位置1,位置1上没有关键字,放入即可;
到这一步所有关键字均已填入,散列表已经构造完成,如下表所示。
地址 0 1 2 3 4 5 6 7 8 9 关键字 7 14 8 11 30 18 9 (2)等概率情况下查找成功平均查找长度:
这一问可以根据第一问的构造过程求解:
key7 一次就填入了表中,因此查找次数为1,同理8, 30, 11查找次数均为1;
key18 进行了三次探测操作,探测位置分别是5,6,7 ,因此查找次数为3;
key9 也是三次;
key14 进行了两次探测,因此查找次数为2。次数如下表所示:
地址 0 1 2 3 4 5 6 7 8 9 关键字 7 14 8 11 30 18 9 成功次数 1 2 1 1 1 3 3 所以ASLsuccess= (1+2+1+1+1+3+3)/ 7 = 12/7。
接下来讨论不成功的情况,计算查找不成功的次数就直接找关键字到下一个地址关键字为空的距离即可,但根据散列函数地址为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,到第三个关键字为空的地址9的距离为5,因此查找不成功的次数为5;
地址6,到第三个关键字为空的地址9的距离为4,因此查找不成功的次数为4;
注意地址7、8、9不用看。
因此查找不成功的次数表如下表所示:
地址 0 1 2 3 4 5 6 7 8 9 关键字 7 14 8 11 30 18 9 失败次数 3 2 1 2 1 5 4
所以ASLunsuccess= (3+2+1+2+1+5+4)/ 7 = 18/7。 -
哈希表查找不成功的ASL问题
2017-10-24 23:07:31哈希表(等概率情况下)查找成功与查找不成功的平均查找长度计算问题,迷惑了好一会,在这里总结下来: 首先,你要明白的是平均查找长度求的是期望,那么你就按照求期望的方法来求平均查找长度吧,千万记着...哈希表(等概率情况下)查找成功与查找不成功的平均查找长度计算问题,迷惑了好一会,在这里总结下来:
首先,你要明白的是平均查找长度求的是期望,那么你就按照求期望的方法来求平均查找长度吧,千万记着期望怎么求平均查找长度就怎么求啊。
题目:
在地址空间为0~16的散列区中,对以下关键字序列构造两个哈希表:
{Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec}
(1) 用线性探测开放地址法处理冲突;
(2) 用链地址法(开散列存储)处理冲突
并分别求这两个哈希表在等概率情况下查找成功和查找不成功时的平均查找长度。设哈希函数为
H(key) = i/2,其中i为关键字中第一个字母在字母表中的序号,如下:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26解决如下:
(1) 线性探测进入散列区的次序如下,X 代表冲突,要找下一个空格
Jan -> 5
Feb -> 3
Mar -> 6
Apr -> 0
May -> 6X -> 7
June -> 5X -> 6X -> 7X -> 8
July -> 5X -> 6X -> 7X -> 8X -> 9
Aug -> 0X -> 1
Sep -> 9X -> 10
Oct -> 7X -> 8X -> 9X -> 10X -> 11
Nov -> 7X -> 8X -> 9X -> 10X -> 11X -> 12
Dec -> 20
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Apr
Aug
Dec
Feb
Jan
Mar
May
Jun
July
Sep
OCt
Nov
很明显,查找成功时,查找Jan、Feb、Mar等仅需要一次,其余的也可以由上面看出来
所以查找成功时平均查找长度 (ASL) = (1 + 1 + 1 + 1 + 2 + 4 + 5 + 2 + 2 + 5 + 6 + 1) / 12 = 31/12 = 2.58 为什么是除以12呢?因为查找成功的情况总共有12种啊查找不成功时呢?什么是查找不成功呢?查找不成功就是从查找位置开始直到一个位置为空需要比较的次数。
首先,26/2=13,也就是说查找不成功的情况也只能出现在0~13之间,只有这14种情况。
举个例子来说,查找Aay吧,根据hash表,与Apr比较不匹配,接着与Aug比较又是不匹配,接着与Dec比较又是不匹配,又与Feb比较又是不匹配,到了4位置的时候为空了,即4上内容与nullkey比较,结果为空,所以查找Aay失败,查找长度为5。同理也能计算其他的。
最终平均查找失败时平均查找长度为(5+4+3+2+1+9+8+7+6+5+4+3+2+1)/14=60/14。注意啊,这里是除以14啊。(这是求期望的方法啊)
(2) 链地址法
0 之下有 Apr, Aug
2 之下有 Dec
3 之下有 Feb
5 之下有 Jan, June, July
6 之下有 Mar, May
7 之下有 Oct, Nov
9 之下有 Sep
查找成功时候,查 Apr, Dec, Feb, Jan, Mar, Oct, Sep 各需 1 次,查 Aug, June, May, Nov 各需 2 次,查 July 需 3 次。
所以查找成功时平均查找长度 (ASL) = (1 * 7 + 2 * 4 + 3 * 1) / 12 = 18/12 = 1.5查找失败时平均查找长度:举个例子吧,查找Boy,2/2=1,而1的地方的指针为空,就不用比较就可以知道不存在,查找产度为0。查找Aay,与Apr比较不匹配,与Aug比较不匹配,同时,Aug指向下一个节点的指针为空,就可以知道查找失败,查找长度为2。
所以查找失败的平均查找长度:(2+1+1+3+2+2+1)/14=12/14。
-
哈希表查找不成功平均长度例子
2020-04-30 16:08:40接下来讨论不成功的情况, 看表2,计算查找不成功的次数就直接找关键字到第一个地址上关键字为空的距离即可, 但根据哈希函数地址为MOD7,因此初始只可能在06的位置。等概率情况下,查找06位置查找失败的查找次数为:...等概率情况下查找不成功的平均查找长度:
接下来讨论不成功的情况, 看表2,计算查找不成功的次数就直接找关键字到第一个地址上关键字为空的距离即可, 但根据哈希函数地址为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之间,因此循环回去)的距离为5,因此查找不成功的次数为5.
地址6,到第一个关键为空的地址2(注意不是地址9,因为初始只可能在0~6之间,因此循环回去)的距离为4,因此查找不成功的次数为4.
因此查找不成功的次数表如下表所示所以ASLunsuccess= (3+2+1+2+1+5+4)/ 7 = 18/7。
————————————————
版权声明:本文为CSDN博主「dancheren」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/dancheren/article/details/76359424 -
哈希表等概率情况下查找成功和查找不成功的平均查找长度的计算
2016-09-02 22:55:25哈希表等概率情况下查找成功和查找不成功的平均查找长度的计算 最近复习了下数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时比较迷茫,不知道到底是怎么计算出来的。现在通过查阅...哈希表等概率情况下查找成功和查找不成功的平均查找长度的计算
最近复习了下数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时比较迷茫,不知道到底是怎么计算出来的。现在通过查阅资料终于知道如何计算了,所以记录下来以供以后查阅。
下面看下2010年2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题中一个考哈希表的题。
Question1:
将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组,散列函数为: H(key) = (keyx3) MOD 7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。
(1) 请画出所构造的散列表。
(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。
Ans:
(1).首先明确一个概念装载因子,装载因子是指所有关键子填充哈希表后饱和的程度,它等于 关键字总数/哈希表的长度。 根据题意,我们可以确定哈希表的长度为 L = 7/0.7 = 10;因此此题需要构建的哈希表是下标为0~9的一维数组。根据散列函数可以得到如下散列函数值表。
H(Key) = (keyx3) MOD 7, 例如key=7时, H(7) = (7x3)%7 = 21%7=0,其他关键字同理。
(表1)Key 7 8 30 11 18 9 14 H(Key) 0 3 6 5 5 6 0
采用线性探测再散列法处理冲突,所构造的散列表为:
(表2)地址 0 1 2 3 4 5 6 7 8 9 关键字 7 14 8 11 30 18 9
下面对散列表的构造方式加以说明,注意表1中的关键字7和14,30和9, 11和18,这三组关键子的H(Key)值相同,这在构建散列表时就会产生冲突,因为他们的地址相同,所以要通过一定的冲突处理方法来解决这个问题。依题,采用线性探测再散列法处理冲突。下面详细介绍如何构建散列表:
第一个key 7,它的地址是0,因此放到散列表的数组下表为0的位置,这个位置上没有关键字,因此没有冲突可以直接填入;
第二个key 8,它的地址是3,因此放到散列表的数组下表为3的位置,这个位置上没有关键字,因此没有冲突可以直接填入;
第三个key 30,它的地址是6,因此放到散列表的数组下表为6的位置,这个位置上没有关键字,因此没有冲突可以直接填入;
第四个key 11,它的地址是5,因此放到散列表的数组下表为5的位置,这个位置上没有关键字,因此没有冲突可以直接填入;
第五个key 18,它的地址是5,因此放到散列表的数组下表为5的位置,但这个位置上已经有关键字11,遇到了冲突,此时我们根据线性探测再散列法来处理这个冲突,探测下一个位置6, 6这个位置上已经存在关键字30则继续增加步长1,因此现在的新地址应为7,位置7上没有关键字,放入即可,到此冲突已经解决;
第六个key 9,它的地址是6,因此放到散列表的数组下表为6的位置,但这个位置上已经有关键字30,遇到了冲突,探测下一个位置7, 7这个位置上已经存在关键字18则继续增加步长1,因此现在的新地址应为8,位置8上没有关键字,放入即可;
第七个key 14,它的地址是0,因此放到散列表的数组下表为0的位置,但这个位置上已经有关键字7,遇到了冲突,探测下一个位置1, 位置1上没有关键字,放入即可;
到这一步所有关键字均已填入,散列表已经构造完成,如表2所示。
(2)等概率情况下查找成功平均查找长度:
这一问可以根据第一问的构造过程求解:
key7一次就填入了表中,因此查找次数为1,同理8, 30, 11查找次数均为1; key18 进行了3次放入操作,探测位置分别是5,6,7 ,因此查找次数为3;key9也是3次;key14 进行了两次探测,因此查找次数为2。次数表如表3所示
(表3)Key 7 8 30 11 18 9 14 Count 1 1 1 1 3 3 2
所以ASLsuccess= (1+1+1+1+3+3+2)/ 7 = 12/7。
等概率情况下查找不成功的平均查找长度:
接下来讨论不成功的情况, 看表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(注意不是地址9,因为初始只可能在0~6之间,因此循环回去)的距离为5,因此查找不成功的次数为5.
地址6,到第一个关键为空的地址2(注意不是地址9,因为初始只可能在0~6之间,因此循环回去)的距离为4,因此查找不成功的次数为4.
因此查找不成功的次数表如下表所示
(表4)Key 7 8 30 11 18 9 14 Count 3 2 1 2 1 5 4 所以ASLunsuccess= (3+2+1+2+1+5+4)/ 7 = 18/7。
-
哈希表(等概率情况下)查找成功与查找不成功的平均查找长度
2018-09-23 17:38:52继续小结,做到一道求 哈希表查找成功与查找不成功 情况下平均查找长度的计算问题,迷惑了好一会,在这里总结下来: 首先,你要明白的是平均查找长度求的是期望,那么你就按照求期望的方法来求平均查找长 -
C语言实现构造哈希表,计算等概率的情况查找成功与不成功的平均查找长度
2020-04-23 19:15:46编程实现:构造哈希表:在地址空间为0~12,对以下关键字序列:(Jan,Feb,Apr,May,Jun,Jul,Aug,Sep,Oct)建哈希表,并且求出等概率情况下查找成功与不成功的平均查找长度。 实现代码: typedef struct HashTable{ ... -
哈希表(等概率情况下)查找成功与查找不成功的平均查找长
2015-01-06 22:51:19做到一道求 哈希表查找成功与查找不成功 情况下平均查找长度的计算问题,迷惑了好一会,在这里总结下来: 首先,你要明白的是平均查找长度求的是期望,那么你就按照求期望的方法来求平均查 -
[数据结构与算法]哈希表(等概率情况下)查找成功与查找不成功的平均查找长度
2014-11-17 15:34:33做到一道求 哈希表查找成功与查找不成功 情况下平均查找长度的计算问题,迷惑了好一会,在这里总结下来: 首先,你要明白的是平均查找长度求的是期望,那么你就按照求期望的方法来求平均查找长度吧,千万记着... -
[数据结构与算法]哈希表(等概率情况下)查找成功与查找不成功的平均查找长度...
2014-11-17 15:34:00做到一道求 哈希表查找成功与查找不成功 情况下平均查找长度的计算问题,迷惑了好一会,在这里总结下来: 首先,你要明白的是平均查找长度求的是期望,那么你就按照求期望的方法来求平均查找长度吧,千万记着... -
哈希表计算等概率情况下查找不成功的平均查找长度
2013-12-26 16:31:20下面看下2010年2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题中一个考哈希表的题。 Question1: 将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表... -
哈希表中查找成功和不成功时的平均查找长度如何计算
2014-11-30 20:52:36Question1: 将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组,散列...(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。 Ans: (1).首先明 -
哈希表(散列表)查找成功与不成功的平均查找长度,一篇就够了
2020-12-26 22:14:21完整举例: 在地址空间为0~16的散列区中,对以下关键字序列构造两个...求查找成功与查找不成功的平均查找长度。 很据:H(x)=i/2;除不尽的,向下取整即可。如下所示: Jan - 5 Feb - 3 Mar -6 Apr -0 May - 6 June -5 -
哈希表查找 的 平均长度
2018-08-11 22:24:55将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。...(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。 一、查找成功平均长度 通过公式计算出存放的位置,如果该位置已经... -
哈希表中线性探测再散列法和等概率平均查找长度
2020-06-22 10:41:35(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。 Ans: (1).首先明确一个概念装载因子,装载因子是指所有关键子填充哈希表后饱和的程度,它等于 关键字总数/哈希表的长度。 根据题意,我们可以确定... -
哈希表中线性探测再散列法及等概率条件下平均查找长度
2018-10-17 11:39:38最近复习了下数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时比较迷茫,不知道到底是怎么计算出来的。现在通过查阅资料终于知道如何计算了,所以记录下来以供以后查阅。 下面看下2010年... -
哈希表的综合应用(创建、处理冲突、查找成功和失败的次数)
2015-12-11 17:59:18最近学了数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时比较迷茫,不知道到底是怎么计算出来的。现在通过查阅资料终于知道如何计算了,所以记录下来以供以后查阅。 Question1: 将关键字序列...
-
C++STL编程轻松入门
-
Java:排序算法
-
Vue.js:轻量高效的前端组件化方案
-
g1127:一个MakeCode项目-源码
-
LVS + Keepalived 实现 MySQL 负载均衡与高可用
-
脉冲Ho∶YAG激光与生物组织相互作用效果与残留热效应的分析
-
MySQL 高可用工具 DRBD 实战部署详解
-
JMETER 性能测试基础课程
-
用JSP写一个网络点击率记录器
-
BufferedInputStream的使用
-
MySQL你该了解的那些事【服务端篇】
-
【邻接矩阵】56 邻接矩阵:添加一个顶点
-
改进的小型多频带
-
一种基于改进FCM的自动图像分割算法
-
【Python-随到随学】 FLask第一周
-
PPTP_NNN 服务生产环境实战教程
-
MySQL 管理利器 mysql-utilities
-
2021年 系统分析师 系列课
-
【邻接矩阵】60 邻接矩阵:有权图删除边
-
用于无线胶囊内窥镜系统的具有极化分集的定向不敏感天线