第7講 查找技術(shù)

計算機(jī)

軟件技術(shù)基礎(chǔ)第7講查找技術(shù)3.1基本的查找技術(shù)順序查找有序表的折半查找分塊查找查找的概念查找是指在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找某個指定的元素。查找的效率將直接影響到數(shù)據(jù)處理的效率。通常，根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)，應(yīng)采用不同的查找方法。分類靜態(tài)查找---只查找，不改變查找表內(nèi)元素動態(tài)查找---既查找，又改變差找表內(nèi)元素查找的概念評估查找方法優(yōu)劣的評價指標(biāo)查找就是將給定值與查找表內(nèi)各元素進(jìn)行比較的過程，所以用比較次數(shù)的平均值來評估查找算法的優(yōu)劣，稱為平均查找長度(ASL)n:查找表內(nèi)元素個數(shù)Ci:是找到第i個元素時經(jīng)歷的比較次數(shù)Pi:是查找第i個元素的概率(通常取等概率即：Pi=1/n)查找的概念靜態(tài)查找的主要算法順序查找折半查找靜態(tài)樹表的查找分塊查找（索引順序查找）

順序查找順序查找又稱順序搜索。其基本方法是：從線性表的第一個元素開始，依次將線性表中的元素與被查元素進(jìn)行比較，若相等則表示查找成功；若線性表中所有的元素都與被查元素進(jìn)行了比較但都不相等，則表示線性表中沒有要找的元素，即查找失敗。C描述：順序表的順序查找intSeqSearch(inta[]，intn，intkey){inti；

for(i=0;i<n;i++)if(a[i]==key)returni;returni;}C描述：鏈表的順序查找structnode*lserch(structnode*head，intx){structnode*p；

p＝head；

while(p!=NULL&&p－>d!=x) p＝p－>next；

returnp；}順序查找優(yōu)點(diǎn)：算法簡單而且適用性廣，對查找表的結(jié)構(gòu)無要求。無論表內(nèi)元素是否有序均可應(yīng)用，對于線性鏈表也適用。缺點(diǎn)：平均查找次數(shù)較大，特別是n值較大時，查找效率較低。如果線性表為無序表，則不管是順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯Y(jié)構(gòu)，都只能用順序查找。即使是有序線性表，如果采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，也只能用順序查找。有序表查找的分類根據(jù)確定中間位置的方法不同，分為折半查找斐波納契查找插值查找折半查找思想：將給定的查找關(guān)鍵字K與線性表的中間位置上的元素進(jìn)行比較，若相等則查找成功。若不等，中間元素將表分為兩部分，前一部分的元素均小于中間元素，后一部分的元素均大于中間元素。根據(jù)和中間元素的比較結(jié)果，選擇一部分重復(fù)進(jìn)行上述過程，直到查找成功或失敗。C描述：非遞歸intBiSearch(inta[]，intn，intkey){intlow,high,mid,i;

low=0;high=n-1;

while(low＜＝high){mid＝(low＋high)/2；

if(a[mid]==key) returnmid；

if(a[mid]＞key)low=mid+1

else hight＝mid-1；

}

return－1；}C描述：遞歸intBiSearch(inta[],intkey,intlow,inthigh){intmid;

if(low<high)return-1;mid＝(low＋high)/2；if(a[mid]==key) returnmid；elseif(a[mid]>key)returnBiSearch(a[],key,mid+1,high)

else

returnBiSearch(a[],key,low,mid-1)}折半查找的效率(ASL)1次比較就查找成功的元素有1個(20)，即中間值2次比較就查找成功的元素有2個(21)，即1/4(或3/4)處3次比較就查找成功的元素有2個(22)，即1/8(或3/8)處第m次比較就查找成功的元素有2m-1個為方便起見，假設(shè)表中所有n元素=2n-1，此時不討論第m次比較后還有剩余元素的情況。假設(shè)查找每個元素的概率相等。分塊查找分塊有序：將線性表分成若干個塊B1、B2、…、Bn，并要求當(dāng)i<j時，Bi中的記錄關(guān)鍵字都小于Bj中記錄的關(guān)鍵字。索引表：每個塊在索引表中有一項(xiàng)，稱為索引項(xiàng)。索引項(xiàng)中包括兩個域，一個域存放塊中記錄關(guān)鍵字的最大值，另一個域存放塊的第一個記錄在線性表中的位置。分塊查找索引表最大關(guān)鍵字255689起始地址1611

10525201856342932476872618489步驟①確定待查記錄所在的塊：將待查關(guān)鍵字k與索引表中的關(guān)鍵字進(jìn)行比較。②進(jìn)一步用順序查找法，在相應(yīng)塊內(nèi)查找關(guān)鍵字為k的元素

Hash表在一般的線性表，樹中，記錄在結(jié)構(gòu)中的相對位置是隨機(jī)的，即和記錄的關(guān)鍵字之間不存在確定的關(guān)系，因此，在結(jié)構(gòu)中查找記錄時需進(jìn)行一系列和關(guān)鍵字的比較。這一類查找方法建立在“比較“的基礎(chǔ)上，查找的效率依賴于查找過程中所進(jìn)行的比較次數(shù)。理想的情況是能直接找到需要的記錄，因此必須在記錄的存儲位置和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系f，使每個關(guān)鍵字和結(jié)構(gòu)中一個唯一的存儲位置相對應(yīng)。Hash表哈希表最常見的例子是以學(xué)生學(xué)號為關(guān)鍵字的成績表，１號學(xué)生的記錄位置在第一條，１０號學(xué)生的記錄位置在第１０條...如果我們以學(xué)生姓名為關(guān)鍵字，如何建立查找表，使得根據(jù)姓名可以直接找到相應(yīng)記錄呢？Hash表Hash表上面這張表即哈希表。如果將來要查李秋梅的成績，可以用上述方法求出該記錄所在位置：李秋梅:lqm12+17+13=42取表中第42條記錄即可。問題：如果兩個同學(xué)分別叫劉麗劉蘭該如何處理這兩條記錄？這個問題是哈希表不可避免的，即沖突現(xiàn)象：對不同的關(guān)鍵字可能得到同一哈希地址。Hash表的基本概念若結(jié)構(gòu)中存在和關(guān)鍵字K相等的記錄，則必定在f(K)的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應(yīng)關(guān)系f為散列函數(shù)(Hashfunction)，按這個思想建立的表為散列表。問題：上面例子中的散列函數(shù)是什么？問題：如果兩個同學(xué)分別叫劉麗劉蘭該如何處理這兩條記錄？Hash表的基本概念對不同的關(guān)鍵字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，這種現(xiàn)象稱沖突。具有相同函數(shù)值的關(guān)鍵字對該散列函數(shù)來說稱做同義詞。根據(jù)散列函數(shù)H(key)和處理沖突的方法將一組關(guān)鍵字映象到一個有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“象”作為記錄在表中的存儲位置，這種表便稱為散列表，這一映象過程稱為散列造表或散列，所得的存儲位置稱散列地址。Hash表提供了快速的插入操作和查找操作。不論哈希表中有多少數(shù)據(jù)，只需要接近常量的時間即0(1）的時間級。實(shí)際上，這只需要幾條機(jī)器指令Hash表的基本概念Hash表是基于快速存取的角度設(shè)計的，是一種典型的以空間換取時間的做法。必須在原有數(shù)據(jù)占用的空間之外利用額外的空間構(gòu)造Hash表。哈希表基于數(shù)組的，數(shù)組創(chuàng)建后難于擴(kuò)展。某些哈希表被基本填滿時，性能下降得非常嚴(yán)重，所以程序員必須要清楚表中將要存儲多少數(shù)據(jù)（或者準(zhǔn)備好定期地把數(shù)據(jù)轉(zhuǎn)移到更大的哈希表中，這是個費(fèi)時的過程）。沒有一種簡便的方法可以以任何一種順序〔例如從小到大〕遍歷表中數(shù)據(jù)項(xiàng)。如果需要這種能力，就只能選擇其他數(shù)據(jù)結(jié)構(gòu)。Hash表的關(guān)鍵散列函數(shù)的構(gòu)造方法直接定址法數(shù)字分析法平方取中法折疊法隨機(jī)數(shù)法除留余數(shù)法處理沖突的方法開放地址法再散列法鏈地址法（拉鏈法）建立一個公共溢出區(qū)直接定址法取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為散列地址。即H(key)=key或H(key)=a?key+b，其中a和b為常數(shù)（這種散列函數(shù)叫做自身函數(shù)）有一個從1到100歲的人口數(shù)字統(tǒng)計表，其中，年齡作為關(guān)鍵字，哈希函數(shù)取關(guān)鍵字自身。但這種方法效率不高,時間復(fù)雜度是O(1),空間復(fù)雜度是O(n),n是關(guān)鍵字的個數(shù)數(shù)字分析法有學(xué)生的生日數(shù)據(jù)如下：年.月.日75.10.03

75.11.23

76.03.02

76.07.12

75.04.21

76.02.15經(jīng)分析,第一位，第二位，第三位重復(fù)的可能性大，取這三位造成沖突的機(jī)會增加，所以盡量不取前三位，取后三位比較好。因此數(shù)字分析法就是找出數(shù)字的規(guī)律，盡可能利用這些數(shù)據(jù)來構(gòu)造沖突幾率較低的散列地址。平方取中法以關(guān)鍵字的平方值的中間幾位作為存儲地址。求“關(guān)鍵字的平方值”的目的是“擴(kuò)大差別”，同時平方值的中間各位又能受到整個關(guān)鍵字中各位的影響。此方法適合于:關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象。構(gòu)造Hash表構(gòu)造Hash表的方法很多，用戶可根據(jù)具體情況自行設(shè)計。采用哪種構(gòu)造哈希函數(shù)的方法取決于建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài))總的原則是使產(chǎn)生沖突的可能性盡可能的小。處理沖突的方法開放定址法再散列法鏈地址法（拉鏈法）建立一個公共溢出區(qū)開放定址法開放定址法處理沖突的基本思想是：當(dāng)發(fā)生沖突時，使用某種方法在散列表中形成一個探查序列，沿著此探查序列逐個單元的查找，直到找到給定的關(guān)鍵字或碰到一個開放的地址（即該單元為空）為止。開放定址法Hi=(H(key)+di)modm(i=1,2,…,m-1)其中，H(key)為散列函數(shù)，m為散列表長度，di為增量序列，有以下三種取法：di=1,2,…,m-1,稱為線性探查再散列，其探查單元序列為：d+1,d+2,…,m-1,0,…,d-1。di=12,-12,22,-22,32,…,+(-)k2,(k<=m/2),稱為二次探查再散列。di=偽隨機(jī)數(shù)序列，稱偽隨機(jī)探查再散列。例：在長度為11的哈希表中已填有關(guān)鍵字分別為17,60,29的記錄，現(xiàn)有第四個記錄，其關(guān)鍵字為38，由哈希函數(shù)得到地址為5，若用線性探測再散列，如下：開放定址法再散列法Hi=RHi(key)i=1,2,3,……，kRHi均是不同的哈希函數(shù)，在同義詞產(chǎn)生地址沖突時計算另一個哈希函數(shù)地址，直到?jīng)_突不再發(fā)生。缺點(diǎn)：增加了計算時間。建立一個公共溢出區(qū)前述方法中存在一個缺點(diǎn)：在填入過程中不顧后效，沖突的元素仍然被填入到Hash表的存儲空間中，而又無法預(yù)測被占用的空間以后是否有元素正常填入，從而填入過程中沖突的機(jī)會不斷增多。如果將沖突的元素安排在另外的空間里，而不占用hash表本身的空間，則就不會產(chǎn)生新的沖突。溢出Hash表包括Hash表和溢出表兩部分。在Hash表的填入過程中，將沖突的元素順序填入溢出表，而當(dāng)查找過程中發(fā)現(xiàn)沖突時，就在溢出表中進(jìn)行順序查找。溢出表是一個順序查找表。建立一個公共溢出區(qū)例將關(guān)鍵字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入長度為n＝12的溢出Hash表中。設(shè)Hash散列函數(shù)為i＝INT(k/3)＋1。拉鏈地址法基本思想是，散列表（向量）的每個元素由兩個域組成，一個域存放關(guān)鍵字，另一個域是一個地址指針，指向該關(guān)鍵字的同義詞，若無同義詞，該域?yàn)榭?。設(shè)關(guān)鍵字的個數(shù)是n，散列表長m，則同義詞子表的平均長度為n/m，很短。將所有關(guān)鍵字為同義詞的記錄存儲在同一線性鏈表中。拉鏈地址法著名的Hash算法MD4

MD4(RFC1320)是MIT的RonaldL.Rivest在1990年設(shè)計的，MD是MessageDigest的縮寫。它適用在32位字長的處理器上用高速軟件實(shí)現(xiàn)--它是基于32位操作數(shù)的位操作來實(shí)現(xiàn)的。MD5

MD5(RFC1321)是Rivest于1991年對MD4的改進(jìn)版本。它對輸入仍以512位分組，其輸出是4個32位字的級聯(lián)，與MD4相同。MD5比MD4來得復(fù)雜，并且速度較之要慢一點(diǎn)，但更安全，在抗分析和抗差分方面表現(xiàn)更好著名的Hash算法SHA-1及其他

SHA1是由NISTNSA設(shè)計為同DSA一起使用的，它對長