第二十六講哈希表及其查找-wenkub.com
2024-08-31 14:57 本頁(yè)面
【正文】 實(shí)際 上，哈希表的平均查找長(zhǎng)度是裝填因子α的函數(shù)，只是不同處理沖突的方法有不同的函數(shù)。影響產(chǎn)生沖突多少有以下三個(gè)因素： 1. 哈希函數(shù)是否均勻； 2. 處理沖突的方法； 3. 哈希表的裝填因子。在介紹的三種處理沖突的方法中，產(chǎn)生沖突后的查找仍然是給定值與關(guān)鍵碼進(jìn)行比較的過(guò)程。 圖 拉鏈法處理沖突時(shí)的哈希表 (向鏈表中插入元素均在表頭進(jìn)行 ) 三 . 建立一個(gè)公共溢出區(qū) 設(shè)哈希函數(shù)產(chǎn)生的哈希地址集為 [0， m1]，則分配兩個(gè)表： 一個(gè)基本表 ElemType base_tbl[m]；每個(gè)單元只能存放一個(gè)元素； 一個(gè)溢出表 ElemType over_tbl[k]；只要關(guān)鍵碼對(duì)應(yīng)的哈希地址在基本表上產(chǎn)生沖突，則所有這樣的元素一律存入該表中。 di) mod m 其中： Hash(key)為哈希函數(shù) m 為哈希表長(zhǎng)度， m 要求是某個(gè) 4k+3 的質(zhì)數(shù) (k 是整數(shù) ) di 為增量序列 12， 12， 22， 22，??， q2， q2 且 q≤ (m1) 仍以上例用二次探測(cè)法處理沖突，建表如下： 0 1 2 3 4 5 6 7 8 9 10 11 22 3 47 92 16 7 29 8 △ ▲ △ △ 對(duì)關(guān)鍵碼尋找空的哈希地址只有 3 這個(gè)關(guān)鍵碼與上例不同， Hash(3)=3，哈希地址上沖突，由 H1=(Hash(3)+12) mod 11=4 仍然沖突； H2=(Hash(3)12) mod 11=2 找到空的哈希地址，存入。另外， 2 8 同樣在哈希地址上有沖突，也是由 H1找到空的哈希地址的； 而 Hash(3)=3，哈希地址上沖突，由 H1=(Hash(3)+1) mod 11=4 仍然沖突； H2=(Hash(3)+2) mod 11=5 仍然沖突； H3=(Hash(3)+3) mod 11=6 找到空的哈希地址，存入。 3 4 8 5 2 7 0 若哈希地址是兩位，則可取這四位中的任 3 4 8 6 3 0 5 意兩位組合成哈希地址，也 可以取其中兩 3 4 9 8 0 5 8 位與其它兩位疊加求和后，取低兩位作哈 3 4 7 9 6 7 1 希地址。 【例 】若關(guān)鍵碼是僅由英文字母組成的字符串，不考慮大小寫(xiě)，則每位上可能有 26 種不同的字母，所以 r=26。使用除留余數(shù)法，選取合適的 p 很重要，若哈
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1