大三黨，大資料專業，正在為面試準備，歡迎學習交流，`

文章中總結了四種常見的查找方法，內容包括了基本概念及代碼實作，內容較多，特別是哈希查詢的內容比較多，可能有所遺漏，但是總結了大部分的內容，
附帶一本熱銷的電子書配套適用更佳，鏈接如下
大話資料結構
提取碼：mazy

往期文章
緒論-資料結構的基本概念
緒論-演算法
線性表-順序表和鏈式表概念及其代碼實作

1 常見的查找演算法

• 順序查找
• 二分查找
• 索引查找
• 哈希查找

2 平均查找長度ASL比較查找演算法性能

公式：ASL=P1C1+P2C2+…+PnC

Pi——查找第i個元素的概率
Ci——查找第i個元素需要的比較次數

3 順序查找

3.1 順序查找的思想

• 從表中指定位置（一般為最后一個，第0個位置設為崗哨）
  的記錄開始，沿某個方向將記錄的關鍵字與給定值相比較，
  若某個記錄的關鍵字和給定值相等，則查找成功；
• 反之，若找完整個順序表，都沒有與給定關鍵字值相等的
  記錄，則此順序表中沒有滿足查找條件的記錄，查找失敗，

3.2 順序查找代碼

int seqsearch(DataType R[], KeyType key)
{
R[0]=key, i=n;//第一個位置設為崗哨
while (R[i] != key) 
i=i-1;//從最后一個位置往前查找
return i;
}

3.3 順序表上順序查找的平均查找長度（性能分析）

對于順序表的
Ci=n-i+1
Pi =1/n
則可以得到如下計算結果（等引數列的計算）：

4 折半查找

4.1 折半查找的前提條件及查找程序

前提條件
如果順序表中的紀律按關鍵字值有序即R[i].≤R[i+1]，i=1,2,…,n-1，則稱順序表為有序表，

4.2 折半查找代碼

int BinarySearch(DataType SL[], KeyType key, int n){
/*在長度為n的有序表SL中折半查找其關鍵字等于key的記錄*/
/*查找成功回傳其在有序表中的位置，查找失敗否回傳0*/
int low=1;
int high=n;
while(low<=high){
mid=(low+high)/2;//取整 小的數 右邊的數
if(key = = SL[mid]) 
{
  return mid;
}
else if( key>SL[mid])//查找值在左邊 移動low
low=mid+1;
else //查找值在右邊 移動low 
high=mid-1;
}
return 0;
}

查找程序
將待查關鍵字與有序表中間位置的記錄進行比較，若相等，查找成功，若小于，則只可能在有序表的前半部分，若大于則只可能在有序表的后半部分，因此，經過一次比較，就將查找范圍縮小一半，這樣一直進行下去直到找到所需記錄或記錄不在查找表中，

4.3 折半查找的性能分析

引入判定樹

其中6查找一次，3 9查找兩次，1 4 7 10 查找3次，2 5 8 11 查找4次，

4.4 折半查找特點

• 折半查找的查找效率高；
• 平均查找性能和最壞性能相當接近；
• 折半查找要求查找表為有序表；
• 并且，折半查找只適用于順序存盤結構

5 索引查找

5.1 索引的使用方法

• 先分析資料規律，建立索引
• 再根據索引進行快速定位
• 在定位的地方進行細致搜索

5.2 索引表的構建

1. 分塊：第Rk 塊中所有關鍵字< Rk+1塊中所有關鍵字，（k=1, 2, …, L-1）
2. 建立索引項：關鍵字項：記載該塊中最大關鍵字值； 指標項： 記載該塊第一個記錄在表中位置，
3. 建立索引表：所有索引項組成索引表
   如下圖展示
   
   索引項展示
   

5.3 索引查找代碼

typedef struct IndexType
{
KeyType key;//最大關鍵字
int Link;  //地址項
} IndexType;

int IndexSequelSearch(IndexType ls[], DataType s[], int m, KeyType key){
/*索引表為ls[0]-ls[m-1]，順序表為s*/
i=0;
while(i<m && key>ls [i ].key) i++; /*塊間查找*/
if(i==m)return -1; /*查找失敗*//*不在查找范圍內*/
else{ /*在塊內順序查找*/
j=ls[ i ].Link;
while(Key!=s[j].key && j<ls[ i+1 ].Link) //j<是為了不超出當前塊
j++;
if(key = = s[j].key)return j; /*查找成功*/
else return -1; /*查找失敗*/
}
}

5.4 索引順序查找的ASL

ASL=ASL(索引表）+ASL（塊內）

6 三種查找演算法的比較

7 哈希查找

7.1 哈希查詢的思想

以學號查詢為例子，取給定學號的后三位，不需要經過比較，便可直接從查找表中找到給定學生的記錄，因為如下圖我們建立了關鍵字和存盤地址之間的映射關系，

7.2 哈希函式的定義

一般情況下，需在關鍵字與記錄在表中的存盤位置之間建立一個函式關系，以 H(key) 作為關鍵字為key 的記錄在表中的位置，通常稱這個函式 h(key) 為哈希函式，

• 哈希函式是一個映象，即：將關鍵字的集合映射
  到某個地址集合上， 它的設定很靈活，只要這個地
  址集合的大小不超出允許范圍即可；

• 由于哈希函式是一個壓縮映象，因此，在一般
  情況下，很容易產生“沖突”現象，即： key1！=
  key2，而 h(key1) = h(key2)，例如下圖 key分別是100和1000
  

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

7.3 哈希表的定義

根據設定的哈希函式 H(key) 和提供的處理沖突的方法，將一組關鍵字映象到一個地址連續的地址空間上，并以關鍵字在地址空間中的“象”作為相應記錄在表中的存盤位置，如此構造所得的查找表稱之為哈希表，

7.4 常見的哈希函式

7.4.1 直接哈希函式

7.4.2 數字分析法

7.4.3 平方去中法

思想：以關鍵字的平方值的中間幾位作為存盤地址，求“關鍵字的平方值” 的目的是“擴大差別”和“貢獻均衡”，

7.4.4 折疊法

7.4.5 除留余數法

7.4.6 亂數法

7.5 哈希函式選取通常需要考慮的因素

• 計算哈希函式所需時間；
• 關鍵字的長度；
• 哈希表的大小；
• 關鍵字的分布情況；
• 記錄的查找頻率，

7.6 哈希函式沖突的處理方法

7.6.1 開放地址法

為產生沖突的地址H(key)重新求得求得一個地址序列，通過如下的公式：
H0 = H(key)
Hi = ( H(key) + di) MOD m
H0, H1, H2, …, Hs 1≤ s≤m-1

• Hi 為第i次沖突的地址
• H(key)為Hash函式值
• m 為Hash表表長
• di 為增量序列

對于di的取法有是三種，如下圖：

由于并不復雜我們以線性探測再散列舉例：

關鍵字 { 19, 01, 23, 14, 55, 68, 11, 82, 36 }

設定哈希函式 H(key) = key MOD 11 ( 表長=11 )

選用線性探測再散列處理沖突

• 19/11=7 沒有沖突 放入表中
• 1/11=1 沒有沖突 放入表中
• 23/11=1 產生沖突 1的位置已經存放了，使用函式 Hi = ( H(key) + di) MOD m，第一次沖突di取1 H1 = ( H(key) + di) MOD m=（23+1）mod 11=2 放入2
• 依次類推 沖突一次 di依次取 1 2 3 4 5（實際意義就是往右邊找空格子）
• 最終結果如下，下方數次表示第幾次成功
  
• 計算ASL(成功)=(1+1+2+1+3+6+2+5+1)/9
• 計算ASL(失敗)=(9+8+7+6+5+4+3+2+1)/9（假設格子如圖占完 余數從0~8要查找幾次后再能解決沖突 得到了如上數字計算）

7.6.2 再哈希法

第一次沖突使用RH1哈希函式
第二次沖突使用RH2哈希函式
…
每次對應不同的哈希函式

7.6.3 鏈地址法

重點關注一下ASL失敗怎么求，同上

7.6.4 公共溢位區法

7.7 哈希表查找代碼實作及實體

思想：

• 給定K值，根據構造表時所用的哈希函式求哈希地址j
• 若此位置無記錄, 則查找不成功；否則比較關鍵字，若和給定的關鍵字相等則成功； 否則根據構造表時設定的沖突處理的方法計算“下一地址”， 重復2）

Status SearchHash(HashTable H, KeyType key, int &p, int &c){
/*在開放定址哈希表H中查找關鍵字為key的資料*/
/*用c記錄發生沖突的次數，初值為0*/
p=Hash(k); /*求哈希地址*/
while(H.data[p].key!=NULL && H.data[p].key!=key)
/*該位置填有資料且與所查關鍵字不同*/
collision(p, ++c); /*求下一探查地址p*/
if(H.data[p].key==key )
return SUCCESS; /*查找成功,p回傳待查資料元素位置*/
else return UNSUCCESS; /*查找不成功,p回傳插入位置*/
}

Status InsertHash(HashTable &H, DataType e){
/*查找不成功時在H中插入資料元素e，并回傳SUCCESS*/
/*若沖突次數過大，則重建哈希表*/
c=0;
if(SearchHash (H, e.key, p, c))
return UNSUCCESS; /*資料已在哈希表中，不需插入*/
else if(c<hashsize[H.sizeindex]/2){
H.data[p]=e; ++H.count; /*次數c還未達到上限，插入e*/
return SUCCESS;
}
else {
RecreatHashTable(H); /*重建哈希表，當哈希表用了一半以上的空間*/
return SUCCESS;
}
}

查找實體

7.8 哈希查找性能分析

實際上，哈希表的ASL是處理沖突方法和裝載因子α 的函式

哈希表的平均查找長度是裝填因子 α 的函式，而不是 n 的函式，這說明，用哈希表構造查找表時，可以選擇一個適當的裝填因子 α，使得平均查找長度限定在某個范圍，

1. 選擇哈希函式
2. 給定平均查找長度
3. 根據沖突策略（隨機探測 線性探測 鏈地址）選擇對應的公式求出α裝載因子
4. 由裝載因子和我們關鍵字（資料）個數求的表長 裝載因子=關鍵字個數/表長
5. 建立查找表

總結

內容較多，可能有所遺漏和錯誤的地方，歡迎指出，

附帶一本熱銷的電子書配套適用更佳，鏈接如下
大話資料結構
提取碼：mazy

往期文章
緒論-資料結構的基本概念
緒論-演算法
線性表-順序表和鏈式表概念及其代碼實作