散列表冲突解决方法：线性探测法与链地址法比较 - 平均查找长度分析

///'首先，根据散列函数 H(k) = k mod 7，计算每个关键字的散列地址：//n//nH(25) = 25 mod 7 = 4//nH(31) = 31 mod 7 = 3//nH(8) = 8 mod 7 = 1//nH(27) = 27 mod 7 = 6//nH(13) = 13 mod 7 = 6//nH(68) = 68 mod 7 = 5//n//n接下来，我们分别使用线性探测法和链地址法来处理冲突。//n//n1. 线性探测法：//n在线性探测法中，当发生冲突时，我们将继续探测下一个位置，直到找到一个空槽或者查找完整个散列表。//n//n将关键字依次放入散列表中：//n位置4：25//n位置3：31//n位置1：8//n位置6：27//n位置6已被占用，继续探测下一个位置。//n位置0：13//n位置5：68//n//n最终散列表为：//n位置0：13//n位置1：8//n位置2：空//n位置3：31//n位置4：25//n位置5：68//n位置6：27//n位置7：空//n//n计算平均查找长度：//n(1+2+3+4+5+6+7) / 7 = 4//n//n2. 链地址法：//n在链地址法中，我们将每个冲突的关键字放入一个链表中。//n//n建立链表并将关键字插入：//n位置4：25//n位置3：31//n位置1：8//n位置6：27//n位置6已被占用，将27插入到27的链表中。//n位置0：13//n位置5：68//n//n最终散列表为：//n位置0：13 -> NULL//n位置1：8 -> NULL//n位置2：NULL//n位置3：31 -> NULL//n位置4：25 -> NULL//n位置5：68 -> NULL//n位置6：27 -> NULL//n位置7：NULL//n//n计算平均查找长度：//n(1+2+1+1+1+1+1) / 7 = 1//n//n因此，使用线性探测法的平均查找长度为4，使用链地址法的平均查找长度为1。//n//n///