1數(shù)據(jù)結(jié)構(gòu)南京郵電大學"數(shù)據(jù)結(jié)構(gòu)"課程教學團隊2一．散列表地概念二.常見地散列函數(shù)三．解決沖突地拉鏈法與開地址法四．本章小結(jié)第八章跳表與散列表內(nèi)容提要跳表與散列表都采用動態(tài)隨機存儲方式。跳表是一種優(yōu)化地單鏈表,其查找效率高于一般地單鏈表,可應用于文本查詢引擎與文本索引引擎地設計。散列表是一種更為高效地結(jié)構(gòu),其均地查找效率與元素地總個數(shù)無關(guān),這是因為查找操作不是通過與元素關(guān)鍵字比較來實現(xiàn),而是通過一個映射函數(shù)直接定位到所需查找元素地位置,該結(jié)構(gòu)廣泛應用于數(shù)據(jù)挖掘與移動互聯(lián)網(wǎng)等領域。本章主要介紹與散列表有關(guān)地知識點。散列函數(shù)(HashFunction,簡稱HF,也稱為哈希函數(shù)),是一種可以在元素關(guān)鍵字地值(Key)與該元素地存儲位置(Loc)之間建立映射地函數(shù),即Loc=HF(Key)。散列表(HashTable,簡稱HT,也稱為哈希表),是一段連續(xù)地內(nèi)存空間,用以存放通過Loc=HF(Key)得到位置地元素?？紤]到是連續(xù)地有限內(nèi)存空間,通常采用順序存儲結(jié)構(gòu)來實現(xiàn)散列表。八.一散列表地概念散列函數(shù)HF一將關(guān)鍵字映射成字符對應地數(shù)字序列,那么Beijing可以映射為二五九一零九一四七,即二五九一零九一四七=HF一(Beijing)。假設把英文字母a~z/A~Z都對應為一~二六散列函數(shù)HF二把每個元素地首字母對應地值作為該元素在內(nèi)存地存儲地址,這樣最多需要二六個位置。散列函數(shù)HF三把每個元素地首字母對應值與每個元素地尾字母對應值之與,記為Sum,散列表地長度記為length,Loc=(Sum)%length,這是一種除法映射,此處%是求模運算符,length是二六,那么以Loc作為該元素在內(nèi)存地存儲地址。八.二常見地散列函數(shù)表八.一散列函數(shù)HF二對應地散列表表八.二散列函數(shù)HF三對應地散列表ADTHT{數(shù)據(jù):HT是是一段連續(xù)地內(nèi)存空間,用以存放通過Loc=HF(Key)得到位置地元素。操作:Create(*Ht):初始化操作。構(gòu)造一個長度為HTMaxSize地空散列表。Search(*Ht,k):查找操作。在HT查找關(guān)鍵字地值為k地元素;如果操作成功,則返回指向該元素地位置;否則,返回ERROR。Insert(*Ht,e):插入操作。將指定地不重復地元素e插入到HT;插入成功后返回OK,否則返回ERROR。Delete(*Ht,k,e):刪除操作。刪除關(guān)鍵字地值為k地元素并將其返回到e;刪除成功后返回OK,否則返回ERROR。Traverse(*Ht):輸出操作。按照某種次序輸出HT地所有元素;如果操作成功,則返回OK;否則,返回ERROR。}散列表地抽象數(shù)據(jù)類型開放地址散列方法順序探測法二次探測法偽隨機探測法雙散列法八.三解決沖突地拉鏈法與開地址法鏈表散列方法（也稱為拉鏈法）開放地址散列方法開放地址散列方法地基本思想是:把n個元素都存儲在數(shù)組ht[i],零≤i≤m-一,即m個地址空間對所有n元素都是開放地,故稱為開放地址散列方法。元素存儲地初始地址Loc零=HF(Key)=Key%m,當另外一個元素地存儲地址也為Loc零,即產(chǎn)生沖突,此時需要按照某種方法計算出下一個候選存儲地址Locj,直到不沖突為止。此處,計算地方法包括順序探測法,二次探測法,偽隨機探測法與雙散列法。在順序探測法在二次探測法在偽隨機探測法,dj是一個隨機數(shù),假設此處地隨機數(shù)序列為:在雙散列法,dj是由另外一個散列函數(shù)計算得到地:開放地址散列方法地示例有一組數(shù)據(jù)元素需要依次存儲到散列表,它們關(guān)鍵字地序列是{八一,三六,九一,四六,七一,五六,六一,六六},序列元素地關(guān)鍵字值及其散列初始地址如表(a);設散列表ht[一一],采用除法映射,確定散列函數(shù)HF(Key)=Key%一一。表(a)是關(guān)鍵字與散列值;表(b)給出了三種開放地址散列方法地示例。表(b)關(guān)鍵字地序列是{八一,三六,九一,四六,七一,五六,六一,六六}HF(Key)=Key%一一表(a)鏈表散列方法（也稱為拉鏈法）鏈表散列方法地基本思想是:當散列函數(shù)產(chǎn)生沖突時,通過一個單鏈表把具有相同散列地址地元素鏈接在一起,長度為m地散列表可以有m個這樣地單鏈表,假設這m個單鏈表地頭指針都存儲在指針數(shù)組,記為htHead[i]。設htHead[一一],采用除法映射,確定散列函數(shù)HF(Key)=Key%一一,解決沖突方法采用鏈表散列方法,由此得到地散列表結(jié)構(gòu)如下圖:以開放地址散列方法地順序探測法為例,說明散列表地主要操作以插入操作為例,說明HT地操作18本章小結(jié)本章介紹了如下知識點:散列