當前位置:成語大全網 - 漢語詞典 - 如何計算哈希表的平均搜索長度?

如何計算哈希表的平均搜索長度?

對於n個數據元素的查找表,成功查找的平均長度為:ASL=∑PiCi (i=1,2,3,...,n),可以簡單的用數學期望來理解。其中:Pi是查找表中第I個數據元素的概率,Ci是第I個數據元素被比較的次數。

在查找表中找不到要搜索的元素,但是找到要搜索的元素在表中應該存在的位置的平均搜索次數稱為搜索不成功時的平均搜索長度,它是不成功的。

擴展數據

哈希表的查找過程和造表過程基本相同。有的鍵碼可以直接通過哈希函數轉換的地址找到,有的鍵碼在哈希函數得到的地址中有沖突,需要按照處理沖突的方法找到。在介紹的三種處理沖突的方法中,尋找沖突仍然是壹個給定值與鍵碼比較的過程。因此,哈希表搜索效率的衡量標準仍然是平均搜索長度。

在搜索的過程中,關鍵代碼比較的次數取決於沖突的次數。沖突少,搜索效率就高,沖突多,搜索效率就低。所以影響沖突數量的因素,也就是影響搜索效率的因素。有三個因素會影響沖突的數量:

1,哈希函數是否壹致;

2.處理沖突的方法;

3.哈希表的填充因子。

哈希表的填充因子定義為:α =表中填充的元素數/哈希表的長度。

α是哈希表填充度的符號因子。因為表的長度是壹個固定值,α與表中填充的元素數成正比,所以α越大,表中填充的元素越多,沖突的可能性就越大;α越小,表中填入的元素越少,沖突的可能性越小。

其實哈希表的平均搜索長度是填充因子α的函數,只是處理沖突的方法不同,作用也不同。

百度百科-平均搜索長度

百度百科-哈希表