求平均查找长度（成功+失败）

1、使用拉链法解决冲突

例：有一堆数据元素，关键字分别为{14，63，68}，散列函数H(key)=key%7,散列表长度是7

查找14成功需要比较1次
查找63成功需要比较2次
查找68成功需要比较1次
ASL成功=（1+2+1）/ 3【注意：分母是关键字个数】
1
2
3
4

查找映射结果是0失败需要比较0次【注意：和空指针^比较时，次数无需+1】
查找映射结果是1失败需要比较2次【注意：先和14比较，再和63比较，最后到空指针，终止比较】
查找映射结果是2失败需要比较0次
查找映射结果是3失败需要比较1次
查找映射结果是4失败需要比较0次
查找映射结果是5失败需要比较0次
查找映射结果是6失败需要比较0次
ASL失败=（0+2+0+1+0+0+0）/7【注意：分母是散列函数H(key)=key%7中的7】
1
2
3
4
5
6
7
8

2、使用线性探测法解决冲突

开放定址法：Hi=(Hi(key) + di)%表长【重要】
线性探测是 di 的取值为 0,1,2…表长-1

例：有一堆数据元素，关键字分别为{7，6，13}，散列函数H(key)=key%7,散列表长度是7【注意：散列表长=p】

查找7成功需要比较1次
查找6成功需要比较1次
查找13成功需要比较3次
ASL成功=（1+1+3）/ 3
1
2
3
4

13放入散列表的具体计算过程
H3(13)=13%7=6
【1】H3=(6+0)%7=6【和6冲突】
【2】H3=(6+1)%7=0【和7冲突】
【3】H3=(6+2)%7=1【放入】

查找映射结果是0失败需要比较3次【比较到的下标分别是0、1、2】
查找映射结果是1失败需要比较2次【比较到的下标分别是1、2】
查找映射结果是2失败需要比较1次【比较到的下标分别是2】
查找映射结果是3失败需要比较1次
查找映射结果是4失败需要比较1次
查找映射结果是5失败需要比较1次
查找映射结果是6失败需要比较4次【注意回头：比较到的下标分别是6、0、1、2】
ASL失败=（3+2+1+1+1+1+4）/7
1
2
3
4
5
6
7
8

例：有一堆数据元素，关键字分别为{7，6，13}，散列函数H(key)=key%7,散列表长度是9【注意区别：散列表长>p】

查找7成功需要比较1次
查找6成功需要比较1次
查找13成功需要比较2次
ASL成功=（1+1+2）/ 3
1
2
3
4

13放入散列表的具体计算过程
H3(13)=13%7=6
【1】H3=(6+0)%9=6【和6冲突】
【2】H3=(6+1)%9=7【放入】

查找映射结果是0失败需要比较2次【比较到的下标分别是0、1】
查找映射结果是1失败需要比较1次
查找映射结果是2失败需要比较1次
查找映射结果是3失败需要比较1次
查找映射结果是4失败需要比较1次
查找映射结果是5失败需要比较1次
查找映射结果是6失败需要比较3次【注意：比较到的下标分别是6、7】
ASL失败=（2+1+1+1+1+1+3）/7
1
2
3
4
5
6
7
8

3、使用平方探测法解决冲突

例：有一堆数据元素，关键字分别为{7，14，21}，散列函数H(key)=key%7,散列表长度是9

注意：21是放在下标8的位置上

查找7成功需要比较1次
查找14成功需要比较2次
查找21成功需要比较3次
ASL成功=（1+2+3）/ 3
1
2
3
4

注意：查找21的di是-1表示从下标0位置向左走1步，走到8（有点像循环队列）

查找映射结果是0失败需要比较4次【比较到的下标分别是0、1、8、4】
查找映射结果是1失败需要比较2次
查找映射结果是2失败需要比较1次
查找映射结果是3失败需要比较1次
查找映射结果是4失败需要比较1次
查找映射结果是5失败需要比较1次
查找映射结果是6失败需要比较1次
ASL失败=（4+2+1+1+1+1+1）/7
1
2
3
4
5
6
7
8

参考：https://www.bilibili.com/video/BV1b7411N798?p=76&share_source=copy_web