數(shù)據(jù)結(jié)構(gòu) 第9章 查找

1、概 述 查找表：由同一類型數(shù)據(jù)元素構(gòu)成的集合。由于“集合”中的元素之間存在著完全松散的關(guān)系，因此查找表是一種非常靈便的數(shù)據(jù)結(jié)構(gòu)。 查找，也稱為檢索。在我們?nèi)粘Ｉ钪?，如查找某人的地址、電話?hào)碼；查某單位45歲以上職工等，都屬于查找范疇。我們規(guī)定查找是按關(guān)鍵字進(jìn)行的，所謂關(guān)鍵字(key)是數(shù)據(jù)元素(或記錄)中某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素。例如，描述一個(gè)考生的信息，可以包含：考號(hào)、姓名、性別、年齡、家庭住址、電話號(hào)碼、成績(jī)等關(guān)鍵字。但有些關(guān)鍵字不能唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素，而有的關(guān)鍵字可以唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素。如考生信息中，姓名不能唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素，而考號(hào)可以唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素(每個(gè)

2、考生考號(hào)是唯一的，不能相同)。我們將能唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素的關(guān)鍵字稱為主關(guān)鍵字，而其它關(guān)鍵字稱為輔助關(guān)鍵字或從關(guān)鍵字。 有了關(guān)鍵字及查找表后，我們可以給查找下一個(gè)完整的定義。所謂查找，就是根據(jù)給定的值，在一個(gè)表中查找出其關(guān)鍵字等于給定值的數(shù)據(jù)元素，若表中有這樣的元素，則稱查找是成功的，此時(shí)查找的信息為給定整個(gè)數(shù)據(jù)元素的輸出或指出該元素在表中的位置；若表中不存在這樣的記錄，則稱查找是不成功的，或稱查找失敗，并可給出相應(yīng)的提示。 因?yàn)椴檎沂菍?duì)已存入計(jì)算機(jī)中的數(shù)據(jù)所進(jìn)行的操作，所以采用何種查找方法，首先取決于使用哪種數(shù)據(jù)結(jié)構(gòu)來表示“表”，即表中結(jié)點(diǎn)是按何種方式組織的。為了提高查找速度，我們經(jīng)常使用某

3、些特殊的數(shù)據(jù)結(jié)構(gòu)來組織表（人為地加上一些關(guān)系以便按某種規(guī)則進(jìn)行查找）。因此在研究各種查找算法時(shí)，我們首先必須弄清這些算法所要求的數(shù)據(jù)結(jié)構(gòu)，特別是存儲(chǔ)結(jié)構(gòu)。 要衡量一種查找算法的優(yōu)劣，主要是看要找的值與關(guān)鍵字的比較次數(shù)，但我們將找到給定值與關(guān)鍵字的比較次數(shù)的平均值來作為衡量一個(gè)查找算法好壞的標(biāo)準(zhǔn)，對(duì)于一個(gè)含有n個(gè)元素的表，查找成功時(shí)的平均查找長(zhǎng)度可表示為ASL= ，其中i為查找第i個(gè)元素的概率，且 =1。一般情形下我們認(rèn)為查找每個(gè)元素的概率相等，ci為查找第i個(gè)元素所用到的比較次數(shù)。9.1 靜態(tài)查找表一、 順序查找查找過程：從表的一端開始逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較.i例 1 2 3 4

4、5 6 7 8 9 10 1113 5 90 21 37 88 64 75 19 56 75找64監(jiān)視哨令r0.key:=Kiiii比較次數(shù)=5比較次數(shù)：查找第n個(gè)元素： 1查找第n-1個(gè)元素：2.查找第1個(gè)元素： n查找第i個(gè)元素： n+1-i查找失?。?n+164算法分析1. 查找過程: 從n開始,依次與k進(jìn)行比較, 若相等則查找成功; 否則, 繼續(xù)進(jìn)行,直到與r0.key比較為止. 2. 算法分析: (1) 算法結(jié)構(gòu)應(yīng)由一個(gè)循環(huán)構(gòu)成; (2) 循環(huán)結(jié)束有兩種可能： 查找成功 ri.key = k 查找不成功 i = 0順序查找方法的ASL二、折半查找查找過程：每次將待查記錄所在區(qū)間縮小一

5、半適用條件：采用順序存儲(chǔ)結(jié)構(gòu)的有序表算法實(shí)現(xiàn)設(shè)表長(zhǎng)為n，low、high和mid分別指向待查元素所在區(qū)間的上界、下界和中點(diǎn),k為給定值初始時(shí)，令low=1,high=n,mid=(low+high)/2讓k與mid指向的記錄比較若k=rmid.key，查找成功若krmid.key，則low=mid+1重復(fù)上述操作，直至lowhigh時(shí)，查找失敗算法描述lowhighmid例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找211 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92

6、lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid找701 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 1

7、9 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh1185210741936判定樹：樹中每個(gè)結(jié)點(diǎn)表示一個(gè)記錄，結(jié)點(diǎn)的值為該記錄在表中的位置，稱這個(gè)描述查找過程的二叉樹為判定樹。1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92算法評(píng)價(jià)有n個(gè)結(jié)點(diǎn)的判定樹的深度為log2n+1折半查找法在查找過程中進(jìn)行的比較次數(shù)最多不超過其判定樹的深度折半查找的ASL三、 分塊查找查找過程：將表分成幾塊，塊內(nèi)無序，塊

8、間有序；先確定待查記錄所在塊，再在塊內(nèi)查找。說明：“分塊有序”指的是第二塊所有的關(guān)鍵字均大于第一塊中最大的關(guān)鍵字。 查找分為兩步: 1. 確定待查記錄所在塊; (可以用順序或折半查找) 2. 在塊內(nèi)順序查找. (只能用順序查找)適用條件：分塊有序表算法實(shí)現(xiàn)用數(shù)組存放待查記錄,每個(gè)數(shù)據(jù)元素至少含有關(guān)鍵字域建立索引表，每個(gè)索引表結(jié)點(diǎn)含有最大關(guān)鍵字域和指向本塊第一個(gè)結(jié)點(diǎn)的指針1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1822 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表查3

9、8算法描述分塊查找方法評(píng)價(jià)ASL最大最小兩者之間表結(jié)構(gòu)有序表、無序表有序表分塊有序表存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)線性鏈表順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)線性鏈表查找方法比較順序查找折半查找分塊查找9.2 動(dòng)態(tài)查找表 動(dòng)態(tài)查找表的特點(diǎn)是: 表結(jié)構(gòu)本身是在查找過程中動(dòng)態(tài)生成的。 即查找不成功時(shí)，將該記錄插入在動(dòng)態(tài)查找表中。一、二叉排序樹（Binary Sort Tree)（又稱為二叉查找樹）1、BST定義： BST或者是一棵空樹；或者是具有如下性質(zhì)的BT: 若左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；若右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；左、右子樹也為BST781006190123724

10、84553例如：2、查找過程為: 若二叉排樹為空，則查找失敗，否則，先拿根結(jié)點(diǎn)值與待查值進(jìn)行比較，若相等，則查找成功，若根結(jié)點(diǎn)值大于待查值，則進(jìn)入左子樹重復(fù)此步驟，否則，進(jìn)入右子樹重復(fù)此步驟，若在查找過程中遇到二叉排序樹的葉子結(jié)點(diǎn)時(shí)，還沒有找到待找結(jié)點(diǎn)，則查找不成功。3、二叉排序樹的基本運(yùn)算（1）二叉排序樹的建立 設(shè)已知一組待排序的數(shù)據(jù)，若要構(gòu)造出對(duì)應(yīng)的二叉排序樹，一般是采取從空樹開始，陸續(xù)插入一系列結(jié)點(diǎn)的辦法，逐步生成對(duì)應(yīng)的二叉排序樹。 首先以第一個(gè)數(shù)據(jù)構(gòu)成根結(jié)點(diǎn)，以后對(duì)應(yīng)每個(gè)數(shù)據(jù)插入一個(gè)結(jié)點(diǎn)，在插入過程中，原有的結(jié)點(diǎn)位置均不再變動(dòng)，只是將新數(shù)據(jù)結(jié)點(diǎn)作為一個(gè)葉子結(jié)點(diǎn)插入到合適的位置處，使樹中

11、任何結(jié)點(diǎn)與其左、右子樹結(jié)點(diǎn)數(shù)據(jù)之間的關(guān)系都符合二叉排序樹的要求。例如，結(jié)定關(guān)鍵字序列79，62，68，90，88，89，17，5，100，120，生成二叉排序樹過程如圖所示。（注：二叉排序樹與關(guān)鍵字排列順序有關(guān)，排列順序不一樣，得到的二叉排序樹也不一樣）79，62，68，90，88，89，17，5，100，120（2）二叉排序樹的插入 若二叉排序樹為空，則作為根結(jié)點(diǎn)插入，否則，若待插入的值小于根結(jié)點(diǎn)值，則作為左子樹插入，否則作為右子樹插入，算法描述（見課本P173）（3）二叉排序樹的刪除刪除的原則：刪除某個(gè)結(jié)點(diǎn)后仍保持BST的特性。設(shè)：被刪除結(jié)點(diǎn)為p(指針p所指結(jié)點(diǎn)）其雙親結(jié)點(diǎn)為f ,且不失一

12、般性，設(shè)p 是f 的左孩子。分三種情況討論： 若P結(jié)點(diǎn)為葉結(jié)點(diǎn)（即PL和PR均為空樹，僅需將f. lchild:=NIL 若P結(jié)點(diǎn)只有左子樹PL或只有右子樹PR ，只需 令PL或PR為f 的左子樹，即f . lchild:= p Lchild或 prchild 若p結(jié)點(diǎn)左、右子樹均不空，此時(shí)，按中序遍歷序列為：CL CQL Q SL S P PR F FR刪除P后為： CLCQL Q SL S PR F FR。cqCSLsCLFFRfPRpPQQLS對(duì)f 的左孩子有兩種處理辦法：S不動(dòng)，仍作為Q的右孩子，C代替P ，作為f的左孩子，PR作為S的右孩子;(2) S代替P，而 SL為QR ;CSL

13、CLPRQQLSFSSLCLFPRQQLC4、BST 的查找分析 BST 上查找過程與折半查找類似，是從根結(jié)點(diǎn)到所找到結(jié)點(diǎn)的一條路徑。與給定值比較次數(shù)等于該路徑長(zhǎng)度+1（即結(jié)點(diǎn)所在層次數(shù)），最大次數(shù)不超過樹的深度。 但長(zhǎng)度為n的折半查找表對(duì)應(yīng)的判定樹是唯一的。而含有n個(gè)結(jié)點(diǎn)的BST卻不唯一。459353371224 (a)(45, 24, 53, 12, 37, 93)122437455393 (b)(12, 24, 37, 45, 53, 93)ASL(a)=1/6（1+2+2+3+3+3）=14/6ASL(b)=1/6（1+2+3+4+5+6）=21/6因此，含有n個(gè)結(jié)點(diǎn)的BST的ASL和

14、樹的形態(tài)有關(guān)。最差情況是BST退化為單支樹，其深度為n，ASL=(n+1)/2 (同順序查找）。最好情況與折半查找相同，ASL=log2n 隨機(jī)情況下，平均查找長(zhǎng)度為1+4log2n 為了避免出現(xiàn)單支樹，在構(gòu)成BST的過程中可進(jìn)行“平衡化”處理。二. 平衡二叉樹 (Balanced Binary Tree), 又稱為AVL樹 1 、AVL樹定義AVL樹或者是一棵空樹，或者是具有下列性質(zhì)的BT: 左、右子樹均為AVL 且任一左、右子樹的深度之差的絕對(duì)值不超過1.稱某結(jié)點(diǎn)左子樹的深度右子樹的深度為該結(jié)點(diǎn)的平衡因子（balance factor) 2、AVL樹的特點(diǎn) AVL樹上任何結(jié)點(diǎn)的平衡因子只可

15、能為-1，0或1; AVL樹的深度與log n同數(shù)量級(jí); AVL樹的ASL也與log n同數(shù)量級(jí); 完全二叉樹一定是AVL , 當(dāng)然AVL樹不一定是完全二叉樹1001(a)0100-11-1(b)01-1002(c)結(jié)點(diǎn)中的值為該結(jié)點(diǎn)的平衡因子3、BST變?yōu)锳VL樹 例：設(shè)表的關(guān)鍵字序列為（13，24，37，90，53）,BST生成過程為：132413AVL AVL AVL旋轉(zhuǎn)372413非AVL372413AVL非AVL903724135390372413旋轉(zhuǎn)旋轉(zhuǎn)9053372413AVL3790532413(2) 調(diào)整形態(tài) (可歸納為四種) LL型平衡旋轉(zhuǎn)（順時(shí)針） 失去平衡點(diǎn)的平衡因子為

16、2, 其左孩子的平衡因子為12AaARh-11BBRBLh-1hh+1LL0AARBRh-1h-10BBLhh調(diào)整語句為： B rchild =A;A lchild =B rchild ; A bf=0B rchild=A; B bf=0 LR型平衡旋轉(zhuǎn)失去平衡點(diǎn)的平衡因子為2, 其左孩子的平衡因子為 -1ARh-12A-1BBLCLh-1h-1 h+11Chh-2CRLR0CARh-10BBLCLh-1h-1-1Ah-2CRA lchild =C rchild ; B rchild = C lchild C rchildA; C lchild B;2A2CARh-1h-2CR0BBLCLh-

17、1h-1 h h+1 RR型平衡旋轉(zhuǎn)（逆時(shí)針，與LL對(duì)稱)失去平衡點(diǎn)的平衡因子為 -2, 其右孩子的平衡因子為 -1-2AALBLh-1h-1-1BhBRRR0BBLALh-10ABRRL型平衡旋轉(zhuǎn)失去平衡點(diǎn)的平衡因子為 -2, 其右孩子的平衡因子為 1RL0CBR0AALCL-1Bh-2CR1BBRh-1-2AALh-1CLh-11Ch-2CR中序遍歷：AL A CL C CR B BR AL A CL C CR B BR(3) 為了得到平衡樹，需作如下處理 找到可能失去平衡的最小子樹的根結(jié)點(diǎn) 可能失去平衡的最小子樹的根結(jié)點(diǎn)，是離插入結(jié)點(diǎn)最近的且插入前平衡因子值0: 插入前平衡因子的絕對(duì)值0

18、 插入后平衡因子的絕對(duì)值1 離插入結(jié)點(diǎn)最近的失去平衡的祖先結(jié)點(diǎn)判別插入結(jié)點(diǎn)后可能失去平衡的最小子樹的根結(jié)點(diǎn)是否失去平衡，（該結(jié)點(diǎn)的平衡因子的絕對(duì)值1）;判別旋轉(zhuǎn)類型作相應(yīng)處理。4、AVL樹上插入結(jié)點(diǎn)算法(1) 算法描述 查找 s 結(jié)點(diǎn)的插入位置過程中，記下離s 最近的，且平衡因子不等于0的結(jié)點(diǎn)，令 a 指向該結(jié)點(diǎn)；（即可能失去平衡的最小子樹的根結(jié)點(diǎn)）。 修改 a 至 s 路徑上所有結(jié)點(diǎn)的平衡因子值； 判別a 結(jié)點(diǎn)的平衡因子絕對(duì)值是否大于1，若是，作旋轉(zhuǎn)處理5平衡二叉樹的查找及性能分析 平衡二叉樹本身就是一棵二叉排序樹，故它的查找與二叉排序樹完全相同。但它的查找 性能優(yōu)于二叉排序樹，不像二叉排序

19、樹一樣，會(huì)出現(xiàn)最壞的時(shí)間復(fù)雜度O(n)，它的時(shí)間復(fù)雜度與二叉排序樹的最好時(shí)間復(fù)雜相同，都為O(log2n)。 例 對(duì)給定的關(guān)鍵字序列4,5,7,2,1,3,6，試用二叉排序樹和平衡二叉樹兩種方法查找，給出查找6的次數(shù)及成功的平均查找長(zhǎng)度。 0 6 2 1 4 3 7 0 0 0 0 0 5 0 從二叉排序樹可知，查找6需4次，平均查找長(zhǎng)度ASL=(1+2+2+3+3+3+4)/7=18/72.57。從平衡二叉樹可知，查找6需2次，平均查找長(zhǎng)度ASL=(1+2+2+3+3+3+3)=17/72.43。從結(jié)果可知，平衡二叉樹的查找性能優(yōu)于二叉排序樹。9.3 哈希查找一、基本概念 散列查找，也稱為哈

20、希查找。它既是一種查找方法，又是一種存貯方法，稱為散列存貯。散列存貯的內(nèi)存存放形式也稱為散列表。 散列查找，與前面介紹的查找方法完全不同，前面介紹的所有查找都是基于待查關(guān)鍵字與表中元素進(jìn)行比較而實(shí)現(xiàn)的查找方法，而散列查找是通過構(gòu)造散列函數(shù)來得到待查關(guān)鍵字的地址，按理論分析真正不需要用到比較的一種查找方法。例如，要找關(guān)鍵字為k的元素，則只需求出函數(shù)值H（k），H（k）為給定的散列函數(shù)，代表關(guān)鍵字k在存貯區(qū)中的地址。例 假設(shè)有一批關(guān)鍵字序列18,75,60,43,54,90,46，給定散列函數(shù)H（k）=k%13，存貯區(qū)的內(nèi)存地址從0到15，則可以得到每個(gè)關(guān)鍵字的散列地址為： H（18）=18%13

21、=5 H（75）=75%13=10 H（60）=60%13=8 H（43）=43%13=4 H（54）=54%13=2 H（90）=90%13=12 H（46）=46%13=7于是，根據(jù)散列地址，可以將上述7個(gè)關(guān)鍵字序列存貯到一個(gè)一維數(shù)組HT（散列表）中，具體表示為： 其中HT就是散列存貯的表，稱為散列表。從散列表中查找一個(gè)元素相當(dāng)方便，例如，查找75，只需計(jì)算出H（75）=75%13=10，則可以在HT10中找到75。 上面討論的散列表是一種理想的情形，即每一個(gè)關(guān)鍵字對(duì)應(yīng)一個(gè)唯一的地址。但是有可能出現(xiàn)這樣的情形，兩個(gè)不同的關(guān)鍵字有可能對(duì)應(yīng)同一個(gè)內(nèi)存地址，這樣，將導(dǎo)致后放的關(guān)鍵字無法存貯，我們

22、把這種現(xiàn)象叫做沖突（collision）。在散列存貯中，沖突是很難避免的，除非構(gòu)造出的散列函數(shù)為線性函數(shù)。散列函數(shù)選得比較差，則發(fā)生沖突的可能性越大。我們把相互發(fā)生沖突的關(guān)鍵字互稱為“同義詞”。 在散列存貯中，若發(fā)生沖突，則必須采取特殊的方法來解決沖突問題，才能使散列查找能順利進(jìn)行。雖然沖突不可避免，但發(fā)生沖突的可能性卻與三個(gè)方面因素有關(guān)。第一是與裝填因子有關(guān)，所謂裝填因子是指散列表中己存入的元素個(gè)數(shù)n與散列表的大小m的比值，即=n/m。當(dāng)越小時(shí)，發(fā)生沖突的可能性越小，越大（最大為1）時(shí)，發(fā)生沖突的可能性就越大。但是，為了減少?zèng)_突的發(fā)生，不能將變得太小，這樣將會(huì)造成大量存貯空間的浪費(fèi)，因此必須

23、兼顧存儲(chǔ)空間和沖突兩個(gè)方面。第二是與所構(gòu)造的散列函數(shù)有關(guān)。第三是與解決沖突的方法有關(guān)。 二、 散列函數(shù)的構(gòu)造 散列函數(shù)的構(gòu)造目標(biāo)是使散列地址盡可能均勻地分布在散列空間上，同時(shí)使計(jì)算盡可能簡(jiǎn)單。具體常用的構(gòu)造方法有如下幾種： 1直接定址法 可表示為H（k）=a.k+b，其中a、b均為常數(shù)。這種方法計(jì)算特別簡(jiǎn)單，并且不會(huì)發(fā)生沖突，但當(dāng)關(guān)鍵字分布不連續(xù)時(shí)，會(huì)出現(xiàn)很多空閑單元，將造成大量存貯單元的浪費(fèi)。2數(shù)字分析法對(duì)關(guān)鍵字序列進(jìn)行分析，取那些位上數(shù)字變化多的、頻率大的作為散列函數(shù)地址。 例如，對(duì)如下的關(guān)鍵字序列： 430104681015355 430101701128352 430103720818

24、350 430102690605351 430105801226356 通過對(duì)上述關(guān)鍵字序列分析，發(fā)現(xiàn)前5位相同，第6、8、10位上的數(shù)字變化多些，若規(guī)定地址取3位，則散列函數(shù)可取它的第6、8、10位。于是有：H（430104681015355）480H（430101701128352）101H（430103620805351）328H（430102690605351）296H（430105801226356）5023平方取中法 取關(guān)鍵字平方后的中間幾位為散列函數(shù)地址。這是一種比較常用的散列函數(shù)構(gòu)造方法，在選定散列函數(shù)時(shí)不一定知道關(guān)鍵字的全部信息，取其中哪幾位也不一定合適，而一個(gè)數(shù)平方后的中間

25、幾位數(shù)和數(shù)的每一位都相關(guān)，因此，可以使用隨機(jī)分布的關(guān)鍵字得到函數(shù)地址。如圖，隨機(jī)給出一些關(guān)鍵字，并取平方后的第2到4位為函數(shù)地址。 4折疊法將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同），然后取這幾部分的疊加和（舍去進(jìn)位）作為散列函數(shù)地址，稱為折疊法。 例如，假設(shè)關(guān)鍵字為某人身份證號(hào)碼430104681015355，則可以用4位為一組進(jìn)行疊加，即有53558101104643014932，舍去高位，則有H（430104681015355）4932為該身份證關(guān)鍵字的散列函數(shù)地址。 除留余數(shù)法計(jì)算簡(jiǎn)單，適用范圍廣，是一種最常使用的方法。這種方法的關(guān)鍵是選取較理想的p值，使得每一個(gè)關(guān)鍵字

26、通過該函數(shù)轉(zhuǎn)換后映射到散列空間上任一地址的概率都相等，從而盡可能減少發(fā)生沖突的可能性。一般情形下，p取為一個(gè)質(zhì)數(shù)或選取一個(gè)不含有小于20的質(zhì)因子的合數(shù)較理想，并且要求裝填因子最好是在0.60.9之間，所以p最好取1.1n1.7n之間的一個(gè)質(zhì)數(shù)較好，其中n為散列表中待裝元素個(gè)數(shù).5除留余數(shù)法該方法是用關(guān)鍵字序列中的關(guān)鍵字k除以p(p是小于等于散列表長(zhǎng)度m）所得余數(shù)作為散列函數(shù)的地址，即有H（k）kp 。 選取哈希函數(shù)，考慮以下因素：計(jì)算哈希函數(shù)所需時(shí)間關(guān)鍵字長(zhǎng)度哈希表長(zhǎng)度（哈希地址范圍）關(guān)鍵字分布情況記錄的查找頻率三、 解決沖突的方法由于散列存貯中選取的散列函數(shù)不是線性函數(shù)，故不可避免地會(huì)產(chǎn)生沖

27、突，下面給出常見的解決沖突方法。1開放定址法 開放定址法就是從發(fā)生沖突的那個(gè)單元開始，按照一定的次序，從散列表中找出一個(gè)空閑的存儲(chǔ)單元，把發(fā)生沖突的待插入關(guān)鍵字存儲(chǔ)到該單元中，從而解決沖突的發(fā)生。在開放定址法中，解決沖突時(shí)具體使用下面一些方法。（1）線性探查法 假設(shè)散列表的地址為0m-1，則散列表的長(zhǎng)度為m。若一個(gè)關(guān)鍵字在地址d處發(fā)生沖突，則依次探查d+1，d+2，m-1(當(dāng)達(dá)到表尾m-1時(shí)，又從0，1，2，.開始探查)等地址，直到找到一個(gè)空閑位置來裝沖突處的關(guān)鍵字，將這一種方法稱為線性探查法。探查下一位置的公式為di=(di-1+1)%m (1im-1)，最后將沖突位置的關(guān)鍵字存入di地址中

28、。例 給定關(guān)鍵字序列為19，14，23，1，68，20，84，27，55，11，10，79，散到函數(shù)H（k）=k%13 ，散列表空間地址為012，試用線性探查法建立散列存貯(散列表)結(jié)構(gòu)。得到的散列表如下圖所示(2) 平方探查法該方法規(guī)定，若在d地址發(fā)生沖突，下一次探查位置為d+12，d+22，直到找到一個(gè)空閑位置為止。(3) 雙散列函數(shù)探查法該方法使用兩個(gè)散列函數(shù)H和T，用H作散列函數(shù)建立散列存儲(chǔ)（散列表），用T來解決沖突。具體實(shí)施時(shí)，若H(k)在d0位置發(fā)生沖突時(shí)，即d0 =H(k)，則下一個(gè)探查位置序列應(yīng)該是di=(di-1+T(k)%m (1im-1)。 2.拉鏈法拉鏈法也稱鏈地址法，是把相互發(fā)生沖突的同義詞用一個(gè)單鏈表鏈接起來，若干組同義詞可以組成若干個(gè)單鏈表 例 對(duì)給定的關(guān)鍵字序列19,14,23,1,68,20,84,27,55,11,10,79，給定散列函數(shù)為H(k)=k%13，試用拉鏈法解決沖突建立散列表。下圖為用尾插法建立的關(guān)