散列表鏈地址法查找成功的平均查找長度怎么計(jì)算？對于包含N個數(shù)據(jù)元素的查找表，成功查找的平均長度為ASL=∑Pici（I=1，2，3，N），其中：Pi是查找表中第I個數(shù)據(jù)元素的概率，CI是找到第I個數(shù)據(jù)

散列表鏈地址法查找成功的平均查找長度怎么計(jì)算？

對于包含N個數(shù)據(jù)元素的查找表，成功查找的平均長度為ASL=∑Pici（I=1，2，3，N），其中：Pi是查找表中第I個數(shù)據(jù)元素的概率，CI是找到第I個數(shù)據(jù)元素時進(jìn)行比較的次數(shù)。

眾所周知，要散列的線性表是（38、25、74、63、52、48），散列函數(shù)是h（k）=kmod7。如果使用線性檢測的開放地址方法來處理沖突，則平均查找長度為：

答案：ASL=p1c1、P2C2、p3c3…

也可以表示為

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

其中C是每個數(shù)字的查詢數(shù)

根據(jù)h（k）=kmod7，我們可以得到以下結(jié)果：

38----1

25----1

74----2

63----1

52----4

48----3

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

哈希函數(shù)的鏈地址法的查找不成功怎么算？

首先建立表，然后我們可以計(jì)算每個位置不成功時的比較次數(shù)之和，并將其除以表空間數(shù)

！例如：hash函數(shù)為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個位置不成功時的比較次數(shù)是第n個位置到第一個位置的距離，沒有數(shù)據(jù)。至少需要查詢多少次才能確認(rèn)沒有這樣的值。

（1）查詢哈希（x）=0。當(dāng)表值為空時，至少有9次可以確認(rèn)查詢失敗。

（2）查詢哈希（x）=1。當(dāng)表值為空時，至少有8次可以確認(rèn)查詢失敗。

（3）查詢哈希（x）=2。當(dāng)表值為空時，至少7次可以確認(rèn)查詢失敗。

（4）查詢哈希（x）=3。當(dāng)表值為空時，至少6次可以確認(rèn)查詢失敗。

（5）查詢哈希（x）=4。當(dāng)表值為空時，至少5次可以確認(rèn)查詢失敗。

（6）查詢哈希（x）=5。當(dāng)表值為空時，您至少可以確認(rèn)查詢失敗4次。

（7）查詢哈希（x）=6。當(dāng)表值為空時，至少3次可以確認(rèn)查詢失敗。

（8）查詢哈希（x）=7。只有當(dāng)表值至少兩次為空時，才能確認(rèn)查詢失敗。

（9）查詢哈希（x）=8。只有當(dāng)表值至少為空一次時，才能確認(rèn)查詢失敗。

（10）查詢哈希（x）=9。只有當(dāng)表值至少為空一次時，才能確認(rèn)查詢失敗。

（11）查詢哈希（x）=10。只有當(dāng)表值至少為空兩次時，查詢才會失敗。

（12）查詢哈希（x）=11。只有當(dāng)表值至少為空一次時，才能確認(rèn)查詢失敗。

（13）查詢哈希（x）=12。當(dāng)表值為空（循環(huán)查詢序列表）時，至少10次可以確認(rèn)查詢失敗。

搜索不成功ASL：定義為搜索不成功時對關(guān)鍵字執(zhí)行比較的平均次數(shù)。因此，對于拉鏈方法，如果第一次檢測到空位置，則搜索失敗長度為0。例如，aslunsucc=（10210100103）/13≈10/13≈0.77

ASL查找失敗數(shù)是從地址到空位置的比較數(shù)。5原因1:哈希表中有5個空位置，比較一次。5原因5：哈希表中關(guān)聯(lián)詞的位置比較一次，公共溢出區(qū)比較3+1。除以地址總數(shù)