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

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

1

2

3

4

5

6

7

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

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