構(gòu)造哈希表以及二次探測法

1、構(gòu)造哈希表以及二次探測法今天做筆試題時，遇到一道構(gòu)造哈希表的題，hash函數(shù)是k%11，然后一個數(shù)組記不清了，然后就是問二次探測法進行，問下面那個是正確，懵逼啊，沒做過，不知道，亂選直接下一題，于是有這個博客，趕緊學習一波。網(wǎng)上查詢了一下。構(gòu)造哈希表的幾種方法常用方法是直接定址法和除留余數(shù)法。直接定址法(取關(guān)鍵字的某個線性函數(shù)為哈希地址)類似于這樣的式子f(key)=axkey+b“除留余數(shù)法(取關(guān)鍵值被某個不大于散列表長m的數(shù)p除后的所得的余數(shù)為散列地址)對于散列表長為m的散列函數(shù)公式為：f(key)=keymodp(pm)mod是取模(求余數(shù))的意思。事實上，這方法不僅可以對關(guān)鍵字直接取模

2、，也可在折疊、平方取中后再取模。平方取中法折疊法隨機數(shù)法數(shù)學分析法哈希沖突(碰撞)以及處理哈希沖突：既然有哈希函數(shù)Hash(key)，在有限的空間里，肯定會產(chǎn)生相同的的值(哈希地址)，我們稱這種情況為哈希沖突(碰撞)。任意的散列函數(shù)都不能避免產(chǎn)生沖突。1.開發(fā)定址法所謂的開放定址法就是一旦發(fā)生了沖突，就去尋找下一個空的散列地址，只要散列表足夠大，空的散列地址總能找到，并將記錄存入。線性探測法fi(key)=(f(key)+di)MODm(di=1,2,3,m-1)用開放定址法解決沖突的做法是：當沖突發(fā)生時，使用某種探測技術(shù)在散列表中形成一個探測序列。沿此序列逐個單元地查找，直到找到給定的關(guān)鍵字

3、，或者碰到一個開放的地址(即該地址單元為空)為止(若要插入，在探查到開放的地址，則可將待插入的新結(jié)點存人該地址單元)。查找時探測到開放的地址則表明表中無待查的關(guān)鍵字，即查找失敗。ep:我們的關(guān)鍵字集合為12,67,56,16,25,37,22,29,15,47,48,34,表長為12。我們用散列函數(shù)f(key)=keymod12。當計算前S個數(shù)12,67,56,16,25時，都是沒有沖突的散列地址，直接存入：口；01234567891011計算key=37時，發(fā)現(xiàn)f(37)=1此時就與25所在的位置沖突。于是我們應(yīng)用上面的公式f(37)=(f(37)+1)mod12=2。于是將37存入為2的下

4、標位置。卜標01234567891011鼻.-1&到了key=48,我們計算得f(48)=0,與12所在的0位置沖突了，不要緊，我們f(48)=(f(48)+1)mod12=1,此時又與25所在的位置沖突。于是f(48)=(f(48)+2)mod12=2,還是沖突一直到f(48)=(f(48)+6)mod12=6時，存入該位置：F標012345678910117亠*KAJAWJiEKJft#-w我們把這種解決沖突的開放定址法稱為線性探測法。:二次探測法考慮深一步，如果發(fā)生這樣的情況，當最后一個key=34,f(key)=10,與22所在的位置沖突，可是22后面沒有空位置了，反而它的前面有一個空

5、位置,盡管可以不斷地求余數(shù)后得到結(jié)果,但效率很差。因此我們可以改進di=12,-12,22,-22,q2,-q2(q=m/2),這樣就等于是可以雙向?qū)ふ业娇赡艿目瘴恢?。對?4來說，我們?nèi)i即可找到空位置了。另外增加平方運算的目的是為了不讓關(guān)鍵字都聚集在某一塊區(qū)域。我們稱這種方法為二次探測法。f(key)=(f(key)+di)MODm(di=1A2,-1A2,2A2,-2A2,qA2,-qA2,q=m/2)注：1八2表示是1的平方。2鏈地址法前面我們談到了散列沖突處理的開放定址法，它的思路就是一旦發(fā)生了沖突，就去尋找下一個空的散列地址。那么，有沖突就非要換地方呢，我們直接就在原地處理行不行呢？