2022-02-08 18:41发布
查找不成功的次数表如下表所示 Key 7 8 30 11 18 9 14 Count 3 2 1 2 1 5 所以ASLunsuccess= (3+2+1+2+1+5+4)/ 7 = 18/7。 下面看下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,其他关键字同理 Key 7 8 30 11 18 9 14 H(Key) 0 3 6 5 5 6 0 采用线性探测再散列法处理冲突,所构造的散列表为: 地址 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所示 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. 因此查找不成功的次数表如下表所示 Key 7 8 30 11 18 9 14 Count 3 2 1 2 1 5 所以ASLunsuccess= (3+2+1+2+1+5+4)/ 7 = 18/7。
2.
用链地址法(开散列存储)处理冲突 并分别求这两个哈希表在等概率情况下查找成功和查找不成功时的平均查找长度。设哈希函数为 H(key) = i/2,其中i为关键字中第一个字母在字母表中的序号,如下: A B C...
3.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...
4.
之下有 Apr, Aug
这个主要是看你数组的长度是多少, 比如之前写过的一个程序有个数组存的是各个客户端的ip地址:string clientIp[4]={XXX, xxx, xxx, xxx};这个时候如果想把hash值对应到上面四个地址的话,就应该对4取余,这个时候p就应该为4...
哈希表的大小 · 关键字的分布情况 · 记录的查找频率 1.直接寻址法:取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b,其中a和b为常数(这种散列函数叫做自身函数)。...
哈希表的大小取决于一组质数,原因是在hash函数中,你要用这些质数来做模运算(%)。而分析发现,如果不是用质数来做模运算的话,很多生活中的数据分布,会集中在某些点上。所以这里最后采用了质数做模的除数。 因为用质数做了模的除数,自然存储空间的大小也用质数了...
是啊,哈希函数的设计至关重要,好的哈希函数会尽可能地保证计算简单和散列地址分布均匀,但是,我们需要清楚的是,数组是一块连续的固定长度的内存空间
解码查表优化算法,seo优化
1.对对象元素中的关键字(对象中的特有数据),进行哈希算法的运算,并得出一个具体的算法值,这个值 称为哈希值。2.哈希值就是这个元素的位置。3.如果哈希值出现冲突,再次判断这个关键字对应的对象是否相同。如果对象相同,就不存储,因为元素重复。如果对象不同,就...
一般情况确实不应该用地址来作为删除的参数,但如果你已经事先搜索到了一个元素但之后不用了不就可以
哈希表是散列的一种。散列是一种用以常数平均时间执行插入、删除和查找的技术。 为了得到更快的执行速度,当查询某个元素多于遍历时可使用。但是数组无法确定准确的位置
跟加载因子设置的大小有关
虽然哈希表和数组在 lua 里都表示为一个 table,但是其底层实现还是有所区别的,理想情况下哈希表的内存占用是数组的两倍,主要区别在于哈希节点比数组节点多了一个 TKey 的内存占用。在数据量大的情况下考虑使用数组可以有效减少内存...
我们知道,数据结构的物理存储结构只有两种:顺序存储结构和链式存储结构(像栈,队列,树,图等是从逻辑结构去抽象的,映射到内存中,也这两种物理组织形式),在数组中根据下标查找某个元素,一次定位就可以达到,哈希表利用了这种特性,哈希表的主干就是数...
哈希表可以理解为一维数组。因为只是单一的坐标。当然如果考虑到哈希碰撞,理解为二维数组也无不可。至于下标1跟10001,这个问题很好。你观察到了,这样的数组会有大量的空洞。这是一种常见的现象。一维的这种数组叫做稀疏数组,二维的这种数组叫做稀疏矩阵。...
在数据结构哈希表中不成功平均查找长度和成功平均查找长度之间并没有什么直接的关系。他们都是对于特定的哈希表和特定的查找序列,才有意义的。
A--->function()---> B源数据A经过function()的运算得到B.这里的function()就是哈希函数,它是某一种hash算法的实现。得到的数据B就是hashCode,它是源数据A的哈希体现。如果我们将A->B这样的的关系保存下来,存储这个对应关系的我们称为哈希表。补充:还是正...
哈希表的长度一般是定长的,在存储数据之前我们应该知道我们存储的数据规模是多大,应该尽可能地避免频繁地让哈希表扩容。但是如果设计的太大,那么就会浪费空间,因为我们跟不用不到那么大的空间来存储我们当前的数据规模;如果设计的太小,那么就会很容易发...
最多设置5个标签!
2.
用链地址法(开散列存储)处理冲突 并分别求这两个哈希表在等概率情况下查找成功和查找不成功时的平均查找长度。设哈希函数为 H(key) = i/2,其中i为关键字中第一个字母在字母表中的序号,如下: A B C...
3.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...
4.
之下有 Apr, Aug
{19,14,23,01,68,20,84,27,55,11,10,79}
hash = key;
分离链接解决冲突法
key kash_key find_numbers
19 6 1
14 1 1
23 10 1
01 1 2 ( 01->14)
68 3 1
20 7 1
84 6 2 ( 84->19)
27 1 3 ( 27->01->14)
55 3 2 ( 55->68)
11 11 1
10 10 2 ( 10->23 )
79 1 4 ( 79->27->01->14)
ASL(12) = (1*6+2*4+3+4)/12
相关问题推荐
这个主要是看你数组的长度是多少, 比如之前写过的一个程序有个数组存的是各个客户端的ip地址:string clientIp[4]={XXX, xxx, xxx, xxx};这个时候如果想把hash值对应到上面四个地址的话,就应该对4取余,这个时候p就应该为4...
哈希表的大小 · 关键字的分布情况 · 记录的查找频率 1.直接寻址法:取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b,其中a和b为常数(这种散列函数叫做自身函数)。...
哈希表的大小取决于一组质数,原因是在hash函数中,你要用这些质数来做模运算(%)。而分析发现,如果不是用质数来做模运算的话,很多生活中的数据分布,会集中在某些点上。所以这里最后采用了质数做模的除数。 因为用质数做了模的除数,自然存储空间的大小也用质数了...
是啊,哈希函数的设计至关重要,好的哈希函数会尽可能地保证计算简单和散列地址分布均匀,但是,我们需要清楚的是,数组是一块连续的固定长度的内存空间
解码查表优化算法,seo优化
1.对对象元素中的关键字(对象中的特有数据),进行哈希算法的运算,并得出一个具体的算法值,这个值 称为哈希值。2.哈希值就是这个元素的位置。3.如果哈希值出现冲突,再次判断这个关键字对应的对象是否相同。如果对象相同,就不存储,因为元素重复。如果对象不同,就...
一般情况确实不应该用地址来作为删除的参数,但如果你已经事先搜索到了一个元素但之后不用了不就可以
哈希表是散列的一种。散列是一种用以常数平均时间执行插入、删除和查找的技术。 为了得到更快的执行速度,当查询某个元素多于遍历时可使用。但是数组无法确定准确的位置
跟加载因子设置的大小有关
虽然哈希表和数组在 lua 里都表示为一个 table,但是其底层实现还是有所区别的,理想情况下哈希表的内存占用是数组的两倍,主要区别在于哈希节点比数组节点多了一个 TKey 的内存占用。在数据量大的情况下考虑使用数组可以有效减少内存...
我们知道,数据结构的物理存储结构只有两种:顺序存储结构和链式存储结构(像栈,队列,树,图等是从逻辑结构去抽象的,映射到内存中,也这两种物理组织形式),在数组中根据下标查找某个元素,一次定位就可以达到,哈希表利用了这种特性,哈希表的主干就是数...
哈希表可以理解为一维数组。因为只是单一的坐标。当然如果考虑到哈希碰撞,理解为二维数组也无不可。至于下标1跟10001,这个问题很好。你观察到了,这样的数组会有大量的空洞。这是一种常见的现象。一维的这种数组叫做稀疏数组,二维的这种数组叫做稀疏矩阵。...
在数据结构哈希表中不成功平均查找长度和成功平均查找长度之间并没有什么直接的关系。他们都是对于特定的哈希表和特定的查找序列,才有意义的。
A--->function()---> B源数据A经过function()的运算得到B.这里的function()就是哈希函数,它是某一种hash算法的实现。得到的数据B就是hashCode,它是源数据A的哈希体现。如果我们将A->B这样的的关系保存下来,存储这个对应关系的我们称为哈希表。补充:还是正...
哈希表的长度一般是定长的,在存储数据之前我们应该知道我们存储的数据规模是多大,应该尽可能地避免频繁地让哈希表扩容。但是如果设计的太大,那么就会浪费空间,因为我们跟不用不到那么大的空间来存储我们当前的数据规模;如果设计的太小,那么就会很容易发...