[理學(xué)]第二十五講哈希表查找(已修改)
2025-10-23 21:28 本頁(yè)面
【正文】 第二十五講 哈 希 表 查 找 重點(diǎn)： 了解哈希表的概念。 掌握構(gòu)造哈希函數(shù)的常見方法。 掌握在構(gòu)造哈希函數(shù)的過程中，解 決沖突的方法。 哈希表的概念 在前面講過的幾種查找方法中，都是在結(jié) 構(gòu)中查找記錄時(shí)需要進(jìn)行一系列和關(guān)鍵字的比 較。查找的效率依賴于查找過程中所進(jìn)行的比 較次數(shù)。 ? 理想的情況是希望不經(jīng)過任何比較，一次 存取便能夠得到所查記錄，那就必須在記錄的 存儲(chǔ)位置上和它的關(guān)鍵字之間建立一個(gè)確定的 對(duì)應(yīng)關(guān)系 f， 使每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一 的存儲(chǔ)位置相對(duì)應(yīng)。因而在查找時(shí)，只要根據(jù) 這個(gè)對(duì)應(yīng)關(guān)系 f找到給定值 k的的映像 f(k)。若 結(jié)構(gòu)中存在關(guān)鍵字和 k相等的記錄，則必定在 f(k)的存儲(chǔ)位置上，由此， 不需要進(jìn)行比較 便 可直接 取得所查記錄。在此，我們稱這個(gè)對(duì)應(yīng) 關(guān)系 f為哈希函數(shù) ， 按這個(gè)思想建立的表為哈 希表。 而 使用哈希表進(jìn)行查找的方法稱為哈希查找。 因此，其查找時(shí)間與計(jì)算地址的函數(shù)有關(guān)。 假設(shè) table是一個(gè)包含 n個(gè)元素的線性表， Ri 為表中的某個(gè)元素（ 1=i=n）， keyi是其關(guān)鍵 字值，若在關(guān)鍵字值 keyi與元素 Ri的地址（即 在線性表中的位置）之間建立某種函數(shù)關(guān)系， 則可以通過這個(gè)函數(shù)，把關(guān)鍵字值轉(zhuǎn)換成相應(yīng) 元素在表中的地址，即 Addr(Ri)=H(keyi) 其中， Addr(Ri)為 Ri的地址，函數(shù) H 稱為哈希 （ Hash） 函數(shù)（散列函數(shù)）， 稱 H(keyi) 的值為哈希地址（散列地址）。 哈希查找的基本思想： 確定將關(guān)鍵字值轉(zhuǎn)換成存儲(chǔ)位置的函數(shù) H， 以記錄中關(guān)鍵字值 K為自變 量，對(duì)應(yīng)的 函 數(shù)值 H（ K） 作為其記錄的存儲(chǔ)地址將其存到 相應(yīng)的位置中。查找時(shí)，通過函數(shù) H計(jì)算得到 待查找記錄的存儲(chǔ)位置。 在進(jìn)行查找之前，我們先來(lái)了解如何構(gòu)造哈希表。 例如：假定一個(gè)線性表為 S={18， 75， 60， 43， 54， 90， 46， 67} 將其存儲(chǔ)到數(shù)組 H[13]中，如下圖所示： 0 1 2 3 4 5 6 7 8 9 10 11 12 54 67 43 18 46 60 75 90 H 表一 哈希表 H[13] 若哈希函數(shù)定義為 H（ key） =key%13,則查找 過程就是一個(gè)求 H（ key） 的值的過程，如查找 75，則 H（ 75） =75%13=10， 說(shuō)明 H[10]存放著 75。若查找 90， H（ 90） =90%13=12， 說(shuō)明 H[12]存放著 90。 若根據(jù)哈希函數(shù)，把元素存放到線性表中相 應(yīng)的位置上，這樣形成的表便稱為 哈希表 ，又 叫 散列表。 哈希表的查找是以同樣的方式進(jìn)行 的。 若某個(gè)哈希函數(shù)對(duì)于不同的關(guān)鍵字值 key1和 key2， 得到相同的散列地址， 即 H（ key1） = H（ key2）， 這種現(xiàn)象稱為沖 突。例如： H（ 54） =H（ 67） =2， 說(shuō)明 54和 67在存放時(shí)發(fā)生沖突，即 54和 67都要存放到 H[2]中，這就需要有辦法來(lái)處理沖突，發(fā)生 沖突的關(guān)鍵字對(duì)該哈希函數(shù) H（ key） 來(lái)說(shuō)稱 為是 同義詞。 解決沖突就是為對(duì)應(yīng)到同一地址的多個(gè)同 義詞安排存儲(chǔ)位置，因此，在選定哈希函數(shù)時(shí) 應(yīng)考慮避免沖突，也就是說(shuō)，一個(gè)好的哈希函 數(shù)能將關(guān)鍵字值均勻地分布在整個(gè)地址空間， 使產(chǎn)生沖突機(jī)會(huì)盡量減少，同時(shí)，選定一個(gè)解 決沖突的方法，即對(duì)同義詞再次找到一個(gè)空間 地址，存放該元素。 綜上所述， 哈希表是根據(jù)設(shè)定的哈希函 數(shù)和解決沖突的方法，為一組元素建立一張 表，每個(gè)元素在表中的位置依賴于設(shè)定的哈 希函數(shù)和
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1