散列表的平均查找长度怎么计算？

Question

如题：假定一个待散列存储的线性表为（32,78,29,63,48,94,25,36,18,70,49,80），散列地址空间为HT[11] ，若采用除留余数法构造散列函数和链接法处理冲突，求出平均查找长度？（这个公式到底有用吗：1/2(1+1/(1-装填因子))）

Answer 1

对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL=∑PiCi (i=1，2，3，…，n)，可以简单以数学上的期望来这么理解。其中：Pi 为查找表中第i个数据元素的概率，Ci为找到第i个数据元素时已经比较过的次数。

在查找表中查找不到待查元素，但是找到待查元素应该在表中存在的位置的平均查找次数称为查找不成功时的平均查找长度，不成功。

扩展资料

散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。

查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：

1、散列函数是否均匀；

2、处理冲突的方法；

3、散列表的装填因子。

散列表的装填因子定义为：α= 填入表中的元素个数 / 散列表的长度

α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。

实际上，散列表的平均查找长度是装填因子α的函数，只是不同处理冲突的方法有不同的函数。

参考资料来源：百度百科-平均查找长度

参考资料来源：百度百科-散列表

Answer 2

先构造散列表，再将查找到每个关键码的探查次数求和，然后除以关键码的总个数就是ASL了
这个数据序列的结果就是17/12
这个公式只是用随机过程和排队论得出的理论性能，大量的随机数据的平均值就是这个值，但是每个表的值并非如此本回答被网友采纳

Answer 3

一、分析问题：这是一个建立哈希函数的问题。　哈希表中元素是由哈希函数确定的。将数据元素的关键字K作为自变量，通过一定的函数关系（称为哈希函数），计算出的值，即为该元素的存储地址。表示为： 　　Addr = H（key） 　　为此在建立一个哈希表之前需要解决两个主要问题： 　　⑴构造一个合适的哈希函数 　　均匀性 H（key）的值均匀分布在哈希表中； 　　简单　以提高地址计算的速度 　　⑵冲突的处理 　　冲突：在哈希表中，不同的关键字值对应到同一个存储位置的现象。即关键字K1≠K2，但H（K1）= H（K2）。均匀的哈希函数可以减少冲突，但不能避免冲突。发生冲突后，必须解决；也即必须寻找下一个可用地址。 本题是用除留余数法构造散列函数（哈希函数），用链接法（拉链法）处理冲突。1、除留余数法：取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。 　　H(key)=key MOD p (p<=m)2、拉链法：拉出一个动态链表代替静态顺序存储结构，可以避免哈希函数的冲突，不过缺点就是链表的设计过于麻烦，增加了编程复杂度。此法可以完全避免哈希函数的冲突。确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度(Average Search Length)，ASL成功。 　　对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL=∑PiCi (i=1,2,3,…,n),可以简单以数学上的期望来这么理解。其中：Pi 为查找表中第i个数据元素的概率，Ci为找到第i个数据元素时已经比较过的次数。 　　在查找表中查找不到待查元素，但是找到待查元素应该在表中存在的位置的平均查找次数称为查找不成功时的平均查找长度，ASL不成功。二、解答问题散列地址空间为HT[11] p=11所以32%11＝10......80%11=3。所以散列地址为（10，1，7，8，4，6，3，3，7，4，5，3） ASL=∑PiCi (i=1,2,3,…,n),在这里n=12p1=1/12,C1=0;P2=1/12,C2=1;然后你自已求解吧