1、文件及查找第九章本章內(nèi)容9.1 文件的基本概念9.2 順序文件9.3 索引文件9.4 B-樹和B+樹9.5 散列(Hash)文件 9.1 文件的基本概念花名冊(cè)例199001張 三 女17 99002李 四 男18 99003王 五 男17 99050劉 末 女19 學(xué)號(hào) 姓 名性別年齡其 他 商品清單110025電視機(jī)3002000.2.3 代號(hào) 名稱 數(shù)量 入庫時(shí)間 其 他 120040洗衣機(jī)1252000.6.11 150003空調(diào)機(jī)502000.6.5 180024電冰箱302000.8.15 例299001張 三 女17 99002李 四 男18 99003王 五 男17 99050劉

2、 末 女19 學(xué)號(hào) 姓名性別年齡其 他：描述一個(gè)客體某一方面特征的數(shù)據(jù)信息。：區(qū)分不同記錄的屬性或?qū)傩越M。字段、數(shù)據(jù)項(xiàng)：具有相同性質(zhì)的記錄的集合。：由若干屬性值構(gòu)成的集合。一.名詞術(shù)語屬性記錄文件關(guān)鍵字記錄呈現(xiàn)在用戶眼前的排列的先后次序關(guān)系。 (線性結(jié)構(gòu))文件在存儲(chǔ)介質(zhì)上的組織方式。1.連續(xù)組織方式(順序組織方式)2.鏈接組織方式4.隨機(jī)組織方式(散列組織方式)3.索引組織方式順序文件索引文件散列文件二.文件的邏輯結(jié)構(gòu)三.文件的物理結(jié)構(gòu)四. 文件的基本操作(1). 查找文件的第i個(gè)記錄。(2). 查找當(dāng)前位置的下一個(gè)記錄。(3). 按關(guān)鍵字值查找記錄。查找 排序 插入刪除 修改在文件中確定某個(gè)

3、特定記錄存在與否的過程。以查找操作為基礎(chǔ)使記錄按關(guān)鍵字值有序排列的過程。查找成功,給出被查到記錄的位置；查找失敗,給出相應(yīng)的信息。結(jié)論 : 9.2 順序文件 記錄的排列按關(guān)鍵字值有序的順序文件稱為排序順序文件，否則，稱為一般順序文件。 在存儲(chǔ)介質(zhì)上采用連續(xù)組織方式的順序文件稱為連續(xù)順序文件；采用鏈接組織方式的順序文件稱為鏈接順序文件。邏輯上劃分物理上劃分 在物理結(jié)構(gòu)中記錄排列的先后次序與在邏輯結(jié)構(gòu)中記錄排列的先后次序一致的文件稱為 。順序文件 若排序順序文件在存儲(chǔ)介質(zhì)上采用連續(xù)組織方式，稱之為 。 排序連續(xù)順序文件一.順序文件的基本概念99001張 三 女17 99002李 四 男18 990

4、03王 五 男17 99050劉 末 女19 學(xué)號(hào) 姓 名性別年齡其 他 關(guān)鍵字關(guān)鍵字排序順序文件一般順序文件排序連續(xù)順序文件 查找思想： 從文件的第一個(gè)記錄開始,將用戶給出的關(guān)鍵字值與當(dāng)前被查找記錄的關(guān)鍵字值進(jìn)行比較，若匹配，則查找成功，給出被查到的記錄在文件中的位置，查找結(jié)束。若所有n 個(gè)記錄的關(guān)鍵字值都已比較，不存在與用戶要查的關(guān)鍵字值匹配的記錄，則查找失敗，給出信息0。 ( key1 , key2 , key3 , , keyn )關(guān)鍵字集合k被查找記錄的關(guān)鍵字值1. 順序查找法二. 連續(xù)順序文件的查找key1:10 38 75 19 57 100 48 50 7 62 11若查找 k

5、=48經(jīng)過六次比較,查找成功,返回i = 6查找失敗, 返回信息0若查找 k=35int SEQSEARCH( keytype key , int n, keytype k ) int i; for( i=1; in)，則返回信息0； 若存在(keyi=k) ，則返回位置i; 否則，從第i+1個(gè)位置開始執(zhí)行上述過程。每一個(gè)回合的查詢int SEQSEARCH2(keytype key ,int n,keytype k,int i) if(in) return 0; if(keyi=k) return i; return SEQSEARCH2(key,n,k,i+1);遞歸算法查找效率如何平均查

6、找長(zhǎng)度ASL(Average Search Length) 對(duì)于具有n個(gè)記錄的文件，有 ASL=pici其中，pi為查找第i個(gè)記錄的概率，ci為查找第i個(gè)記錄所進(jìn)行過的關(guān)鍵字的比較次數(shù)。 ni=1 確定一個(gè)記錄在文件中的位置所需要進(jìn)行的關(guān)鍵字值的比較次數(shù)的期望值(平均值)。 對(duì)于具有n個(gè)記錄的順序文件，若查找概率相等，則有 ASL=pici = i = 1 n+1 n 2 ni=1 ni=1結(jié)論算法的時(shí)間復(fù)雜度為O(n)優(yōu)點(diǎn)：缺點(diǎn)：對(duì)于被查找對(duì)象的排列次序沒有限制。查找的時(shí)間效率低。查找原理和過程簡(jiǎn)單，易于理解。2. 排序連續(xù)順序文件的折半查找法(二分查找法、 對(duì)半查找法) 將要查找的關(guān)鍵字值

7、與當(dāng)前查找范圍內(nèi)位置居中的記錄的關(guān)鍵字的值進(jìn)行比較， 若匹配，則查找成功，給出被查到記錄在文件中的位置，查找結(jié)束。 若要查找的關(guān)鍵字值小于位置居中的記錄的關(guān)鍵字值，則到當(dāng)前查找范圍的前半部分重復(fù)上述查找過程，否則，到當(dāng)前查找范圍的后半部分重復(fù)上述查找過程，直到查找成功或者失敗。 若查找失敗，則給出信息0。 查找思想：n 排序連續(xù)順序文件中記錄的個(gè)數(shù)。low 當(dāng)前查找范圍內(nèi)第一個(gè)記錄在文件 中的位置。初值 low=1high 當(dāng)前查找范圍內(nèi)最后那個(gè)記錄在文 件中的位置。初值 high=nmid 當(dāng)前查找范圍內(nèi)位置居中的那個(gè)記 錄在文件中的位置。幾個(gè)變量mid =low+high 2 2 5 7

8、11 14 16 19 23 27 32 50key1: n n=11 k=23lowhighmidlowlowmidmidhighhighmidmidlowlowmidmid例1 經(jīng)過四次元素之間的比較，查找成功,給出被查到記錄在文件中的位置8(mid)。查找成功1 2 3 4 5 6 7 8 9 10 11key1:n n=11 k=92 5 7 11 14 16 19 23 27 32 50lowhighmidhighhighmidmidlowlowmidmidhighhigh例2 經(jīng)過3次元素之間的比較，未能查到匹配的記錄，查找失敗。給出信息0。查找失敗查找失敗的標(biāo)志：lowhigh1

9、 2 3 4 5 6 7 8 9 10 11int BINSEARCH 1( keytype key , int n, keytype k ) int low=1, high=n, mid; while ( lowkeymid ) low=mid+1; /* 查找后半部分 */ else high=mid1; /* 查找前半部分 */ return 0; /* 查找失敗 */非遞歸算法int BINSEARCH 2( keytype key , int low, int high, keytype k ) int mid; if ( lowhigh ) return 0; else mid=(

10、low+high)/2; if ( keymid=k ) return mid; else if( kkey=k ) return( p ); /* 查找成功 */ p=p-link; return( NULL ); /* 查找失敗 */ 算法typedef struct node keytype key; rectype rec; struct node *link; *KeyLink; KeyLink SEARCH(KeyLink F, keytype k) if(F!=NULL) if(F-key=k ) return F; /* 查找成功 */ else return SEARCH(F

11、-link, k ); return NULL; /* 查找失敗 */ 遞歸算法一.索引文件的基本概念 9.3 索引文件1.索引記錄關(guān)鍵字值與記錄的存儲(chǔ)位置之間的對(duì)應(yīng)關(guān)系。2.索引文件 由基本數(shù)據(jù)與索引表兩部分組成的數(shù)據(jù)文件稱為索引文件。3.索引表的特點(diǎn)(1). 索引表是由系統(tǒng)自動(dòng)產(chǎn)生的。(2). 索引表中表項(xiàng)按關(guān)鍵字值有序排列。二. 稠密索引文件特點(diǎn) 文件的基本數(shù)據(jù)中的每一個(gè)記錄在索引表中都占 有一項(xiàng)。學(xué)號(hào) 姓名 其他110516031408062015322925王強(qiáng)李軍劉云張麗王義何山周鳴葛樹高德趙華陳舸于萍0101020103010401050106010701080109011001

12、11011201基本數(shù)據(jù)索引表學(xué)號(hào) 地址030506081114151620252932040102010701060101010501090103010801120111011001. 在稠密索引文件中查找一個(gè)記錄存在與否的過程是直接查找索引表。結(jié)論三.非稠密索引分塊文件特點(diǎn) 將文件的基本數(shù)據(jù)中記錄分成若干塊(塊與塊之間 記錄按關(guān)鍵字值有序, 塊內(nèi)記錄是否按關(guān)鍵字值 有序無所謂),索引表中為每一塊建立一項(xiàng)。學(xué)號(hào) 姓名 其他030506081114151620252932李義李春伍力張莎王強(qiáng)何山周海劉云高天文華陳舸宋濤01010201030104010501060107010801090110

13、0111011201基本數(shù)據(jù)學(xué)號(hào) 地址081632010105010901索引表對(duì)于每一項(xiàng)，給出該塊最大關(guān)鍵字值與該塊首地址kKEYi i =1, 2, , n例如查找 學(xué)號(hào)k=14 的學(xué)生結(jié)論 在非稠密索引(分塊)文件中查找一個(gè)記錄存在與否的過程是： 先查找索引表(確定被查找記錄所在塊)，然后在相應(yīng)塊中查找被查記錄存在與否。四. 多級(jí)索引文件 當(dāng)索引文件的索引本身非常龐大時(shí),可以把索引分塊,建立索引的索引,形成 。樹形結(jié)構(gòu)的多級(jí)索引 樹形結(jié)構(gòu)的多級(jí)索引二叉排序樹多級(jí)索引結(jié)構(gòu)、 多分樹索引結(jié)構(gòu)如 9.4 B-樹和B+樹一. B- 樹的定義一個(gè)m階的B-樹為滿足下列條件的m叉樹：(1). 每個(gè)分

14、支結(jié)點(diǎn)最多有m 棵子樹；(2). 除根結(jié)點(diǎn)外，每個(gè)分支結(jié)點(diǎn)最少有m/2棵子樹；(3). 根結(jié)點(diǎn)最少有兩棵子樹(除非根為葉結(jié)點(diǎn)，此時(shí)B -樹只 有一個(gè)結(jié)點(diǎn))；(4). 所有“葉結(jié)點(diǎn)”都在同一層上，葉結(jié)點(diǎn)不包含任何關(guān) 鍵字信息(可以把葉結(jié)點(diǎn)視為實(shí)際上不存在的外部結(jié)點(diǎn), 指向這些“葉結(jié)點(diǎn)”的指針為空)；(5). 所有分支結(jié)點(diǎn)中包含下列信息： n, p0, key1, p1, key2, p2, , keyn, pn 其中，n 為結(jié)點(diǎn)中關(guān)鍵字值的個(gè)數(shù)， keyi為關(guān)鍵字，且滿足 keyikeyi+1 1in pi為指向該結(jié)點(diǎn)的第i+1棵子樹的根的指針。0in Pi指的結(jié)點(diǎn)中所有關(guān)鍵字值都大于keyi

15、還含有n個(gè)指向相應(yīng)記錄的指針T35301843781127333947536499abcdefghi111111223一棵4階B-樹每個(gè)分支結(jié)點(diǎn)最多有4棵子樹每個(gè)分支結(jié)點(diǎn)最少有2棵子樹所有“葉結(jié)點(diǎn)”都在同一層上根結(jié)點(diǎn)最少有2棵子樹例分支結(jié)點(diǎn)中包含關(guān)鍵字個(gè)數(shù)、關(guān)鍵字（有序）及子樹指針 首先將給定的關(guān)鍵字k在B-樹的根結(jié)點(diǎn)的關(guān)鍵字集合中采用順序查找法或者折半查找法進(jìn)行匹配查找，若有keyi=k，則查找成功，根據(jù)相應(yīng)的指針取得記錄。否則，若k 在keyi 與 keyi+1 之間，則在指針pi 所指的結(jié)點(diǎn)中重復(fù)上述查找過程，直到在某結(jié)點(diǎn)中查找成功，或者在某結(jié)點(diǎn)中出現(xiàn)pi=nil，查找失敗。二.B- 樹

16、的查找類似于在二叉排序樹中查找一個(gè)結(jié)點(diǎn)的過程 n, p0, key1, p1, key2, p2, , keyn, pn dT35301843781127333947536499abcefghi111111223例例如，查找關(guān)鍵字k=47查找成功 ！例如，查找關(guān)鍵字k=23查找失敗 ！ (1) k=keyi 查找成功 (2) keyikkeynum; p-keyn+1=Maxkey; i=1; while( kp-keyi ) i+; if( p-keyi=k ) return( p-recptri ); else p=p-ptri-1; return (-1);k=53k=62查找成功！算法

17、 在p指結(jié)點(diǎn)的關(guān)鍵字集合中查找k沿著新的指針繼續(xù)查找！p-keyMp-ptrMp0p1p2p3pnp0p1p2p3pn475364Maxkey3key1key2key3keynMaxkeyn#define M 1000typedef struct node int keynum; keytype keyM+1; struct node *ptrM+1; rectype * recptrM+1; *BTree;三.B-樹的插入 一棵m階B-樹的結(jié)點(diǎn)中最多有m-1個(gè)關(guān)鍵字值10 2012 16530T一棵3階B-樹基本思想 若將k插入到某結(jié)點(diǎn)后使得該結(jié)點(diǎn)中關(guān)鍵字值數(shù)目超過m-1時(shí)，則要以該結(jié)點(diǎn)位置

18、居中的那個(gè)關(guān)鍵字值為界將該結(jié)點(diǎn)一分為二,產(chǎn)生一個(gè)新結(jié)點(diǎn)。并把位置居中的那個(gè)關(guān)鍵字值插入到雙親結(jié)點(diǎn)中;如雙親結(jié)點(diǎn)也出現(xiàn)上述情況,則需要再次進(jìn)行分裂。最壞情況下，需要一直分裂到根結(jié)點(diǎn)，以致于使得B-樹的深度加1。1512 15 16k=15插入10 2012 16530T3階B-樹k=15插入1512 15 16T530121610 15 20T5301216102015 一棵3階B-樹 的結(jié)點(diǎn)中最多有2個(gè)關(guān)鍵字值插入15 以后的3階B-樹完整地看這個(gè)例子B-樹的深度增加1層一般情況下 若某結(jié)點(diǎn)已有m-1個(gè)關(guān)鍵字值，在該結(jié)點(diǎn)中插入一個(gè)新的關(guān)鍵字值，使得該結(jié)點(diǎn)內(nèi)容為m key1 key2 key3

19、keym/2-1 key m/2 keym-1 keym q則需要將該結(jié)點(diǎn)分解為兩個(gè)結(jié)點(diǎn)q與q , 結(jié)點(diǎn)內(nèi)容為， m/2-1 key1 key2 keym/2-2 keym/2-1 qm-m/2 keym/2+1 keym/2+2 keym-1 keymq，并且將關(guān)鍵字值keym/2與一個(gè)指向q 的指針插入到q的雙親結(jié)點(diǎn)中。，m=35301216qq10 15 20T10 2012 16530Tq1512 15 16例如四.B +樹的定義一個(gè)m階的B+樹為滿足下列條件的m叉樹：(1). 每個(gè)分支結(jié)點(diǎn)最多有m 棵子樹；(2). 除根結(jié)點(diǎn)外，每個(gè)分支結(jié)點(diǎn)最少有m/2棵子樹；(3). 根結(jié)點(diǎn)最少有兩

20、棵子樹(除非根為葉結(jié)點(diǎn)結(jié)點(diǎn)，此 時(shí)B+樹只有一個(gè)結(jié)點(diǎn))；(4). 具有n 棵子樹的結(jié)點(diǎn)中一定有n 個(gè)關(guān)鍵字；(6). 所有分支結(jié)點(diǎn)可以看成是索引的索引，結(jié)點(diǎn)中僅 包含它的各個(gè)孩子結(jié)點(diǎn)中最大(或最小)關(guān)鍵字 值和指向孩子結(jié)點(diǎn)的指針。(5). 葉結(jié)點(diǎn)中存放記錄的關(guān)鍵字以及指向記錄的指針, 或者數(shù)據(jù)分塊后每塊的最大關(guān)鍵字值及指向該塊 的指針，并且葉結(jié)點(diǎn)按關(guān)鍵字值的大小順序鏈接 成線性鏈表。 key1 p1 key2 p2 keyn pn 同B-樹一棵3階B+樹T60 9985 9910 2092 9920 41 6027 36 4146 51 6065 79 85只有葉結(jié)點(diǎn)含有指向相應(yīng)記錄的指針li

21、st兩個(gè)入口B-樹與B+樹的區(qū)別122322T.T.4階B-樹3階B+樹list1.B-樹的每個(gè)分支結(jié)點(diǎn)中含有該結(jié)點(diǎn)中關(guān)鍵字值的個(gè)數(shù),B+樹沒有。2. B-樹的每個(gè)分支結(jié)點(diǎn)中含有指向關(guān)鍵字值對(duì)應(yīng)記錄的指針, 3. B-樹只有一個(gè)指向根結(jié)點(diǎn)的入口, 而B+樹的葉結(jié)點(diǎn)被鏈接成為一 個(gè)不等長(zhǎng)的鏈表，因此，B+樹有兩個(gè)入口，一個(gè)指向根結(jié)點(diǎn)，另 一個(gè)指向最左邊的葉結(jié)點(diǎn)(即最小關(guān)鍵字所在的葉結(jié)點(diǎn))。（從結(jié)構(gòu)上看） 而B+ 樹只有葉結(jié)點(diǎn)有指向關(guān)鍵字值對(duì)應(yīng)記錄的指針。 9.5 散列(Hash)文件 順序文件的順序查找法和折半查找法 、索引文件查找法 以及在B-樹B+樹中進(jìn)行的查找方法。查找的時(shí)間效率取決于查找

22、過程中的比較次數(shù) 基于關(guān)鍵字值比較的查找方法學(xué) 號(hào) 姓 名 年齡 99001 王 亮 17 99002 張 云 18 99003 李海民 20 99004 劉志軍 19 99049 周 穎 18 99050 羅 杰 16 一.散列文件的基本概念1.基本概念 A = H(k) 其中，k 為記錄的關(guān)鍵字，H(K)稱為散列函數(shù)，或哈希(Hash)函數(shù)，或雜湊函數(shù)。函數(shù)值A(chǔ)為k對(duì)應(yīng)的記錄在文件中的位置 能否有一種不經(jīng)過任何關(guān)鍵字值的比較或者經(jīng)過很少次的關(guān)鍵字值的比較就能夠達(dá)到目的方法 需要建立記錄的關(guān)鍵字值與記錄的存儲(chǔ)位置之間的關(guān)系。 答案是肯定的。 例1 學(xué) 號(hào) 姓名 性別 99001 張 云 女

23、99002 王 民 男 99003 李 軍 男 99004 汪 敏 女 99030 劉小春 男 關(guān)鍵字地址范圍： 1：30 散列函數(shù)： H(k)=k99000張 云 王 民 李 軍 汪 敏 劉小春 1 2 3 4 : :30例2 學(xué) 號(hào) 姓名 性別 99001 張 云 女 99002 王 民 男 99003 李 軍 男 99004 汪 敏 女 99030 劉小春 男 關(guān)鍵字 1 2 3 4 : :30散列函數(shù)： H(k) = “ 將組成關(guān)鍵字k 的串 轉(zhuǎn)換為一個(gè)130之 間的代碼 ”H(張?jiān)?=2張 云 H(王民)=4王 民 H(李軍)=1李 軍 H(汪敏)=4汪 敏 地址沖突地址范圍：1：3

24、0一個(gè)處理過程 對(duì)于不同的關(guān)鍵字ki與kj，經(jīng)過散列得到相同的散列地址，即有 H(ki) = H(kj)這種現(xiàn)象稱為散列沖突。 根據(jù)構(gòu)造的散列函數(shù)與處理沖突的方法將一組關(guān)鍵字映射到一個(gè)有限的連續(xù)地址集合上，并以關(guān)鍵字在該集合中的“象”作為記錄的存儲(chǔ)位置，按照這種方法組織起來文件稱為散列文件，或稱哈希文件，或稱雜湊文件；建立文件的過程稱為哈希造表或者散列，得到的存儲(chǔ)位置稱為散列地址或者雜湊地址。稱ki與kj為“同義詞”2.散列沖突3.什么是散列文件？1. 原 則散列函數(shù)的定義域必須包括將要存儲(chǔ)的全部關(guān)鍵碼；若散列表允許有m個(gè)位置時(shí)，則函數(shù)的值域?yàn)?:m1(地址空間)。利用散列函數(shù)計(jì)算出來的地址應(yīng)

25、能盡可能均勻分布在整個(gè)地址空間中。散列函數(shù)應(yīng)該盡可能簡(jiǎn)單，應(yīng)該在較短的時(shí)間內(nèi)計(jì)算出結(jié)果。二.散列函數(shù)的構(gòu)造一個(gè)“好”的散列函數(shù)1. 直接定址法2. 數(shù)字分析法3. 平方取中法4. 疊加法5. 基數(shù)轉(zhuǎn)換法6. 除留余數(shù)法 H(k)=k99000詳見教材P307-3092. 步 驟3. 方 法確定散列的地址空間(地址范圍)；構(gòu)造合適的散列函數(shù)；選擇處理沖突的方法。一般形式 H(k)=ak+bH(k) = k MOD p其中，若m為地址范圍大小(或稱表長(zhǎng))， 則p可為小于等于m的素?cái)?shù)。除留余數(shù)法 所謂開放地址法是在散列表中的“空”地址向處理沖突開放。即當(dāng)散列表未滿時(shí)，處理沖突需要的“下一個(gè)”地址在該

26、散列表中解決。 Di = ( H(k)+di ) MOD m i=1, 2, 3, 其中，H(k)為哈希函數(shù)，m為表的長(zhǎng)度，di為地址增量，有：(1) di=1, 2, 3, , m1 稱為線性再散列 (2) di=12, 22, , ( m/2)2 稱為二次再散列(3) di=偽隨機(jī)數(shù)序列 稱為偽隨機(jī)再散列1.開放地址法 所謂處理沖突,是在發(fā)生沖突時(shí),為沖突的元素找到另一個(gè)散列地址以存放該元素。如果找到的地址仍然發(fā)生沖突，則繼續(xù)為發(fā)生沖突的這個(gè)元素尋找另一個(gè)地址，直到不再發(fā)生沖突。閉散列方法三.沖突的處理方法0 1 2 3 4 5 6 7 8 9 10 11 1270 19 330 1 2

27、3 4 5 6 7 8 9 10 11 1270 19 330 1 2 3 4 5 6 7 8 9 10 11 1270 19 33插入前線性再散列二次再散列1818 設(shè)散列函數(shù)為 H(k) = k MOD 13散列表為0: 12， 表中已分別有關(guān)鍵字為19，70，33的記錄，現(xiàn)將第四個(gè)記錄(關(guān)鍵字值為18)插入散列表中。除留余數(shù)法 Di = ( k MOD 13 + di ) MOD 13例3散列地址為5 已知有長(zhǎng)度為M的散列表HT0:M1，散列函數(shù)為H(k)，并且采用線性探測(cè)再散列方法處理沖突。請(qǐng)寫出在該散列表中查找關(guān)鍵字值為key的元素存在與否的算法。若存在，則給出它在表中的位置，否則，

28、給出相應(yīng)信息。例4 Di = ( k MOD 13 + di ) MOD 130 1 2 3 4 5 6 7 8 9 10 11 1270 19 33HT:18251338key=70key=38key=18key=20查找H(k)=k MOD 13例int HASHSEARCH(ElemType HT, int M, ElemType key) int i,D; i=H(key); D=i; while (HTD !=空 & HTD!=key ) D=(D+1) % M; if (D=i) / 轉(zhuǎn)了一圈回到開始點(diǎn)(表滿) , 查找失敗 / return (1); if (HTD=key) r

29、eturn(D); / 查找成功 / return (1); /查找失敗 / 算法聚集 散列地址不同的元素爭(zhēng)奪同一后 繼散列地址的現(xiàn)象。 1. 散列函數(shù)選擇得不合適； 2. 負(fù)載因子過大。負(fù)載因子 衡量散列表的 。飽滿程度散列表中實(shí)際存入的元素?cái)?shù)散列表中基本區(qū)的最大容量 =產(chǎn)生聚集的主要原因特點(diǎn)“線性探測(cè)法”容易產(chǎn)生元素“聚集”的問題?！岸翁綔y(cè)法”可以較好地避免元素“聚集”的問題，但不能探測(cè)到表中的所有元素(至少可以探測(cè)到表中的一半元素)。只能對(duì)表項(xiàng)進(jìn)行邏輯刪除(如做刪除標(biāo)記)，而不能進(jìn)行物理刪除。使得表面上看起來很滿的散列表實(shí)際上存在許多未用位置。 Di = Hi(k) i=1, 2, 3, 其中， Di為散列地址，Hi(k)為不同的散列函數(shù)。 將哈希文件分為基本區(qū)與溢出區(qū)兩個(gè)部分，沒有發(fā)生沖突的記錄放在基