數(shù)據(jù)結(jié)構(gòu)教程第三十三課哈希表（二）

教學(xué)目的： 掌握哈希表處理沖突的方法及哈希表的查找算法
    教學(xué)重點(diǎn)： 哈希表處理沖突的方法
    教學(xué)難點(diǎn)： 開(kāi)放定址法
    授課內(nèi)容：
    一、復(fù)習(xí)上次課內(nèi)容
    什么是哈希表？如何構(gòu)造哈希表？
    提出問(wèn)題：如何處理沖突？
    二、處理沖突的方法
     成績(jī)一 成績(jī)二...
    3 ...
    ... ...
    24 劉麗 82 95
    25 ...
    26 陳偉
    ... ...
    33 吳軍
    ... ...
    42 李秋梅
    ... ...
    46 劉宏英
    ... ...
    72 吳小艷
    ... ...
    78 ...
    如果兩個(gè)同學(xué)分別叫 劉麗 劉蘭，當(dāng)加入劉蘭時(shí)，地址24發(fā)生了沖突，我們可以以某種規(guī)律使用其它的存儲(chǔ)位置，如果選擇的一個(gè)其它位置仍有沖突，則再選下一個(gè)，直到找到?jīng)]有沖突的位置。選擇其它位置的方法有：
    １、開(kāi)放定址法
    Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1)
    其中m為表長(zhǎng)，di為增量序列
    如果di值可能為1,2,3,...m-1，稱(chēng)線性探測(cè)再散列。
    如果di取值可能為1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2)
    稱(chēng)二次探測(cè)再散列。
    如果di取值可能為偽隨機(jī)數(shù)列。稱(chēng)偽隨機(jī)探測(cè)再散列。
    例：在長(zhǎng)度為11的哈希表中已填有關(guān)鍵字分別為17,60,29的記錄，現(xiàn)有第四個(gè)記錄，其關(guān)鍵字為38，由哈希函數(shù)得到地址為5，若用線性探測(cè)再散列，如下：
    0 1 2 3 4 5 6 7 8 9 10
     60 17 29
    (a)插入前
    0 1 2 3 4 5 6 7 8 9 10
     60 17 29 38
    (b)線性探測(cè)再散列
    0 1 2 3 4 5 6 7 8 9 10
     60 17 29
    (c)二次探測(cè)再散列
    0 1 2 3 4 5 6 7 8 9 10
     38 60 17 29
    (d)偽隨機(jī)探測(cè)再散列
    偽隨機(jī)數(shù)列為9,5,3,8,1...
    ２、再哈希法
    當(dāng)發(fā)生沖突時(shí)，使用第二個(gè)、第三個(gè)、哈希函數(shù)計(jì)算地址，直到無(wú)沖突時(shí)。缺點(diǎn)：計(jì)算時(shí)間增加。
    ３、鏈地址法
    將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在同一線性鏈表中。
    ４、建立一個(gè)公共溢出區(qū)
    假設(shè)哈希函數(shù)的值域?yàn)閇0,m-1],則設(shè)向量HashTable[0..m-1]為基本表，另外設(shè)立存儲(chǔ)空間向量OverTable[0..v]用以存儲(chǔ)發(fā)生沖突的記錄。
    三、哈希表的查找
    //開(kāi)放定址哈希表的存儲(chǔ)結(jié)構(gòu)
    int hashsize[]={997,...};
    typedef struct{
    ElemType *elem;
    int count;
    int sizeindex;
    }HashTable;
    #define SUCCESS 1
    #define UNSUCCESS 0
    #define DUPLICATE -1
    Status SearchHash(HashTable H,KeyType K,int &p,int &c){
    p=Hash(K);
    while(H.elem[p].key!=NULLKEY && !EQ(K,H.elem[p].key))
    collision(p,++c);
    if(EQ(K,H.elem[p].key)
    return SUCCESS;
    else return UNSUCCESS;
    }
    Status InsertHash(HashTable &H,EleType e){
    c=0;
    if(SearchHash(H,e.key,p,c))
    return DUPLICATE;
    else if(cH.elem[p]=e; ++H.count; return OK;
    }
    else RecreateHashTable(H);
    }
    四、總結(jié)
    處理沖突的要求是什么？