哈希表查找成功和不成功的算法

1、哈希表查找不成功怎么計算？解答：先建好表，然后可以算出每個位置不成功時的比較次數(shù)之和，再除以表空問個數(shù)！例如：散列函數(shù)為hash(x)=xMOD13,用線性探測，建立了哈希表之后，如何求查找不成功時的平均查找長度?。康刂罚?123456789101112數(shù)據(jù)：391228154244625-3638成功次數(shù)：1312211911不成功次數(shù)：98765432112110查找成功時的平均查找長度:ASL=(1+3+1+2+2+1+1+9+1+1)/10=2.2查找不成功時的平均查找長度：ASL=(9+8+7+6+5+4+3+2+1+1+2+1+10)/13=4.54說明：第n個位置不成功時的比較次

2、數(shù)為，第n個位置到第1個沒有數(shù)據(jù)位置的距離。至少要查詢多少次才能確認(rèn)沒有這個值。(1)查詢hash(x)=0,至少要查詢9次遇到表值為空的時候，才能確認(rèn)查詢失敗。(2)查詢hash(x)=1,至少要查詢8次遇到表值為空的時候，才能確認(rèn)查詢失敗。(3)查詢hash(x)=2,至少要查詢7次遇到表值為空的時候，才能確認(rèn)查詢失敗。(4)查詢hash(x)=3,至少要查詢6次遇到表值為空的時候，才能確認(rèn)查詢失敗。(5)查詢hash(x)=4,至少要查詢5次遇到表值為空的時候，才能確認(rèn)查詢失敗。(6)查詢hash(x)=5,至少要查詢4次遇到表值為空的時候，才能確認(rèn)查詢失敗。(7)查詢hash(x)=6

3、,至少要查詢3次遇到表值為空的時候，才能確認(rèn)查詢失敗。(8)查詢hash(x)=7,至少要查詢2次遇到表值為空的時候，才能確認(rèn)查詢失敗。(9)查詢hash(x)=8,至少要查詢1次遇到表值為空的時候，才能確認(rèn)查詢失敗。(10)查詢hash(x)=9,至少要查詢1次遇到表值為空的時候，才能確認(rèn)查詢失敗。(11)查詢hash(x)=10,至少要查詢2次遇到表值為空的時候，才能確認(rèn)查詢失敗。(12)查詢hash(x)=11,至少要查詢1次遇到表值為空的時候，才能確認(rèn)查詢失敗。(13)查詢hash(x)=12,至少要查詢10次遇到表值為空(循環(huán)查詢順序表)的時候，才能確認(rèn)查詢失敗。下面看下2010年2

4、010年全國碩士研究生入學(xué)統(tǒng)一考試計算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題中一個考哈希表的題。Question1:將關(guān)鍵字序列(7、8、30、11、18、9、14)散列存儲到散列表中。散列表的存儲空間是一個下標(biāo)從0開始的一維數(shù)組，散列函數(shù)為：H(key)=(keyx3)MOD7,處理沖突采用線性探測再散列法，要求裝填(載)因子為0.7。(1)請畫出所構(gòu)造的散列表。(2)分別計算等概率情況下查找成功和查找不成功的平均查找長度。Ans：(1).首先明確一個概念裝載因子，裝載因子是指所有關(guān)鍵子填充哈希表后飽和的程度，它等于關(guān)鍵字總數(shù)/哈希表的長度。根據(jù)題意，我們可以確定哈希表的長度為L=7

5、/0.7=10;因此此題需要構(gòu)建的哈希表是下標(biāo)為09的一維數(shù)組。根據(jù)散列函數(shù)可以得到如下散列函數(shù)值表。H(Key)=(keyx3)MOD7,例如key=7時，H(7)=(7x3)%7=21%7=0其他關(guān)鍵字同理。Key78301118914H(Key)0365560(表1)采用線性探測再散列法處理沖突，所構(gòu)造的散列表為：地址0123456789關(guān)鍵字71481130189(表2)下面對散列表的構(gòu)造方式加以說明，注意表1中的關(guān)鍵字7和14,30和9,11和18,這三組關(guān)鍵子的H(Key)值相同，這在構(gòu)建散列表時就會產(chǎn)生沖突，因?yàn)樗麄兊牡刂废嗤砸ㄟ^一定的沖突處理方法來解決這個問題。依題，采

6、用線性探測再散列法處理沖突。下面詳細(xì)介紹如何構(gòu)建散列表：第一個key7,它的地址是0,因此放到散列表的數(shù)組下表為0的位置，這個位置上沒有關(guān)鍵字，因此沒有沖突可以直接填入；第二個key8,它的地址是3,因此放到散列表的數(shù)組下表為3的位置，這個位置上沒有關(guān)鍵字，因此沒有沖突可以直接填入；第三個key30,它的地址是6,因此放到散列表的數(shù)組下表為6的位置,這個位置上沒有關(guān)鍵字，因此沒有沖突可以直接填入；第四個key11,它的地址是5,因此放到散列表的數(shù)組下表為5的位置,這個位置上沒有關(guān)鍵字，因此沒有沖突可以直接填入；第五個key18,它的地址是5,因此放到散列表的數(shù)組下表為5的位置,但這個位置上已經(jīng)

7、有關(guān)鍵字11,遇到了沖突，此時我們根據(jù)線性探測再散列法來處理這個沖突，探測下一個位置6,6這個位置上已經(jīng)存在關(guān)鍵字30則繼續(xù)增加步長1,因此現(xiàn)在的新地址應(yīng)為7,位置7上沒有關(guān)鍵字，放入即可，到此沖突已經(jīng)解決；第六個key9,它的地址是6,因此放到散列表的數(shù)組下表為6的位置，但這個位置上已經(jīng)有關(guān)鍵字30,遇到了沖突，探測下一個位置7,7這個位置上已經(jīng)存在關(guān)鍵字18則繼續(xù)增加步長1,因此現(xiàn)在的新地址應(yīng)為8,位置8上沒有關(guān)鍵字，放入即可；第七個key14,它的地址是0,因此放到散列表的數(shù)組下表為0的位置,但這個位置上已經(jīng)有關(guān)鍵字7,遇到了沖突，探測下一個位置1,位置1上沒有關(guān)鍵字，放入即可；到這一步

8、所有關(guān)鍵字均已填入，散列表已經(jīng)構(gòu)造完成，如表2所示。（2）等概率情況下查找成功平均查找長度：這一問可以根據(jù)第一問的構(gòu)造過程求解：key7一次就填入了表中，因此查找次數(shù)為1,同理8,30,11查找次數(shù)均為1;key18進(jìn)行了3次放入操作，探測位置分別是5,6,7,因此查找次數(shù)為3;key9也是3次；key14進(jìn)行了兩次探測，因此查找次數(shù)為2。次數(shù)表如表3所小Key78301118914Count1111332（表3）所以ASLsuccess=（1+1+1+1+3+3+2/7=12/7。等概率情況下查找不成功的平均查找長度：接下來討論不成功的情況，看表2,計算查找不成功的次數(shù)就直接找關(guān)鍵字到第一個

9、地址上關(guān)鍵字為空的距離即可，但根據(jù)哈希函數(shù)地址為MOD7因此初始只可能在06的位置。等概率情況下，查找06位置查找失敗的查找次數(shù)為：看地址0,到第一個關(guān)鍵字為空的地址2的距離為3,因此查找不成功的次數(shù)為3.地址1,到第一個關(guān)鍵為空的地址2的距離為2,因此查找不成功的次數(shù)為2.地址2,到第一個關(guān)鍵為空的地址2的距離為1,因此查找不成功的次數(shù)為1.地址3,到第一個關(guān)鍵為空的地址4的距離為2,因此查找不成功的次數(shù)為2.地址4,到第一個關(guān)鍵為空的地址4的距離為1,因此查找不成功的次數(shù)為1.地址5,到第一個關(guān)鍵為空的地址2（注意不是地址9,因?yàn)槌跏贾豢赡茉?6之間，因此循環(huán)回去）的距離為5,因此查找不成

10、功的次數(shù)為5.地址6,到第一個關(guān)鍵為空的地址2（注意不是地址9,因?yàn)槌跏贾豢赡茉?6之間，因此循環(huán)回去）的距離為4,因此查找不成功的次數(shù)為4.因此查找不成功的次數(shù)表如下表所示Key78301118914Count3212154（表4）所以ASLunsuccess=（3+2+1+2+1+5+4/7=18/7。哈希表鏈地址法平均查找長度十二月28th,2010Mr.li1796 chaining DS HashTable哈希函數(shù)為：H（key）=keymod11關(guān)鍵字為：1131234383327221mod11=1所以數(shù)據(jù)1是屬于地址113mod11=2所以數(shù)據(jù)13是屬于地址212mod11=1

11、所以數(shù)據(jù)12也是屬于地址1（這個數(shù)據(jù)是數(shù)據(jù)1指針的另一個新數(shù)據(jù)）34mod11=1所以數(shù)據(jù)34是屬于地址1（這個數(shù)據(jù)是數(shù)據(jù)12指針的另一個新數(shù)據(jù)）38mod11=5所以數(shù)據(jù)38是屬于地址533mod11=0所以數(shù)據(jù)33是屬于地址027mod11=5所以數(shù)據(jù)27是屬于地址5,（這個數(shù)據(jù)是數(shù)據(jù)38指針的另一個新數(shù)據(jù)）22mod11=0所以數(shù)據(jù)22是屬于地址0,（這個數(shù)據(jù)是數(shù)據(jù)33指針的另一個新數(shù)據(jù)）鏈地址法處理沖突構(gòu)造所得的哈希表如下:0->22->33A1->1->12->34A2->13A3A4A5->27->38A6A7A8A9A10a查找成功

12、時：ASL=(1X4+2X3+3X1)/8=13/8其中紅色標(biāo)記為查找次數(shù)。也就是說，需查找1次找到的有4個，其它以此類推查找不成功時：ASL=(3+4+2+1+1+3+1+1+1+1+1)/11=19/11以第一個3為例，其對應(yīng)于0地址位，確定查找不成功需比較3次，其它以此類推.鏈?zhǔn)教幚頉_突怎么求不成功的平均查找長度1 346723 584 2648815 9367 6889 75這個貌似不同的教材有不同的計算結(jié)果，不過運(yùn)算方法是相同的。第一列的數(shù)據(jù)時需要比較一次的，包括34、58、26等以及2、6、8這三個位置。其中除了這三個位置外是查找成功比較一次，而這三個位置是查賬不成功的。另外，3、

13、5、7、9這幾個位置是需要比較兩次才知道查找不成功的；同理，1位置查找不成功比較3次，4位置比較4次。所以有ASL=(1X3+2X4+3X1+4X1)/9=18/9下面看下2010年2010年全國碩士研究生入學(xué)統(tǒng)一考試計算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題中一個考哈希表的題。Question1:將關(guān)鍵字序列(7、8、30、11、18、9、14)散列存儲到散列表中。散列表的存儲空間是一個下標(biāo)從0開始的一維數(shù)組，散列函數(shù)為：H(key)=(keyx3)MOD7處理沖突采用線性探測再散列法，要求裝填(載)因子為0.7。(1)請畫出所構(gòu)造的散列表。(2)分別計算等概率情況下查找成功和查找不

14、成功的平均查找長度。Ans：(1),首先明確一個概念裝載因子，裝載因子是指所有關(guān)鍵子填充哈希表后飽和的程度，它等于關(guān)鍵字總數(shù)/哈希表的長度。根據(jù)題意，我們可以確定哈希表的長度為L=7/0,7=10;因此此題需要構(gòu)建的哈希表是下標(biāo)為09的一維數(shù)組。根據(jù)散列函數(shù)可以得到如下散列函數(shù)值表。H(Key)=(keyx3)MOD7,例如key=7時，H(7)=(7x3)%7=21%7=0,其他關(guān)鍵字同理。Key78301118914H（Key）0365560（表1）采用線性探測再散列法處理沖突，所構(gòu)造的散列表為:地址0123456789關(guān)鍵字71481130189（表2）下面對散列表的構(gòu)造方式加以說明，注

15、意表1中的關(guān)鍵字7和14,30和9,11和18,這三組關(guān)鍵子的H(Key)值相同，這在構(gòu)建散列表時就會產(chǎn)生沖突，因?yàn)樗麄兊牡刂废嗤砸ㄟ^一定的沖突處理方法來解決這個問題。依題，采用線性探測再散列法處理沖突。下面詳細(xì)介紹如何構(gòu)建散列表：第一個key7,它的地址是0,因此放到散列表的數(shù)組下表為沒有關(guān)鍵字，因此沒有沖突可以直接填入；0的位置，這個位置第二個key8,它的地址是3,因此放到散列表的數(shù)組下表為沒有關(guān)鍵字，因此沒有沖突可以直接填入；3的位置，這個位置上第三個key30,它的地址是6,因此放到散列表的數(shù)組下表為上沒有關(guān)鍵字，因此沒有沖突可以直接填入；6的位置，這個位置第四個key11,

16、它的地址是5,因此放到散列表的數(shù)組下表為上沒有關(guān)鍵字，因此沒有沖突可以直接填入；5的位置，這個位置第五個key18,它的地址是5,因此放到散列表的數(shù)組下表為5的位置，但這個位置上已經(jīng)有關(guān)鍵字11,遇到了沖突，此時我們根據(jù)線性探測再散列法來處理這個沖突，探測下一個位置6,6這個位置上已經(jīng)存在關(guān)鍵字30則繼續(xù)增加步長1,因此現(xiàn)在的新地址應(yīng)為7,位置7上沒有關(guān)鍵字，放入即可，到此沖突已經(jīng)解決；第六個key9,它的地址是6,因此放到散列表的數(shù)組下表為6的位置，但這個位置上已經(jīng)有關(guān)鍵字30,遇到了沖突，探測下一個位置7,7這個位置上已經(jīng)存在關(guān)鍵字18則繼續(xù)增加步長1,因此現(xiàn)在的新地址應(yīng)為8,位置8上沒有

17、關(guān)鍵字，放入即可；第七個key14,它的地址是0,因此放到散列表的數(shù)組下表為0的位置，但這個位置上已經(jīng)有關(guān)鍵字7,遇到了沖突，探測下一個位置1,位置1上沒有關(guān)鍵字，放入即可；到這一步所有關(guān)鍵字均已填入，散列表已經(jīng)構(gòu)造完成，如表2所示。(2)等概率情況下查找成功平均查找長度：這一問可以根據(jù)第一問的構(gòu)造過程求解：key7一次就填入了表中，因此查找次數(shù)為1,同理8,30,11查找次數(shù)均為1;key18進(jìn)行了3次放入操作，探測位置分別是5,6,7,因此查找次數(shù)為3;key9也是3次；key14進(jìn)行了兩次探測，因此查找次數(shù)為2。次數(shù)表如表3所示Key78301118914Count1111332(表3)所以ASLsuccess=(1+1+1+1+3+3+2)/7=12/7。等概率情況下查找不成功的平均查找長度：接下來討論不成功的情況，看表2,計算查找不成功的次數(shù)就直接找關(guān)鍵字到第一個地址上關(guān)鍵字為空的距離即可，但根據(jù)哈希函數(shù)地址為MOD7因此初始只可能在06的位置。等概率情況下，查找06位置查找失敗的查找次數(shù)為：看地址0,到第一個關(guān)鍵字為空的地址2的距離為3,因此查找不成功的次數(shù)為3.地址1,到第一個關(guān)鍵為空的地址2的距離為2,因此查找不成功的次數(shù)為2.地址2,到第一個關(guān)鍵為空的地址2的距離為1,因此查找不成功的次數(shù)為1.