????查找（Search）又稱為搜索，指從數(shù)據(jù)表中找出符合條件的記錄。如今我們處在信息爆炸的大數(shù)據(jù)時代，如何從海量信息中快速找到需要的信息，就需要查找技術(shù)。如果有什么不懂得，要查詢得東西，都會在網(wǎng)上搜索一下，查找是最常見得應(yīng)用。

????查找算法得性能和下面幾個因素有關(guān)：

????1) 算法；

????2) 數(shù)據(jù)規(guī)模；

????3) 待查關(guān)鍵字在數(shù)據(jù)表中得位置;

? ? 4）查找得頻率;

????評價一個查找算法得好壞，一般采用平均查找長度（Average Search Length,ASL）來衡量。分為查找成功得平均查找長度和查找失敗得平均查找長度。平均查找長度的計算公式：

????其中，n為數(shù)據(jù)規(guī)模，pi為查找第i個記錄的概率，ci為查找第i個記錄所需要的關(guān)鍵字比較次數(shù)。

????根據(jù)在查找過程是否對表有修改，分為靜態(tài)查找和動態(tài)查找；

????根據(jù)數(shù)據(jù)結(jié)構(gòu)的不同又分為線性查找，樹查找和散列表查找。散列表查找是一種比較特殊的查找技術(shù)。

????線性表的查找非常簡單，如果線性表無序，則采用順序查找，如果線性表有序，則采用折半查找。

順序查找：

算法分析：

算法優(yōu)化：

折半查找：

（1）非遞歸算法

????????

（2）遞歸算法：

因為遞歸有自調(diào)用問題，那么就需要增加兩個參數(shù)low和high來標記搜索范圍的開始和結(jié)束。

哈希表：

線性表和樹表的查找都是通過比較關(guān)鍵字的方法，查找的效率取決于關(guān)鍵字的比較次數(shù)。有沒有一種查找方法，不進行關(guān)鍵字比較，直接找到目標？

????散列表是根據(jù)關(guān)鍵字直接進行訪問的數(shù)據(jù)結(jié)構(gòu)。散列表通過散列函數(shù)將關(guān)鍵字映射到存儲地址，建立了關(guān)鍵字和存儲地址之間的一種直接映射關(guān)系，這里的存儲地址可以是數(shù)字下標，索引，內(nèi)存地址等等。

????例如，關(guān)鍵字key = (17,24,48,25)，散列函數(shù)H(key) = key%5。散列函數(shù)將關(guān)鍵字映射到存儲地址下標，將關(guān)鍵字存儲到散列表的對應(yīng)位置。如圖所示：

????

????如果要查找48，就可以通過散列函數(shù)得到其存儲地址，直接找到該關(guān)鍵字。散列表查找的時間復雜度與表中的元素個數(shù)無關(guān)。理想情況下，散列表查找的時間復雜度為O(1)。但是，散列函數(shù)可能會把兩個或兩個以上的關(guān)鍵字映射到同一個地址，發(fā)生“沖突”，這種發(fā)生沖突的不同關(guān)鍵字稱為同義詞。例如，13通過散列函數(shù)計算的映射地址也是3，與48的映射地址相同，13和48為同義詞。因此，設(shè)計散列函數(shù)時應(yīng)盡量減少沖突，如果沖突無法避免，則需要設(shè)計處理沖突的方法。

????散列函數(shù)（Hash function）又稱為哈希函數(shù)，是將關(guān)鍵字映射到存儲地址的函數(shù)。

????記為：hash(key) = Addr。設(shè)計散列函數(shù)時需要遵循2個原則：

????1）散列函數(shù)盡可能簡單，能夠快速計算出任一關(guān)鍵字的散列地址。

????2）散列函數(shù)映射的地址應(yīng)均勻分布整個地址空間，避免聚集，以減少沖突。

散列函數(shù)設(shè)計原則為：簡單、均勻。

設(shè)計方法：

1.直接定址法

????直接取關(guān)鍵字的某個線性函數(shù)作為散列函數(shù)，散列函數(shù)形式如下：

????hash(key) = a*key + b,? 其中，a、b為常數(shù)。

????適用于事先知道關(guān)鍵字，關(guān)鍵字集合不是很大且連續(xù)性較好。關(guān)鍵字如果不連續(xù)，則有大量空位，造成空間浪費。

????例如，學生的學號{30331，30332，30333，30334，30335，......, 303369}。那么可以設(shè)計散列函數(shù)為：H(key) = key - 30330

????這樣可以將學生的學號直接映射到存儲地址下標。符合簡單均勻的原則。

2.除留余數(shù)法

????除留余數(shù)法是一種最簡單、最常用的構(gòu)造散列函數(shù)的方法，并且不需要事先知道關(guān)鍵字的分布。假定散列表的表廠為m，取一個不大于表廠的最大素數(shù)p,設(shè)計散列函數(shù)為：

????hash(key) = key%p

????為什么要選擇素數(shù)p?

????選擇p為素數(shù)的原因是為了避免沖突。因為在實際應(yīng)用中，訪問往往具有某種周期性，若周期與p有公共的素因子，則沖突的概率將急劇上升。例如，手表中的齒輪，兩個交合齒輪的齒數(shù)最好是互質(zhì)的。否則出現(xiàn)齒輪磨損絞斷的概率很大。因此，發(fā)生沖突的概率隨著p所含素因子的增多而迅速增大，素因子越多，沖突越多。

3.隨機數(shù)法

????隨機可以讓關(guān)鍵字分布的更均勻一些，因此可以將關(guān)鍵字隨機化，然后再使用除留余數(shù)法得到存儲地址。散列函數(shù)為：

????hash(key） = rand(key) % p

????其中，rand()為C、C++中的隨機函數(shù)，rand(n)表示求0~n-1的隨機數(shù)。p的取值和除留存余法相同。

4.數(shù)字分析法

????數(shù)字分析法根據(jù)每個數(shù)字在各個位上的出現(xiàn)概率，選擇均勻分布的若干位，作為散列地址。該方法適用于已知關(guān)鍵字集合，通過觀察分析得到。

????例如，一個關(guān)鍵字集合，如圖所示。第1，2位的數(shù)字完全相同，不需要考慮。4、7、8位的數(shù)字只有個別不同，而3、5、6位的數(shù)字均勻分布，可以將3，5，6位的數(shù)字作為散列地址，或者將3，5，6位的數(shù)字求和作為散列地址。

5.平方取中法

????對關(guān)鍵字平方后，按散列表大小，取中間的若干位作為散列地址（平方后截?。?。使用于事先不知道關(guān)鍵字的分布且關(guān)鍵碼的位數(shù)不是很大。

????例：散列地址為3位，則關(guān)鍵碼10123的散列地址位475：

????????????????????????????????10123**2 = 102475129

6.折疊法

????將關(guān)鍵字從左到右分割成位數(shù)相等的幾部分，將這幾部分疊加求和，取后幾位作為散列地址。適用于關(guān)鍵字位數(shù)很多，事先不知道關(guān)鍵字分布。折疊法分為 1）移位折疊和 2）邊界折疊兩種。

????移位折疊是將分割后的每個部分的最低位對齊，然后相加求和；

????邊界折疊如同折紙，將相鄰部分沿邊界來回折疊，然后對齊相加。

????例如：設(shè)關(guān)鍵字為 4 5 2 0 7 3 7 9 6 0 3,散列地址為三位。因為散列地址為3位，因此將關(guān)鍵字每3位劃分一塊，疊加后將進位舍去，移位疊加得到的散列地址位324，邊界疊加得到的散列地址位648.如下如所示。

7.基數(shù)轉(zhuǎn)換法

????例如，將十進制數(shù)轉(zhuǎn)換位其它的進制表示，如345的九進制表示為423。另外散列函數(shù)大多是基于整數(shù)的，如果關(guān)鍵字是浮點數(shù)，可以將關(guān)鍵字乘以M并四舍五入得到整數(shù)，再使用散列函數(shù)，或者將關(guān)鍵字表示為二進制數(shù)然后再使用散列函數(shù)；如果關(guān)鍵字是字符，可以將字符轉(zhuǎn)換R進制的整數(shù)，然后再使用散列函數(shù)。

8.全域散列法（很少用，了解）

????如果對關(guān)鍵字了解不多，可以使用全域散列法。即將多種備選的散列函數(shù)放在一個集合H中，在實際應(yīng)用中，隨機選擇其中的一個作為散列函數(shù)。如果任意兩個不同的關(guān)鍵字key1 ≠ key2，hash(key1) = hase(key2)的散列函數(shù)個數(shù)最多位H/m,H最為集合中散列函數(shù)的個數(shù)，m為表長，則稱H是全域的。

沖突處理方法

無論如何設(shè)計散列函數(shù)，都無法避免沖突問題。如果發(fā)生沖突，就需要進行沖突處理。沖突處理方法分為3種：開放地址法，鏈地址法，建立公共溢出區(qū)。

1.開放地址法

????開放地址法是在線性存儲空間上的解決方案，也稱為閉散列。當發(fā)生沖突時，采用沖突處理方法在線性存儲空間上探測其他的位置。

????根據(jù)增量序列的不同，開放地址法又分為線性探測、二次探測、隨機探測、再散列法。

????????????

????

????

2.鏈地址法

????鏈地址法又稱為拉鏈法。如果不同關(guān)鍵字通過散列函數(shù)映射到同一地址，這些關(guān)鍵字為同義詞，將所有的同義詞存儲在一個線性表中。查找、插入、刪除操作主要在這個鏈表中進行，拉鏈法使用于經(jīng)常進行插入，刪除的情況。

????例如，一組關(guān)鍵字（14，36，42，38，40，15，19，12，51，65，34，25），若表長為15，散列函數(shù)為 hash(key) = key%13，采用鏈地址法處理沖突，構(gòu)造該散列表。

????

3.建立公共溢出區(qū)

????除了以上處理沖突的方法之外，也可以建立一個公共溢出區(qū)，發(fā)生沖突時，將關(guān)鍵字放入公共溢出區(qū)中。查找時先根據(jù)待查找關(guān)鍵字的散列地址，在散列表中查找，如果為空則查找失??；如果非空且關(guān)鍵字不相等，則到公共溢出區(qū)中查找，如果仍未找到則查找失敗。