第七章查找表7.2靜態查找表7.3哈希表7.1基本概念和術語何謂查找表？

查找表是由同一類型的數據元素(或記錄)構成的集合。

“集合”中的數據元素之間存在著松散的關系，因此查找表是一種應用靈便的結構。7.1基本概念和術語對查找表經常進行的操作:1）查詢某個“特定的”數據元素是否在查找表中；2）檢索某個“特定的”數據元素的各種屬性；與查詢不同，檢索已知數據元素及它的屬性。3）在查找表中插入一個數據元素；4）從查找表中刪去某個數據元素。

查找表的四種操作都在查詢基礎上完成。作查詢和檢索操作的查找表；靜態查找表若在查找過程中同時插入查找表中不存在的數據元素,或從查找表中刪除已存在的某個數據元素,則稱此類表為動態查找表.動態查找表查找表可分為兩類:(1)基本不改變查找表的結構。(2)“查詢”數據元素“不在查找表中”，將其插入；“查詢”數據元素“在查找表中”，將其刪除；改變查找表的結構。

在一個含有眾多數據元素(或記錄)的查找表中找出某個“特定的”數據元素(或記錄)。

查找必須給出“特定的”詞的確切含義，首先引入一個“關鍵字”的概念。

數據元素（或記錄）中某個數據項的值，用以標識（識別）一個數據元素（或記錄）。關鍵字:

若此關鍵字可以唯一地標識一個數據元素（或記錄），則稱之謂“主關鍵字”。（對不同的記錄，其主關鍵字均不同）如：銀行中的帳號

若此關鍵字能識別若干記錄，則稱之謂“次關鍵字”。如：姓名

假設關鍵字是ElemType型，可進行比較。

查找:在查找表中確定一個關鍵字等于給定的數據元素或（記錄）。

若查找表中存在這樣一個記錄，則稱“查找成功”，查找結果：給出整個記錄的信息，或指示該記錄在查找表中的位置；否則稱“查找不成功”，查找結果：給出“空記錄”或“空指針”。

由于查找表本身是一種松散的集合結構，數據元素之間不存在明顯的組織規律，因此不便于查找。如：修自行車時，從雜物盒中找鏍釘。為了提高查找的效率，需要在查找表松散的集合元素之間人為地附加某種確定的關系，以便按某種規則進行查找，即

用另外一種數據結構來表示查找表。即：將雜物盒中的鏍釘分類。如何進行查找？查找的方法取決于查找表的結構。衡量一個算法好壞的量度有三條：

時間復雜度(衡量算法執行的時間量級)

空間復雜度(衡量算法的數據結構所占存儲以及大量的附加存儲)

算法的其它性能查找操作的性能分析:查找算法中的基本操作是“將記錄的關鍵字和給定值進行比較”，因此，通常以“平均查找長度”作為衡量查找算法的好壞。不再采用時間復雜度作依據。

查找算法的平均查找長度ASL

(AverageSearchLength)

為確定記錄在表中的位置，需和給定值進行比較的關鍵字次數的期望值稱為查找算法在查找成功時的平均查找長度。查找操作的時間性能分析對于含有n個數據元素的表,查找成功時的平均查找長度為

:nASL=ΣPiCi

i=1

其中:Pi——為查找第i個數據元素的概率,且Ci——為找到表中其關鍵字與給定值相等的第i個記錄時,和給定值已進行過比較的關鍵字個數。在等概率查找的情況下，順序表查找的平均查找長度為：對順序表每進行一次查找，我們需比較的數據元素的關鍵字的個數幾乎是表長的一半。7.2靜態查找表數據對象D：數據關系R：D是具有相同特性的數據元素的集合。每個數據元素含有類型相同的關鍵字，可唯一標識數據元素。

數據元素同屬一個集合。抽象數據類型靜態查找表的定義為:ADTStaticSearchTable{

Create(&ST,n);Destroy(&ST);Search(ST,key);Traverse(ST,Visit());基本操作P：next}ADTStaticSearchTable若ST中存在其關鍵字等于

key的數據元素，則函數值為該元素的值或在表中的位置，否則為“空”。

Search(ST,key);初始條件：操作結果：靜態查找表ST存在，key為和查找表中元素的關鍵字類型相同的給定值；7.2.1順序查找7.2.2折半表的查找7.2.3索引順序表的查找順序查找又稱線性查找。其基本思想是：從靜態查找表的一端開始，將給定記錄的關鍵字與表中各記錄的關鍵字逐一比較，若表中存在要查找的記錄，則查找成功，并給出該記錄在表中的位置；否則，查找失敗，并給出失敗信息。7.2順序查找表ST.elemii例:在順序查找表中查找一個key=64的給定值在下標變量為0處賦值給定值key，叫設置監視哨，所賦的給定值叫哨兵。從表中最后一個記錄開始,逐個進行記錄的關鍵字和給定值的比較,指針向前移，計數器i-1，直到某個記錄的關鍵字和給定值比較相等為止,則查找成功,找到所查記錄;iii64監視哨

i指針從表長開始，不相等時i-1,當i指針移到0位置時，就自然停住了，指針不會出界,因為在此處一定是相等的。在整個查找過程中不需檢驗i值是否大于0，這就是順序表查找過程。監視哨ST.elemiikey=60iii60i靜態查找表的順序存儲結構為算法7.1//----------靜態查找表的順序存儲結構-----------#defineLIST_INIT_SIZE100//線性表存儲空間的初始分配量typedef

struct{

ElemType*elem; //存儲空間基址

intlength; //當前線性表長度

int

listsize; //當前分配的存儲容量(以sizeof(ElemType)為單位)}SqList;int

Search_Seq(SSTableST,

KeyTypekey){

//在順序表ST中順序查找其關鍵字等于

//key的數據元素。若找到，則函數值為

//該元素在表中的位置，否則為0。

ST.elem[0].key=key;//設置“哨兵”

for(i=ST.length；ST.elem[i].key!=key;--i);

//從后往前找，i的初值是表長，終值元素是//賦的值，在不相等的情況下i-1。

returni;//找不到時，i為0；找到時，i大于0。}//Search_Seqintmain() //主程序用來檢驗順序查找算法7.1{

SqList

st;

inti;

st.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));

for(i=1;i<=6;i++)st.elem[i]=i;st.length=6;//構造靜態查找表st=(1,2,3,4,5,6)

i=Search(st,5);

//調用順序查找方法，在查找表st中查找5是否存在

printf(“位置為：%d\n”,i);i=Search(st,8); //調用順序查找方法，在查找表st中查找8是否存在

printf(“位置為：%d\n”,i); //不存在位置為0}性能分析：假設順序表中每個記錄的查找概率相同，即pi?=?1/n，查找表中第i個記錄順序查找的平均查找需進行n-i+1次比較，即ci?=?n-i+1。當查找成功時順序查找的平均查找長度為

ASL?==(n?-?i?+?1)?=?(n+1)/2

當查找不成功時，關鍵字的比較次數是n+1次。順序查找的基本操作是關鍵字的比較，因此，查找表的長度就是查找算法的時間復雜度，即為O(n)。

上述順序查找表的查找算法簡單，但平均查找長度較大，不太適用于表長較大的查找表。7.2.2折半查找表

以有序表（按關鍵字的大小從小到大或從大到小排列的表）表示靜態查找表，查找過程可以基于“折半”進行。ST.elemST.length折半查找的算法：例如:key=64

的查找過程如下lowhighmidlow

mid

high

mid指針low

指示查找區間的下界;指針high

指示查找區間的上界;指針mid=(low+high)/2intSearch_Bin(SSTableST,KeyTypekey){

low=1;high=ST.length;

//置區間初值

while(low<=high){mid=(low+high)/2;

if（key==ST.elem[mid].key)

returnmid;//找到待查元素

elseif(key<ST.elem[mid].key))

high=mid-1;

//繼續在前半區間進行查找

else

low=mid+1;//繼續在后半區間進行查找

}return0;//順序表中不存在待查元素}//Search_Bin先看一個具體的情況，假設：n=11分析折半查找的平均查找長度122333344440513192137566475808892從上述查找過程可知：找到第⑥個元素僅需比較1次；找到第③和第⑨個元素需比較2次；找到第①、④、⑦和⑩個元素需比較3次；找到第②、⑤、⑧…需比較4次。這個查找過程可用二叉樹來描述,通常稱這個描述查找過程的二叉樹為判定樹，從判定樹上可見，(1)查找到給定值21的過程恰好是走了一條從根到結點④的路徑，(2)與給定值21進行比較的關鍵字的個數為該路徑上的結點數或結點④在判定樹上的層次數。6391425781011判定樹查找成功時折半查找的平均查找長度(ASL):假設n=2h-1并且查找概率相等則在n>50時，可得近似結果

折半查找的效率比順序查找高，但折半查找只適用于有序表，且限于順序存儲結構。（對線性鏈表無法有效地進行折半查找）7.2.3索引順序表是順序查找的一種改進方法,在建立順序表的同時，建立一個索引。012345678910111213……1708211914313322254052617846……2104057810……例：索引順序表=索引+順序表順序表索引一般情況下，索引表是一個有序表。例：表中含有18個記錄，可分成三個子表(Rl，R2，…，R6)、(R7，R8，…，R12)、(R13，R14，…R18)，對每個子表(或稱塊)建立一個索引項

索引表按關鍵字有序，則表有序或分塊有序。“分塊有序”是第i個子表中所有記錄的關鍵字均大于第i-1個子表中的最大關鍵字。索引表包括兩項內容：關鍵字項：其值為該子表內的最大關鍵字指針項：指示該子表的第一個記錄在表中位置137186482286745860484442338131222索引表最大關鍵字

起始地址17

1338244953920

假設給定值key=38，則先將key依次和索引表中各最大關鍵字進行比較，由于22<key<48，則關鍵字為38的記錄若存在，必定在第二個子表中，由于索引表中的指針項指示第二個子表中的第一個記錄是表中第7個記錄，則自第7個記錄起進行順序查找，直到ST.elem[10].key=38為止。137186482286745860384842338131222索引表最大關鍵字起始地址分塊查找過程需分兩步進行：（1）確定待查記錄所在的塊(子表)；（2）在塊中順序查找。17

13137186482286745860384842338131222索引表最大關鍵字起始地址

索引表是有序的，子表不是有序的但是有限的。

每個子表中都有空格字符，可直接插入元素而不移動其它元素。索引順序查找表由有序表和順序表的簡單合成17

13例如：在一個系中有多個班級，索引表中是班級名，子表中是每個班級中同學的名單，是有限的，當有插班的同學時，可直接將其姓名插入，索引表不變。索引順序查找的平均查找長度為在索引中進行查找的平均查找長度和在“順序表”中進行查找的平均查找長度之和。

7.3.1哈希表的基本概念7.3.2哈希函數的構造方法

7.3.3

理沖突的方法

7.3.4哈希表的查找7.3哈希表

以上兩節討論了查找表的查找的過程為給定值依次和關鍵字集合中各個關鍵字進行比較。7.3.1哈希表的基本概念共同特點：記錄在表中的位置和它的關鍵字之間不存在一個確定的關系。

不同的表示方法，其差別僅在于：關鍵字和給定值進行比較的順序不同。前幾節幾種方法表示的查找表，其平均查找長度都不為零。

查找的效率取決于和給定值進行比較的關鍵字個數即平均查找長度ASL。對于頻繁使用的查找表，希望平均查找長度ASL=0。只有一個辦法：預先知道所查關鍵字在表中的位置。

即，要求：記錄在表中位置和其關鍵字之間存在一種確定的關系。因此，需在關鍵字與記錄在表中的存儲位置之間建立一個函數關系。以f(key)作為關鍵字為key的記錄在表中的位置，通常稱這個函數f(key)為哈希函數。{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei}例如：對于如下9個關鍵字設哈希函數

f(key)=

(Ord(第一個字母))/2

ChenZhaoQianSunLiWuHanYeDei問題:

若添加關鍵字Zhou,怎么辦？能否找到另一個哈希函數？261917

1)哈希函數是一個映象，即：將關鍵字的集合映射到某個地址集合上，

它的設置很靈活，只要這個地址集合的大小不超出允許范圍即可；從這個例子可見：

2)由于哈希函數是一個壓縮映象，因此，在一般情況下，很容易產生“沖突”現象，即：

key1

key2，而

f(key1)=f(key2)。

3)

很難找到一個不產生沖突的哈希函數。一般情況下，只能選擇恰當的哈希函數，使沖突盡可能少地產生。

因此，在構造這種特殊的“查找表”時，除了需要選擇一個“好”(盡可能少產生沖突)的哈希函數之外；還需要找到一種“處理沖突”

的方法。哈希表的定義：

根據設定的哈希函數H(key)

和所選中的處理沖突的方法，將一組關鍵字映象到一個有限的、地址連續的地址集(區間)上，并以關鍵字在地址集中的“象”作為相應記錄在表中的存儲位置，如此構造所得的查找表稱之為“哈希表”。對于哈希表，主要考慮兩個問題，其一是如何構造哈希函數，其二是如何解決哈希沖突。對于如何構造哈希函數，應解決兩個主要問題：(1)哈希函數是一個壓縮映像函數，它具有較大的壓縮性，不可避免地產生沖突。(2)哈希函數具有較好的散列性，盡可能均勻地把記錄映射到各個存儲地址上，盡量減少沖突的產生，從而提高查找效率。7.3.2構造哈希函數的方法

構造哈希函數時，一般都要對關鍵字進行計算，為了盡量避免產生相同的哈希函數值，應使關鍵字的所有組成成分都能起作用。對數字的關鍵字可有下列構造方法：

若是非數字關鍵字，則需先對其進行數字化處理。1.

直接定址法4.平方取中法2.除留余數法3.數字分析法哈希函數為關鍵字的線性函數

H(key)=key或者

H(key)=a

key+b1.

直接定址法此法僅適合于：地址集合的大小==關鍵字集合的大小2.除留余數法

設定哈希函數為:

H(key)=keyMODp

其中，

p≤m(表長)

對P的選擇很重要。

給定一組關鍵字為：12,39,18,24,33,21，若取p=9,則他們對應的哈希函數值將為：

3,3,0,6,6,3例如：為什么要對p加以選擇？

可見，若p中含質因子3，

則所有含質因子3的關鍵字均映射到“3的倍數”的地址上，從而增加了“沖突”的可能。此方法僅適合于：

能哈希表中可能出現的關鍵字是事先知道的。3.

數字分析法

假設關鍵字集合中的每個關鍵字都是由s位數字組成(u1,u2,…,us)，分析關鍵字集中的全體，并從中提取分布均勻的若干位或它們的組合作為地址。例如，有80個記錄，要構造的哈希表長度為100。為了不失一般性，取其中8個記錄的關鍵字進行分析，8個關鍵字如下所示：1231034612560783114201282113151712850435222416512178187421600002…..…..

分析：8個關鍵字可知，關鍵字從左到右的第1、2、5位的取值比較集中，不宜作為哈希地址，剩余的第3、4、6、7、8位取值近乎隨機，可選取其中的兩位作為哈希地址。設選取第6和7位作為哈希地址，則8個關鍵碼的哈希地址為34、78、12、51、43、65、87、02。4．平方取中法

平方取中法是指取關鍵字平方后的中間幾位作為哈希地址。這是一種較常用的構造哈希函數的方法。但是，在選定哈希函數時不一定能知道關鍵字的全部情況，取其中的哪幾位也不一定合適，而一個數平方后的中間幾位數與數的每一位都相關，所以，隨機分布的關鍵字得到的，哈希地址也是隨機的，取的位數由表長決定。實際造表時，采用何種構造哈希函數的方法取決于建表的關鍵字集合的情況(包括關鍵字的范圍和形態)，總的原則是使產生沖突的可能性降到盡可能地小。7.3.3處理沖突的方法

“處理沖突”

的實際含義是：為產生沖突的地址尋找下一個哈希地址。1.開放定址法2.鏈表法

為產生沖突的地址H(key)尋找下一個哈希地址：

H=

H(key)MODm

Hi=(H(key)+di

)MODm

i=1,2,…,s1≤s≤m-11.開放定址法對增量di

有三種取法：1)線性探測再散列

di=c

i

最簡單的情況c=12)平方探測再散列

di=12,-12,22,-22,…,3)隨機探測再散列

di

是一組偽隨機數列

或者

di=i×H2(key)

(又稱雙散列函數探測)例7.3已知9個記錄的關鍵字為(12，22，25，38，24，47，29，16，36)，試構造哈希表存放這9個記錄。哈希函數為H(key)?=?keymod12，哈希表的內存空間為12個存儲單元。采用線性探測法處理沖突過程如下：

H(key)?=?keymod12?=?12mod12?=?0，不沖突，關鍵字12放入0號單元。

H(key)?=?keymod12?=?22mod12?=?10，不沖突，關鍵字22放入10號單元。

H(key)?=?keymod12?=?25mod12?=?1，不沖突，關鍵字25放入1號單元。

H(key)?=?keymod12?=?38mod12?=?2，不沖突，關鍵字38放入2號單元。

H(key)?=?keymod12?=?24mod12?=?0，沖突，按照處理沖突的方法求下一個哈希地址。

H1?=?0?+?1?=?1，1號單元有記錄，沖突。

H2?=?0+2?=?2，沖突。

H3?=?0+3?=?3，不沖突，關鍵字24放入3號單元。

H(key)?=?keymod12?=?47mod12?=?11，不沖突，關鍵字47放入11號單元，

H(key)?=?keymod12?=?29mod12?=?5，不沖突，關鍵字29放入5號單元，

H(key)?=?keymod12?=?16mod12?=?4，不沖突，關鍵字16放入4號單元，

H(key)?=?keymod12?=?36mod12?=?0，沖突，按照處理沖突的方法求下一個哈希地址。

H1?=?0+1?=?1，1號單元有記錄，沖突。

H2?=?0+2?=?2，沖突。

H3?=?0+3?=?3，沖突。

H4?=?0+4?=?4，沖突。

H5?=?0+5?=?5，H6?=?0+6?=?6，不沖突，關鍵字36放入6號單元。

最后建成的哈希表如書上表7.2所示

例表長為11的哈希表中已填有關鍵字為17，60，29的記錄，H(key)=keyMOD11,現有第4個記錄，其關鍵字為38，按三種處理沖突的方法，將它填入表中012345678910601729(1)H(38)=38MOD11=5沖突

H1=(5+1)MOD11=6沖突

H2=(5+2)MOD11=7沖突

H3=(5+3)MOD11=8不沖突

38(2)H(38)=38MOD11=5沖突

H1=(5+12)MOD11=6沖突

H2=(5-12)MOD11=4不沖突38(3)H(38)=38MOD11=5沖突設偽隨機數序列為9，則：

H1=(5+9)MOD11=3不沖突38線性探測再散列：平方探測再散列：隨機探測再散列：例如:

關鍵字集合

{19,01,23,14,55,68,11,82,36}設定哈希函數

H(key)=keyMOD11(表長=11)1901231455681901231468若采用線性探測再散列處理沖突若采用二次探測再散列處理沖突118236551182360123456140136198223116855

ASL=(6×1+2×2+3)/9=13/9例如:同前例的關鍵字，哈希函數為H(key)=keyMOD7平均查找長度：2.鏈表法將所有哈希地址相同的記錄都鏈接在同一鏈表中。

例7.5已知12個記錄的關鍵字為(12,22,25,38,24,47,29,16,37,44,55,50)，試構造哈希表存放這12個記錄，哈希函數H(key)=keymod12，用鏈表法處理沖突。

H(key)=keymod12=12mod12=0；

H(key)=keymod12=22mod12=10；

H(key)=keymod12=25mod12=1；