設(shè)散列表長度8，散列函數(shù)H(k)=k%7,用線性探測解決沖突，則根據(jù)一組初始關(guān)鍵字序列。見下？012345678 15 16 22 30 32上面是哈希表中數(shù)據(jù)的分布，計算如下（1 2 4 4 3）/

設(shè)散列表長度8，散列函數(shù)H(k)=k%7,用線性探測解決沖突，則根據(jù)一組初始關(guān)鍵字序列。見下？

1

2

3

4

5

6

7

8 15 16 22 30 32上面是哈希表中數(shù)據(jù)的分布，計算如下（1 2 4 4 3）/6=8/3括號中的六個數(shù)字，從左到右，是初始關(guān)鍵字序列中每個關(guān)鍵字所需的搜索次數(shù)。從左到右的線性檢測是在發(fā)生沖突時向后移動以找到新的位置。8占據(jù)位置1，15%7=1，但被8占據(jù)，所以只能移動到2。后來查15的時候，還需要比較2次，16%7=2，但是位置2被15占據(jù)了，16搜索后只能移到位置3，需要比較2次，22%7=1，但是位置1被占據(jù)了，向后移動，位置2和3被占據(jù)了，結(jié)果最后移到位置4，你需要比較4次。您可以通過這種方式推理得到結(jié)果

首先構(gòu)造哈希表，然后求和查找每個鍵的探測數(shù)，然后除以總鍵數(shù)即為ASL。這個數(shù)據(jù)序列的結(jié)果是17/12。這個公式只是利用隨機過程和排隊論得到的理論性能。大量隨機數(shù)據(jù)的平均值就是這個值，但每個表的值不是這樣