线性探测法的平均查找长度 散列表链地址法查找成功的平均查找长度怎么计算？

散列表链地址法查找成功的平均查找长度怎么计算？

对于包含N个数据元素的查找表，成功查找的平均长度为ASL=∑Pici（I=1，2，3，N），其中：Pi是查找表中第I个数据元素的概率，CI是找到第I个数据元素时进行比较的次数。

众所周知，要散列的线性表是（38、25、74、63、52、48），散列函数是h（k）=kmod7。如果使用线性检测的开放地址方法来处理冲突，则平均查找长度为：

答案：ASL=p1c1、P2C2、p3c3…

也可以表示为

ASL=1/N（C1、C2、C3…）…

其中C是每个数字的查询数

根据h（k）=kmod7，我们可以得到以下结果：

38----1

25----1

74----2

63----1

52----4

48----3

所以ASL=1/6（1 1 1 2 1 4 3）=2

哈希函数的链地址法的查找不成功怎么算？

首先建立表，然后我们可以计算每个位置不成功时的比较次数之和，并将其除以表空间数

！例如：hash函数为hash（x）=x mod 13，采用线性检测，哈希表建立后，搜索不成功时如何求平均搜索长度！？

成功搜索的平均长度：ASL=（13 1 2 1 9 1 1）/10=2.2

失败搜索的平均长度：ASL=（9 8 7 6 5 4 3 2 1 1 1 10）/13=4.54

注意：第n个位置不成功时的比较次数是第n个位置到第一个位置的距离，没有数据。至少需要查询多少次才能确认没有这样的值。

（1）查询哈希（x）=0。当表值为空时，至少有9次可以确认查询失败。

（2）查询哈希（x）=1。当表值为空时，至少有8次可以确认查询失败。

（3）查询哈希（x）=2。当表值为空时，至少7次可以确认查询失败。

（4）查询哈希（x）=3。当表值为空时，至少6次可以确认查询失败。

（5）查询哈希（x）=4。当表值为空时，至少5次可以确认查询失败。

（6）查询哈希（x）=5。当表值为空时，您至少可以确认查询失败4次。

（7）查询哈希（x）=6。当表值为空时，至少3次可以确认查询失败。

（8）查询哈希（x）=7。只有当表值至少两次为空时，才能确认查询失败。

（9）查询哈希（x）=8。只有当表值至少为空一次时，才能确认查询失败。

（10）查询哈希（x）=9。只有当表值至少为空一次时，才能确认查询失败。

（11）查询哈希（x）=10。只有当表值至少为空两次时，查询才会失败。

（12）查询哈希（x）=11。只有当表值至少为空一次时，才能确认查询失败。

（13）查询哈希（x）=12。当表值为空（循环查询序列表）时，至少10次可以确认查询失败。

搜索不成功ASL：定义为搜索不成功时对关键字执行比较的平均次数。因此，对于拉链方法，如果第一次检测到空位置，则搜索失败长度为0。例如，aslunsucc=（10210100103）/13≈10/13≈0.77

ASL查找失败数是从地址到空位置的比较数。5原因1:哈希表中有5个空位置，比较一次。5原因5：哈希表中关联词的位置比较一次，公共溢出区比较3+1。除以地址总数

线性探测法的平均查找长度 链地址法查找不成功的次数 链地址法哈希表

版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。