資源描述：
《數(shù)據(jù)結(jié)構(gòu)26-哈希表(一)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、數(shù)據(jù)結(jié)構(gòu)第二十六課哈希表（一）第四十課哈希表（一）本課主題：哈希表（一）教學(xué)目的：掌握哈希表的概念作用及意義，哈希表的構(gòu)造方法教學(xué)重點(diǎn)：哈希表的構(gòu)造方法教學(xué)難點(diǎn)：哈希表的構(gòu)造方法授課內(nèi)容：一、哈希表的概念及作用1.散列函數(shù)的提出從前講的檢索，都是用待檢索的關(guān)鍵字和各記錄的關(guān)鍵字比較，若相等，則檢索成功，否則，繼續(xù)比較。我們希望找到一個(gè)函數(shù)，對(duì)關(guān)鍵字進(jìn)行計(jì)算，把函數(shù)值解釋為記錄的存儲(chǔ)地址，這就是散列檢索。所用的函數(shù)就叫散列函數(shù)。用散列法存儲(chǔ)的線性表叫散列表。查找時(shí)也用同樣方法計(jì)算地址，到相應(yīng)單元去找記錄。若找到，則查找成功；若該單元無記錄，則查找失敗；若該單元有記錄，但不是所找，要
2、繼續(xù)查找。這種方法也稱關(guān)鍵字-地址轉(zhuǎn)換法。哈希表最常見的例子是以學(xué)生學(xué)號(hào)為關(guān)鍵字的成績表，１號(hào)學(xué)生的記錄位置在第一條，１０號(hào)學(xué)生的記錄位置在第１０條...如果我們以學(xué)生姓名為關(guān)鍵字，如何建立查找表，使得根據(jù)姓名可以直接找到相應(yīng)記錄呢？最小值可能為3最大值可能為78可放75個(gè)學(xué)生用上述得到的數(shù)值作為對(duì)應(yīng)記錄在表中的位置，得到右表：上面這張表即哈希表。如果將來要查李秋梅的成績，可以用上述方法求出該記錄所在位置：李秋梅:lqm12+17+13=42取表中第42條記錄即可。問題：如果兩個(gè)同學(xué)分別叫劉麗和劉蘭該如何處理這兩條記錄？這個(gè)問題是哈希表不可避免的，即沖突現(xiàn)象：對(duì)不同的關(guān)鍵字可能得
3、到同一哈希地址。散列檢索的術(shù)語根據(jù)設(shè)定的散列函數(shù)h(key)和處理沖突的方法，將一組關(guān)鍵字映象到一個(gè)有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“象”作為記錄在表中的存儲(chǔ)位置，這種表稱為散列表，這一映象過程叫散列（或哈希造表），所得存儲(chǔ)地址稱散列地址或哈希地址。碰撞（沖突）：兩個(gè)關(guān)鍵字不同，但其散列函數(shù)值相同，即key1<>key2，f(key1)=f(key2)。沖突是不可避免的，舉標(biāo)識(shí)符的例子。1939年davenport的“生日悖論”。同義詞：發(fā)生碰撞（沖突）的關(guān)鍵字稱為同義詞。負(fù)載因子：定義為?=（散列表中結(jié)點(diǎn)的數(shù)目）/（散列表的長度）?一般取0.6~0.9采用散
4、列表著重考慮兩個(gè)問題：選擇一個(gè)好的散列函數(shù)；選擇一種解決碰撞（沖突）的方法。二、散列函數(shù)的構(gòu)造方法１、直接定址法例如：有一個(gè)從1到100歲的人口數(shù)字統(tǒng)計(jì)表，其中，年齡作為關(guān)鍵字，哈希函數(shù)取關(guān)鍵字自身。２、數(shù)字分析法分析關(guān)鍵字的各位，去掉分布不均勻的位，留下均勻的位作為地址。有學(xué)生的生日數(shù)據(jù)如下：年.月.日75.10.03 75.11.23 76.03.02 76.07.12 75.04.21 76.02.15...經(jīng)分析,第一位，第二位，第三位重復(fù)的可能性大，取這三位造成沖突的機(jī)會(huì)增加，所以盡量不取前三位，取后三位比較好。３、平方取中法關(guān)鍵字平方后取中間幾位為哈希地址。４、折疊法
5、關(guān)鍵字位數(shù)較多，分布均勻，用折疊法。折疊法又分為移位折疊和間界折疊。例如：每一種西文圖書都有一個(gè)國際標(biāo)準(zhǔn)圖書編號(hào)，它是一個(gè)10位的十進(jìn)制數(shù)字，若要以它作關(guān)鍵字建立一個(gè)哈希表，當(dāng)館藏書種類不到10,000時(shí)，可采用此法構(gòu)造一個(gè)四位數(shù)的哈希函數(shù)。如果一本書的編號(hào)為0-442-20586-4,則：５、除余法取關(guān)鍵字被某個(gè)不大于哈希表表長m的數(shù)p除后所得余數(shù)為哈希地址。H(key)=keyMODp(p<=m)６、隨機(jī)數(shù)法選擇一個(gè)隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的哈希地址，即H(key)=random(key),其中random為隨機(jī)函數(shù)。通常用于關(guān)鍵字長度不等時(shí)采用此法。7﹑基數(shù)轉(zhuǎn)換法
6、將一個(gè)小基數(shù)的數(shù)看作大基數(shù)的數(shù)，再轉(zhuǎn)換為小基數(shù)的數(shù)。如key=(215874)10,將其看作以13為基數(shù)，再轉(zhuǎn)化為相應(yīng)的十進(jìn)制數(shù)。（215874）13=（783579）10，再進(jìn)行數(shù)字分析，選2,3,4,5位，得h(215874)=8357。三、總結(jié)哈希表的優(yōu)缺點(diǎn)回目錄上一課下一課
