計(jì)算機(jī)

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

順序查找順序查找又稱順序搜索。其基本方法是：從線性表的第一個(gè)元素開(kāi)始，依次將線性表中的元素與被查元素進(jìn)行比較，若相等則表示查找成功；若線性表中所有的元素都與被查元素進(jìn)行了比較但都不相等，則表示線性表中沒(méi)有要找的元素，即查找失敗。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ǎn)單而且適用性廣，對(duì)查找表的結(jié)構(gòu)無(wú)要求。無(wú)論表內(nèi)元素是否有序均可應(yīng)用，對(duì)于線性鏈表也適用。缺點(diǎn)：平均查找次數(shù)較大，特別是n值較大時(shí)，查找效率較低。如果線性表為無(wú)序表，則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，都只能用順序查找。即使是有序線性表，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能用順序查找。有序表查找的分類根據(jù)確定中間位置的方法不同，分為折半查找斐波納契查找插值查找折半查找思想：將給定的查找關(guān)鍵字K與線性表的中間位置上的元素進(jìn)行比較，若相等則查找成功。若不等，中間元素將表分為兩部分，前一部分的元素均小于中間元素，后一部分的元素均大于中間元素。根據(jù)和中間元素的比較結(jié)果，選擇一部分重復(fù)進(jìn)行上述過(guò)程，直到查找成功或失敗。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個(gè)(20)，即中間值2次比較就查找成功的元素有2個(gè)(21)，即1/4(或3/4)處3次比較就查找成功的元素有2個(gè)(22)，即1/8(或3/8)處第m次比較就查找成功的元素有2m-1個(gè)為方便起見(jiàn)，假設(shè)表中所有n元素=2n-1，此時(shí)不討論第m次比較后還有剩余元素的情況。假設(shè)查找每個(gè)元素的概率相等。分塊查找分塊有序：將線性表分成若干個(gè)塊B1、B2、…、Bn，并要求當(dāng)i<j時(shí)，Bi中的記錄關(guān)鍵字都小于Bj中記錄的關(guān)鍵字。索引表：每個(gè)塊在索引表中有一項(xiàng)，稱為索引項(xiàng)。索引項(xiàng)中包括兩個(gè)域，一個(gè)域存放塊中記錄關(guān)鍵字的最大值，另一個(gè)域存放塊的第一個(gè)記錄在線性表中的位置。分塊查找索引表最大關(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)中的相對(duì)位置是隨機(jī)的，即和記錄的關(guān)鍵字之間不存在確定的關(guān)系，因此，在結(jié)構(gòu)中查找記錄時(shí)需進(jìn)行一系列和關(guān)鍵字的比較。這一類查找方法建立在“比較“的基礎(chǔ)上，查找的效率依賴于查找過(guò)程中所進(jìn)行的比較次數(shù)。理想的情況是能直接找到需要的記錄，因此必須在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系f，使每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)。Hash表哈希表最常見(jiàn)的例子是以學(xué)生學(xué)號(hào)為關(guān)鍵字的成績(jī)表，１號(hào)學(xué)生的記錄位置在第一條，１０號(hào)學(xué)生的記錄位置在第１０條...如果我們以學(xué)生姓名為關(guān)鍵字，如何建立查找表，使得根據(jù)姓名可以直接找到相應(yīng)記錄呢？Hash表Hash表上面這張表即哈希表。如果將來(lái)要查李秋梅的成績(jī)，可以用上述方法求出該記錄所在位置：李秋梅:lqm12+17+13=42取表中第42條記錄即可。問(wèn)題：如果兩個(gè)同學(xué)分別叫劉麗劉蘭該如何處理這兩條記錄？這個(gè)問(wèn)題是哈希表不可避免的，即沖突現(xiàn)象：對(duì)不同的關(guān)鍵字可能得到同一哈希地址。Hash表的基本概念若結(jié)構(gòu)中存在和關(guān)鍵字K相等的記錄，則必定在f(K)的存儲(chǔ)位置上。由此，不需比較便可直接取得所查記錄。稱這個(gè)對(duì)應(yīng)關(guān)系f為散列函數(shù)(Hashfunction)，按這個(gè)思想建立的表為散列表。問(wèn)題：上面例子中的散列函數(shù)是什么？問(wèn)題：如果兩個(gè)同學(xué)分別叫劉麗劉蘭該如何處理這兩條記錄？Hash表的基本概念對(duì)不同的關(guān)鍵字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，這種現(xiàn)象稱沖突。具有相同函數(shù)值的關(guān)鍵字對(duì)該散列函數(shù)來(lái)說(shuō)稱做同義詞。根據(jù)散列函數(shù)H(key)和處理沖突的方法將一組關(guān)鍵字映象到一個(gè)有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“象”作為記錄在表中的存儲(chǔ)位置，這種表便稱為散列表，這一映象過(guò)程稱為散列造表或散列，所得的存儲(chǔ)位置稱散列地址。Hash表提供了快速的插入操作和查找操作。不論哈希表中有多少數(shù)據(jù)，只需要接近常量的時(shí)間即0(1）的時(shí)間級(jí)。實(shí)際上，這只需要幾條機(jī)器指令Hash表的基本概念Hash表是基于快速存取的角度設(shè)計(jì)的，是一種典型的以空間換取時(shí)間的做法。必須在原有數(shù)據(jù)占用的空間之外利用額外的空間構(gòu)造Hash表。哈希表基于數(shù)組的，數(shù)組創(chuàng)建后難于擴(kuò)展。某些哈希表被基本填滿時(shí)，性能下降得非常嚴(yán)重，所以程序員必須要清楚表中將要存儲(chǔ)多少數(shù)據(jù)（或者準(zhǔn)備好定期地把數(shù)據(jù)轉(zhuǎn)移到更大的哈希表中，這是個(gè)費(fèi)時(shí)的過(guò)程）。沒(méi)有一種簡(jiǎn)便的方法可以以任何一種順序〔例如從小到大〕遍歷表中數(shù)據(jù)項(xiàng)。如果需要這種能力，就只能選擇其他數(shù)據(jù)結(jié)構(gòu)。Hash表的關(guān)鍵散列函數(shù)的構(gòu)造方法直接定址法數(shù)字分析法平方取中法折疊法隨機(jī)數(shù)法除留余數(shù)法處理沖突的方法開(kāi)放地址法再散列法鏈地址法（拉鏈法）建立一個(gè)公共溢出區(qū)直接定址法取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址。即H(key)=key或H(key)=a?key+b，其中a和b為常數(shù)（這種散列函數(shù)叫做自身函數(shù)）有一個(gè)從1到100歲的人口數(shù)字統(tǒng)計(jì)表，其中，年齡作為關(guān)鍵字，哈希函數(shù)取關(guān)鍵字自身。但這種方法效率不高,時(shí)間復(fù)雜度是O(1),空間復(fù)雜度是O(n),n是關(guān)鍵字的個(gè)數(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ī)會(huì)增加，所以盡量不取前三位，取后三位比較好。因此數(shù)字分析法就是找出數(shù)字的規(guī)律，盡可能利用這些數(shù)據(jù)來(lái)構(gòu)造沖突幾率較低的散列地址。平方取中法以關(guān)鍵字的平方值的中間幾位作為存儲(chǔ)地址。求“關(guān)鍵字的平方值”的目的是“擴(kuò)大差別”，同時(shí)平方值的中間各位又能受到整個(gè)關(guān)鍵字中各位的影響。此方法適合于:關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象。構(gòu)造Hash表構(gòu)造Hash表的方法很多，用戶可根據(jù)具體情況自行設(shè)計(jì)。采用哪種構(gòu)造哈希函數(shù)的方法取決于建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài))總的原則是使產(chǎn)生沖突的可能性盡可能的小。處理沖突的方法開(kāi)放定址法再散列法鏈地址法（拉鏈法）建立一個(gè)公共溢出區(qū)開(kāi)放定址法開(kāi)放定址法處理沖突的基本思想是：當(dāng)發(fā)生沖突時(shí)，使用某種方法在散列表中形成一個(gè)探查序列，沿著此探查序列逐個(gè)單元的查找，直到找到給定的關(guān)鍵字或碰到一個(gè)開(kāi)放的地址（即該單元為空）為止。開(kāi)放定址法Hi=(H(key)+di)modm(i=1,2,…,m-1)其中，H(key)為散列函數(shù)，m為散列表長(zhǎng)度，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ī)探查再散列。例：在長(zhǎng)度為11的哈希表中已填有關(guān)鍵字分別為17,60,29的記錄，現(xiàn)有第四個(gè)記錄，其關(guān)鍵字為38，由哈希函數(shù)得到地址為5，若用線性探測(cè)再散列，如下：開(kāi)放定址法再散列法Hi=RHi(key)i=1,2,3,……，kRHi均是不同的哈希函數(shù)，在同義詞產(chǎn)生地址沖突時(shí)計(jì)算另一個(gè)哈希函數(shù)地址，直到?jīng)_突不再發(fā)生。缺點(diǎn)：增加了計(jì)算時(shí)間。建立一個(gè)公共溢出區(qū)前述方法中存在一個(gè)缺點(diǎn)：在填入過(guò)程中不顧后效，沖突的元素仍然被填入到Hash表的存儲(chǔ)空間中，而又無(wú)法預(yù)測(cè)被占用的空間以后是否有元素正常填入，從而填入過(guò)程中沖突的機(jī)會(huì)不斷增多。如果將沖突的元素安排在另外的空間里，而不占用hash表本身的空間，則就不會(huì)產(chǎn)生新的沖突。溢出Hash表包括Hash表和溢出表兩部分。在Hash表的填入過(guò)程中，將沖突的元素順序填入溢出表，而當(dāng)查找過(guò)程中發(fā)現(xiàn)沖突時(shí)，就在溢出表中進(jìn)行順序查找。溢出表是一個(gè)順序查找表。建立一個(gè)公共溢出區(qū)例將關(guān)鍵字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入長(zhǎng)度為n＝12的溢出Hash表中。設(shè)Hash散列函數(shù)為i＝INT(k/3)＋1。拉鏈地址法基本思想是，散列表（向量）的每個(gè)元素由兩個(gè)域組成，一個(gè)域存放關(guān)鍵字，另一個(gè)域是一個(gè)地址指針，指向該關(guān)鍵字的同義詞，若無(wú)同義詞，該域?yàn)榭?。設(shè)關(guān)鍵字的個(gè)數(shù)是n，散列表長(zhǎng)m，則同義詞子表的平均長(zhǎng)度為n/m，很短。將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在同一線性鏈表中。拉鏈地址法著名的Hash算法MD4

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

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

SHA1是由NISTNSA設(shè)計(jì)為同DSA一起使用的，它對(duì)長(zhǎng)