哈希表等概率情況下查找成功和查找不成功的平均查找長度的計算
最近復習了下數據結構中的哈希表，發現在計算等概率情況下查找不成功的平均查找長度時比較迷茫，不知道到底是怎麼計算出來的。現在通過查閱資料終於知道如何計算了，所以記錄下來以供以後查閱。
下面看下2010年2010年全國碩士研究生入學統一考試計算機科學與技術學科聯考計算機學科專業基礎綜合試題中一個考哈希表的題。
Question1:
將關鍵字序列（7、8、30、11、18、9、14）散列存儲到散列表中。散列表的存儲空間是一個下標從0開始的一維數組，散列函數為： H(key) = (keyx3) MOD 7，處理沖突采用線性探測再散列法，要求裝填（載）因子為0.7。
(1) 請畫出所構造的散列表。
(2) 分別計算等概率情況下查找成功和查找不成功的平均查找長度。
Ans：
(1).首先明確一個概念裝載因子，裝載因子是指所有關鍵子填充哈希表後飽和的程度，它等於 關鍵字總數/哈希表的長度。 根據題意，我們可以確定哈希表的長度為 L = 7/0.7 = 10；因此此題需要構建的哈希表是下標為0~9的一維數組。根據散列函數可以得到如下散列函數值表。
H(Key) = (keyx3) MOD 7, 例如key=7時， H(7) = (7x3）%7 = 21%7=0，其他關鍵字同理。
Key 7 8 30 11 18 9 14 H(Key) 0 3 6 5 5 6 0(表1)
采用線性探測再散列法處理沖突，所構造的散列表為：
地址 0 1 2 3 4 5 6 7 8 9 關鍵字 7 14 8 11 30 18 9(表2)
下面對散列表的構造方式加以說明，注意表1中的關鍵字7和14，30和9， 11和18，這三組關鍵子的H(Key)值相同，這在構建散列表時就會產生沖突，因為他們的地址相同，所以要通過一定的沖突處理方法來解決這個問題。依題，采用線性探測再散列法處理沖突。下面詳細介紹如何構建散列表：
第一個key 7，它的地址是0，因此放到散列表的數組下表為0的位置，這個位置上沒有關鍵字，因此沒有沖突可以直接填入；
第二個key 8，它的地址是3，因此放到散列表的數組下表為3的位置，這個位置上沒有關鍵字，因此沒有沖突可以直接填入；
第三個key 30，它的地址是6，因此放到散列表的數組下表為6的位置，這個位置上沒有關鍵字，因此沒有沖突可以直接填入；
第四個key 11，它的地址是5，因此放到散列表的數組下表為5的位置，這個位置上沒有關鍵字，因此沒有沖突可以直接填入；
第五個key 18，它的地址是5，因此放到散列表的數組下表為5的位置，但這個位置上已經有關鍵字11，遇到了沖突，此時我們根據線性探測再散列法來處理這個沖突，探測下一個位置6, 6這個位置上已經存在關鍵字30則繼續增加步長1，因此現在的新地址應為7，位置7上沒有關鍵字，放入即可，到此沖突已經解決；
第六個key 9，它的地址是6，因此放到散列表的數組下表為6的位置，但這個位置上已經有關鍵字30，遇到了沖突，探測下一個位置7, 7這個位置上已經存在關鍵字18則繼續增加步長1，因此現在的新地址應為8，位置8上沒有關鍵字，放入即可；
第七個key 14，它的地址是0，因此放到散列表的數組下表為0的位置，但這個位置上已經有關鍵字7，遇到了沖突，探測下一個位置1, 位置1上沒有關鍵字，放入即可；
到這一步所有關鍵字均已填入，散列表已經構造完成，如表2所示。
（2）等概率情況下查找成功平均查找長度：
這一問可以根據第一問的構造過程求解：
key7一次就填入了表中，因此查找次數為1，同理8， 30， 11查找次數均為1； key18 進行了3次放入操作，探測位置分別是5，6，7 ，因此查找次數為3；key9也是3次；key14 進行了兩次探測，因此查找次數為2。次數表如表3所示
Key 7 8 30 11 18 9 14 Count 1 1 1 1 3 3 2(表3)
所以ASLsuccess= （1+1+1+1+3+3+2）/ 7 = 12/7。
等概率情況下查找不成功的平均查找長度：
接下來討論不成功的情況, 看表2，計算查找不成功的次數就直接找關鍵字到第一個地址上關鍵字為空的距離即可， 但根據哈希函數地址為MOD7，因此初始只可能在0~6的位置。等概率情況下，查找0~6位置查找失敗的查找次數為：
看地址0，到第一個關鍵字為空的地址2的距離為3，因此查找不成功的次數為3.
地址1， 到第一個關鍵為空的地址2的距離為2，因此查找不成功的次數為2.
地址2， 到第一個關鍵為空的地址2的距離為1，因此查找不成功的次數為1.
地址3，到第一個關鍵為空的地址4的距離為2，因此查找不成功的次數為2.
地址4，到第一個關鍵為空的地址4的距離為1，因此查找不成功的次數為1.
地址5，到第一個關鍵為空的地址2(注意不是地址9，因為初始只可能在0~6之間，因此循環回去)的距離為5，因此查找不成功的次數為5.
地址6，到第一個關鍵為空的地址2(注意不是地址9，因為初始只可能在0~6之間，因此循環回去)的距離為4，因此查找不成功的次數為4.
因此查找不成功的次數表如下表所示
Key 7 8 30 11 18 9 14 Count 3 2 1 2 1 5 4(表4)
所以ASLunsuccess= （3+2+1+2+1+5+4）/ 7 = 18/7。
