1.查找
概念
•設記錄表L=(R1 R2……Rn)，其中Ri(l≤i≤n)為記錄，對給定的某個值k，在表L中确定key=k的
記錄的過程，稱為查找。
•若表L中存在一個記錄Ri的key=k，記為Ri.key=k，則查找成功，傳回該記錄在表L中的序号i(或Ri 的位址)，否則(查找失敗)傳回0(或空位址Null)。
方法
查找方法有順序查找、折半查找、分塊查找、Hash表查找等等。查找算法的優劣将影響到計算機的使用效率，應根據應用場合選擇相應的查找算法。
平均查找長度
對查找算法，主要分析其T(n)。查找過程是key的比較過程，時間主要耗費在各記錄的key與給定k值的比較上。比較次數越多，算法效率越差（即T(n)量級越高），故用“比較次數”刻畫算法的T(n)。一般以“平均查找長度”來衡量T(n)。
平均查找長度ASL（Average Search Length）：對給定k，查找表L中記錄比較次數的期望值(或平均值)，即：
Pi為查找Ri的機率。等機率情況下Pi=1/n；Ci為查找Ri時key的比較次數(或查找次數)。
順序查找算法
對于順序查找算法，ASL=O(n)，效率是很低的，意味着查找某記錄幾乎要掃描整個表，當表長n很大時，會令人無法忍受。
折半查找算法
對給定值k，逐漸确定待查記錄所在區間，每次将搜尋空間減少一半(折半)，直到查找成功或失敗為止。
設兩個遊标low、high，分别指向目前待查找表的上界(表頭)和下界(表尾)。mid指向中間元素。
分塊查找
1.分塊
設記錄表長為n，将表的n個記錄分成b=n/s(向上取整)個塊，每塊s個記錄（最後一塊記錄數可以少于s個），即：
且表分塊有序，即第i（1≤i≤b-1）塊所有記錄的key小于第i+1塊中記錄的key，但塊内記錄可以無序。
2.建立索引
每塊對應一索引項：
其中kmax為該塊内記錄的最大key；link為該塊第一記錄的序号（或指針）。
例題
總結
順序、折半、分塊查找和樹表的查找中，其ASL的量級在O(n)～O(log2n)之間。
不論ASL在哪個量級，都與記錄長度n有關。随着n的擴大，算法的效率會越來越低。
ASL與n有關是因為記錄在存儲器中的存放是随機的，或者說記錄的key與記錄的存放位址無關，因而查找隻能建立在key的“比較”基礎上。（如何讓查找不建立在比較的基礎之上呢？）
2.hash表原理
2.1概念
理想的查找方法是：對給定的k，不經任何比較便能擷取所需的記錄，其查找的時間複雜度為常數級O(C)。
這就要求在建立記錄表的時候，确定記錄的key與其存儲位址之間的關系f，即使key與記錄的存放位址H相對應：
當要查找key=k的記錄時，通過關系f就可得到相應記錄的位址而擷取記錄，進而免去了key的比較過程。
這個關系f就是所謂的Hash函數（或稱散列函數、雜湊函數），記為H(key)。
它實際上是一個位址映象函數，其自變量為記錄的key，函數值為記錄的存儲位址（或稱Hash位址）。
不同的key可能得到同一個Hash位址，即當key1≠key2時，可能有H(key1)=H(key2)，此時稱key1和key2為同義詞。這種現象稱為“沖突”或“碰撞”，因為一個資料機關隻可存放一條記錄。
一般，選取Hash函數隻能做到使沖突盡可能少，卻不能完全避免。這就要求在出現沖突之後，尋求适當的方法來解決沖突記錄的存放問題。
根據選取的Hash函數H(key)和處理沖突的方法，将一組記錄(R1 R2……Rn)映象到記錄的存儲空間，所得到的記錄表稱為Hash表，如圖：
選取（或構造）Hash函數的方法很多，原則是盡可能将記錄均勻分布，以減少沖突現象的發生。以下介紹幾種常用的構造方法。
直接位址法
平方取中法
疊加法
保留除數法
随機函數法
2.2保留除數法
又稱質數除餘法，設Hash表空間長度為m，選取一個不大于m的最大質數p，令： H(key)=key%p。（質數：指在大于1的自然數中，除了1和它本身以外不再有其他因數的自然數。）
舉例
設記錄的key集合k={28，35，63，77，105……}，若選取p=21=3*7（包括質數因子7），有：
key：28 35 63 77 105 ……
H(key)=key%21： 7 14 0 14 0 ……
使得包含質數因子7的key都可能被映象到相同的單元，沖突現象嚴重。
若取p=19（質數），同樣對上面給定的key集合k，有：
key：28 35 63 77 105
H(key)=key%19： 9 16 6 1 10
H(key)的随機度就好多了。
2.3處理沖突的方法
選取随機度好的Hash函數可使沖突減少，一般來講不能完全避免沖突。設Hash表位址空間為0～m-l（表長為m）：
沖突是指：表中某位址j∈[0，m-1]中己存放有記錄，而另一個記錄的H(key)值也為j。
處理沖突的方法一般為：在位址j的前面或後面找一個空閑單元存放沖突的記錄，或将相沖突的諸記錄拉成連結清單。
在處理沖突的過程中，可能發生一連串的沖突現象，即可能得到一個位址序列H1、H2……Hn，Hi∈[0，m-l]。H1是沖突時選取的下一位址，而H1中可能己有記錄，又設法得到下一位址H2……直到某個Hn不發生沖突為止。這種現象稱為“聚積”，它嚴重影響了Hash表的查找效率。
沖突現象的發生有時并不完全是由于Hash函數的随機性不好引起的，聚積的發生也會加重沖突。
還有一個因素是表的裝填因子α，α=n/m，其中m為表長，n為表中記錄個數。一般α在0.7～0.8之間，使表保持一定的空閑餘量，以減少沖突和聚積現象。
2.3.1開放位址法
當發生沖突時，在H(key)的前後找一個空閑單元來存放沖突的記錄，即在H(key)的基礎上擷取下一位址：
Hi = ( H(key) + di ) % m
其中m為表長，%運算是保證Hi落在[0，m-l]區間；di為位址增量。di的取法有多種：
（1）di=1，2，3，……(m-1)——稱為線性探查法；
（2）di=1^2，-1^2，2^2，-2^2，……——稱為二次探查法。
舉例
設記錄的key集合k={23，34，14，38，46，16，68，15，07，31，26}，記錄數n=11。
令裝填因子α=0.75，取表長m= n/α =15（向上取整）。
用“保留餘數法”選取Hash函數（p=13）：
H(key) = key % 13
68對13取餘等于3，和16重複了，故帶入公式3+1對15取餘等于4，故68放到4的位置 ，其他同理
2.3.2鍊位址法
發生沖突時，将各沖突記錄鍊在一起，即同義詞的記錄存于同一連結清單。
設H(key)取值範圍（值域）為[0,m-1]，建立頭指針向量HP[m]，HP[i]（0≤i≤m-l）初值為空。
設H(key)=key%13，k={ 23，34，14，38，46，16，68，15，07，31，26 }
鍊位址法解決沖突的優點：無聚積現象；删除表中記錄容易實作。
3.hash表的實作
#define N 15
typedef int datatype;
typedef struct node { // 鍵值對兒，這裡和python的字典有點不一樣
datatype key; // 值
datatype value; // 是H(key)，即key所對應的位置
struct node * next;
}listnode, *linklist;
typedef struct {
listnode data[N];
}hash;
建立
hash * hash_create() {
hash * HT; // 整個hash表
if ((HT = (hash *)malloc(sizeof(hash))) == NULL) {
printf("malloc failed\n");
return NULL;
}
memset(HT, 0, sizeof(hash)); // 這樣寫效率更高，使得諸如data[11].key、data[11].value都為0
return HT;
}
插入
int hash_insert(hash *HT, datatype key) {
linklist p, q;
if (HT == NULL) {
printf("HT is NULL\n");
return -1;
}
if ((p = (linklist)malloc(sizeof(listnode))) == NULL) { // 建立新節點
printf("malloc failed\n");
return -1;
}
// 初始化新節點中的值
p->key = key;
p->value = key % N;
p->next = NULL;
q = &(HT->data[key % N]); // HT->data[key % N]是一個節點，此時q指向hash表中key待插入的位置
// 如果q->next為1，表明key的待插入位置（即H(key)）已經插入過節點了
// 由于插入是順序插入，是以要比較新插入的節點的key和已有的節點的key哪個大，大的放後面
while (q->next && q->next->key < p->key ) {
q = q->next;
}
p->next = q->next;
q->next = p;
return 0;
}
查找
// 先找hash表中對應的位置，再看這個位置有沒有重複的
linklist hash_search(hash *HT, datatype key) {
linklist p;
if (HT == NULL) {
printf("HT is NULL\n");
return NULL;
}
p = &(HT->data[key % N]);
while (p->next && p->next->key != key) {
p = p->next;
}
if (p->next == NULL) {
return NULL;
} else {
printf("found\n");
return p->next;
}
}
相關題目
1、下面關于二分查找的叙述正确的是（ ）。
A．表必須有序，表可以順序方式存儲，也可以連結清單方式存儲
B．表必須有序且表中資料必須是整型，實型或字元型
C．表必須有序，而且隻能從小到大排列
D．表必須有序，且表隻能以順序方式存儲
2、請說出順序表查找的特點？
3、設hash表長度為14，hash函數是 H(key) = key % 11 ，表中已有資料的關鍵字為15,38,61,84共四個，現要将關鍵字為49的結點加到表中，用二次探查法處理沖突，則放入的位置是（ ）。
A.8 B. 3 C. 5 D. 9
4、将10個元素散列到100000個單元的哈希表中，則（ ）産生沖突。
A. 一定會 B. 一定不會 C. 仍可能會
5、已知一個線性表(38,25,74,63,52,48)，采用的散列函數為H(Key)=Key mod 7，将元素散列到表長為7的哈希表中存儲。若采用線性探測的開放定址法解決沖突，則在該散清單上進行等機率成功查找的平均查找長度為 __________。
A. 1.5 B. 1.7 C. 2.0 D. 2.3
答案
1.D
2.算法簡單，對表的結構無任何要求，無論是用向量還是用連結清單來存放結點，也無論結點之間是否按關鍵字有序，它都同樣适用。
但查找效率低，是以，當表長較大時不宜采用順序查找。
3.D
4.C
5.C，38-3（1次）25-4（1次）74-5（2次）63-0（1次）52-6（4次）48-1（3次）故計算的（1+1+2+1+4+3）/6=2