链地址法平均查找长度
时间: 2023-12-04 16:39:19 浏览: 459
链地址法是一种解决散列表冲突的方法,它将具有相同散列值的元素存储在同一个链表中。平均查找长度(ASL)是指查找一个元素时平均需要遍历的节点数。在链地址法中,查找成功和查找不成功的平均查找长度的计算方式不同。
1. 查找成功的平均查找长度ASLsuccess的计算方法如下:
- 对于每个具有相同散列值的元素,遍历它们所在的链表,直到找到目标元素。
- 计算每个元素在链表中的位置,将它们的位置相加并除以元素总数,得到平均查找长度ASLsuccess。
2. 查找不成功的平均查找长度ASLunsuccess的计算方法如下:
- 对于目标元素的散列值,找到对应的链表。
- 遍历该链表,计算链表长度并将其加1,得到平均查找长度ASLunsuccess。
以引用为例,关键字序列{1 13 12 34 38 33 27 22}散列存储到散列表中,散列函数为H(key)=key mod 11,处理冲突采用链地址法。具体步骤如下:
1. 根据散列函数,将关键字序列散列到散列表中,得到以下结果:
|地址|关键字|
|---|---|
|0|33|
|1|22|
|2|12|
|3|1 -> 34|
|4|38|
|5|13|
|6|27|
|7||
|8|11|
|9|30|
其中,地址为3的位置发生了冲突,使用链地址法将1和34存储在同一个链表中。
2. 计算查找成功的平均查找长度ASLsuccess:
- 1的位置为3,34的位置为3,链表长度为2,ASLsuccess = (1+2)/2 = 1.5。
- 12的位置为2,链表长度为1,ASLsuccess = 1。
- 13的位置为5,链表长度为1,ASLsuccess = 1。
- 22的位置为1,链表长度为1,ASLsuccess = 1。
- 27的位置为6,链表长度为1,ASLsuccess = 1。
- 33的位置为0,链表长度为1,ASLsuccess = 1。
- 38的位置为4,链表长度为1,ASLsuccess = 1。
- 平均查找长度ASLsuccess = (1.5+1+1+1+1+1+1)/7 = 1.1429。
3. 计算查找不成功的平均查找长度ASLunsuccess:
- 目标元素的散列值为9,对应的链表为空,链表长度为0,ASLunsuccess = 1。
因此,在等概率情况下,查找成功的平均查找长度为1.1429,查找不成功的平均查找长度为1。