重學數據結構（八、查找）
@
查找是各種軟件系統中經常用到的操作。查找的效率非常重要，大型的系統尤其如此。
一、查找的基本概念
首先來看一些查找的基本概念和術語。
-
查找表
查找表是由同一類型的數據元素（或記錄）構成的集合。由於 「集合」 中的數據元素之間存在着完全鬆散的關係，因此查找表是一種非常靈活的數據結構，可以利用其他的數據結構來實現，例如線性表、樹表及散列表等。 -
關鍵字
關鍵字是數據元素（或記錄） 中某個數據項的值，用它可以標識一個數據元素（或記錄）。若此關鍵字 可以唯一地標識一個記錄，則稱此關鍵字為主關鍵字（對不同的記錄，其主關鍵字均不同）。反之，稱用以識別若千記錄的關鍵字為次關鍵字。當數據元素只有一個數據項時，其關鍵字即為該數據元素的值。 -
查找
查找是指根據給定的某個值，在查找表中確定一個其關鍵字等千給定值的記錄或數據元素。若表中存在這樣的一個記錄， 則稱查找成功，此時查找的結果可給出整個記錄的信息，或指示該記錄在查找表中的位置；若表中不存在關鍵字等於給定值的記錄，則稱查找不成功，此時查找的結果可給出一個 「空」 記錄或 「空」 指針。 -
動態查找表和靜態查找表
若在查找的同時對錶做修改操作（如插入和刪除），則相應的表稱之為動態查找表，否則稱之為靜態查找表。換句話說，動態查找表的表結構本身是在查找過程中動態生成的，即在創建表時，對千給定值， 若表中存在其關鍵字等於給定值的記錄， 則查找成功返回；否則插入關鍵字等千給定值的記錄。 -
平均查找長度
為確定記錄在查找表中的位置，需和給定值進行比較的關鍵字個數的期望值，稱為查找算法，在查找成功時的平均查找長度(Average Search Length, ASL)。
二、線性表的查找
在查找表的組織方式中，線性表是最簡單的一種。
1、順序查找
1.1、基本思想
在表的組織方式中，線性表是最簡單的一種。而順序查找是線性表查找中最簡單的一種。
順序查找的基本思想：從表的一端開始，順序掃描線性表，依次掃描到的結點關鍵字和給定的K值相比較，若當前掃描到的結點關鍵字與 K相等，則查找成功；若掃描結束後，仍未找到關鍵字等於 K的結點，則查找失敗。
順序査找方法既適用於線性表的順序存儲結構，也適用於線性表的鏈式存儲結構。
1.2、算法實現
/**
* 順序查找
* @param data
* @param key
* @return
*/
public int linearSearch(int[] data,int key){
//遍歷查找
for (int i=0;i<data.length;i++){
//查找到
if (key==data[i]){
return i;
}
}
//沒有查找到
return -1;
}
1.3、算法分析
成功時的順序査找的平均査找長度為:
在數據量為n的情況下，線性表的平均查找長度：
(n+……+2+1)/n=(n+1)/2
順序查找需要從頭開始不斷地按順序檢查數據，因此在數據量大且目標數據靠後，
或者目標數據不存在時，比較的次數就會更多，也更為耗時。若數據量為 n，線性查找的時間複雜度便為 O(n)。
所以雖然順序查找比較簡單，且對錶的結構無任何要求，但是查詢效率較低，所以當n較大時不宜採用順序査找。
2、二分查找
二分查找也叫折半查找。
2.1、基本思想
二分查找是一種效率相對較高的線性表查找方式，它要求被查找的線性表是有序的。
二分查找的基本思想是：先確定待查找記錄所在的範圍(區間)，然後逐步縮小範圍直到找到或找不到該記錄為止。
具體步驟如下：
- (1) 首先確定該區間的中點位置：mid=(low +high)/ 2
- (2) 然後將待查的 A：值與 R[mid].key 比較。若相等，則査找成功並返回此位置，否則須確定新的査找區間，繼續二分査找。具體如下：
① 若R[mid].key>K：,則由表的有序性可知 R[mid…n].keys 均大於 K，因此若表中存在關鍵字等於尺的結點，則該結點必定是在位置 mid 左邊的子表及[1…mid- 1]中，故新的査找區間是左子表R[1,……,mid-1]。
② 類似地，若R[mid].key<K：，則要査找的 K必在 mid 的右子表R[mid+1,……,n]中，即新的査找區間是右子表R[mid+1,……n]。下一次查找是針對新的查找區間進行的。
2.2、算法實現
- 非遞歸實現：
/**
* 二分查找-非遞歸
* @param data
* @param key
* @return
*/
public int binarySearch(int[] data,int key){
int mid; //置查找區間初值
int left=0;
int right=data.length-1;
while (left<right){
mid=(left+right)/2;
if (key==data[mid]){ //找到待查元素
return mid;
}else if (key>data[mid]){ //在右子表查找
left=mid+1;
mid=(left+right)/2;
}else{ //在左子表查找
right=mid-1;
mid=(left+right)/1;
}
}
return -1; //沒有查找到待查元素
}
- 遞歸實現
/**
* 二分查找-遞歸
*
* @param data
* @param left
* @param right
* @param key
* @return
*/
public int binarySearchRescu(int[] data, int left, int right, int key) {
if (left > right) {
return -1;
}
int mid = (left + right) / 2;
if (key == data[mid]) {
return mid;
} else if (key > data[mid]) { //在右子表查找
return binarySearchRescu(data, mid + 1, right, key);
} else {
return binarySearchRescu(data, left, mid - 1, key);
}
}
2.3、算法分析
折半查找的時間複雜度為 O(log2n）, 折半查找的效率比順序查找高，但折半查找只適用千有序表，且限於順序存儲結構。
折半查找的優點是：比較次數少，查找效率高。其缺點是：對錶結構要求高，只能用於順序存儲的有序表。
如果對無序表進行二分查找，查找前需要排序，而排序本身是一種費時的運算。同時為了保持順序表的有序性，對有序表進行插入和刪除時，平均比較和移動表中一半元素，這也是一種費時的運算。因此，折半查找不適用於數據元素經常變動的線性表。
3、分塊查找
分塊查找又稱索引順序查找。它是把順序查找和二分査找相結合的一種查找方法，即把線性表分成若干塊，塊和塊之間有序，但每一塊內的結點可以無序。
分塊查找的基本思想是：確定被査找的結點所在的塊(採用二分查找法)後，對該塊中的結點採用順序查找。
分塊査找介於順序和二分查找之間，其優點是：在表中插入或刪除一個記錄時，只要找到該記錄所屬的塊，就在該塊內進行插入和刪除運算。分塊査找的主要代價是增加一個輔助數組的存儲空間和將初始表分塊排序的運算
三、樹表的查找
在重學數據結構（六、樹和二叉樹） 里，對大量的輸進行了詳細的描述和實現，所以針對樹表的查找，下面只是是做一些簡單的描述。
1、二叉排序樹
當用線性表作為表的組織形式時，可以用 3 種查找法。其中以二分査找效率最高。但由於二分査找要求表中結點按關鍵字有序，且不能用鏈表作存儲結構，因此，當表的插入或刪除操作頻繁時，為維護表的有序性，勢必要移動表中很多結點。這種由移動結點引起的額外時間開銷，就會抵消二分査找的優點。也就是說，二分查找只適用於靜態查找表。若要對動態查找表進行高效率的查找，最好使用二叉排序樹。
1.1、二叉排序樹基本概念
二叉排序樹又稱為是二叉查找樹或二叉搜索樹。二叉排序樹是具有下列性質的二叉樹：
- 若左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；
- 若右子樹不空，則右子樹上所有結點的值均大於或等於它的根結點的值；
- 左、右子樹也分別為二叉排序樹；
- 沒有鍵值相等的節點。
1.2、二叉排序樹特點
由 BST性質可得：
-
(1) 二叉排序樹中任一結點x，其左(右)子樹中任一結點y若存在)的關鍵字必小(大)於 x 的關鍵字。
-
(2) 二叉排序樹中，各結點關鍵字是惟一的。
需要注意的是在實際應用中，不能保證被查找的數據集中各元素的關鍵字互不相同，所以可將二叉排序樹定義中 BST 性質⑴ 里的「小於」改為「大於等於」，或將 BST性質(2)里的「大於」改為「小於等於」，甚至可同時修改這兩個性質。 -
(3) 按中序遍歷該樹所得到的中序序列是一個遞增有序序列。
1.3、二叉查找樹的操作
- 查找：因為二叉排序樹可以看成是一個有序表，所以在二叉排序樹上進行查找和折半查找類似， 也 是一個逐步縮小查找範圍的過程。
- 插入和生成
已知一個關鍵字值為 key 的結點 s, 若將其插入到二叉排序樹中，只要保證插入後仍符合二叉排序樹的定義即可。插入可以用下面的方法進行：
- (1) 若二叉樹序樹是空樹，則 key 成為二叉樹序樹的根；
- (2) 若二叉樹序樹非空，則將 key 與二叉樹序樹的根進行比較，如果 key 的值等於根結點的值，則停止插入，如果 key 的值小於根結點的值，則將 key 插入左子樹，如果 key的值大於根結點的值，則將 key 插入右子樹。
2、平衡二叉樹
二叉樹雖然利於查找，但是存在一個最壞的情況——二叉樹退化為線性表。
所以就需要就需要引入一些特性來使二叉樹保持平衡。
例如最早提出的平衡二叉樹AVL樹，是具有如下特性的二叉樹：
- (1 ) 左子樹和右子樹的深度之差的絕對值不超過1;
- (2) 左子樹和右子樹也是平衡二叉樹。
3、B樹
B樹也是一種平衡查找樹，不過不是二叉樹。
B樹也稱B-樹，它是一種多路平衡查找樹。
一棵m階的B樹定義如下：
- 每個節點最多有m-1個關鍵字（可以存有的鍵值對）。
- 根節點最少可以只有1個關鍵字。
- 非根節點至少有m/2個關鍵字。
- 每個節點中的關鍵字都按照從小到大的順序排列，每個關鍵字的左子樹中的所有關鍵字都小於它，而右子樹中的所有關鍵字都大於它。
- 所有葉子節點都位於同一層，或者說根節點到每個葉子節點的長度都相同。
- 每個節點都存有索引和數據，也就是對應的key和value。
4、B+樹
B+樹是B樹的變體，也是一種多路搜索樹。
B+樹·和B樹有一些共同的特性：
- 根節點至少一個元素
- 非根節點元素範圍：m/2 <= k <= m-1
B+樹和B樹也有一些不一樣的地方：
- B+樹有兩種類型的節點：非葉子結點（也稱索引結點）和葉子結點。非葉子節點不存儲數據，只存儲索引，數據都存儲在葉子節點。
- 非葉子結點中的key都按照從小到大的順序排列，對於非葉子結點中的一個key，左樹中的所有key都小於它，右子樹中的key都大於等於它。葉子結點中的記錄也按照key的大小排列。
- 每個葉子結點都存有相鄰葉子結點的指針，葉子結點本身依關鍵字的大小自小而大順序鏈接。
- 父節點存有右孩子的第一個元素的索引。
四、散列表的查找
1、散列表的概念
在前面學習了關於線性表、樹表的查找，這類查找方法都是以關鍵字的比較為基礎的。
在查找過程中只考慮各元素關鍵字之間的相對大小，記錄在存儲結構中的位置和其關鍵字無直接關係， 其查找時間與表的長度有關，特別是當結點個數很多時，查找時要大量地與無效結點的關鍵字進行比較，致使查找速度很慢。
如果能在元素的存儲位置和其關鍵字之間建立某種直接關係，那麼在進行查找時，就無需做比較或做很少次的比較，按照這種關係直接由關鍵字找到相應的記錄。這就是散列查找法 （HashSearch)的思想，它通過對元素的關鍵字值進行某種運算，直接求出元素的地址， 即使用關鍵字到地址的直接轉換方法，而不需要反覆比較。因此，散列查找法又叫雜湊法或散列法。
下面來看一些散列查找法的術語：
- 散列函數和散列地址：在記錄的存儲位置p和其關鍵字key 之間建立一個確定的對應關係H, 使 p=H(key), 稱這個對應關係H為散列函數，p為散列地址。
- 散列表：一個連續有限的地址空間，用來存儲散列函數計算的到的散列地址。通常散列表的存儲結構是一個一維數組，散列地址是數組的下標。
- 衝突和同義詞：對不同的關鍵字可能得到同一散列地址，即key不等於key2 ,而H(key1)=H(key2），這種現象稱為衝突。具有相同函數值的關鍵字對該散列函數來說稱作同義詞，key1與key2互稱為同義詞。
2、散列函數的構造方法
構造散列函數的方法很多，一般來說，應根據具體問題選用不同的散列函數，通常要考慮以下因素：
- (1)散列表的長度；
- (2) 關鍵字的長度；
- (3)關鍵字的分佈情況；
- (4)計算散列函數所需的時間；
- (5) 記錄的查找頻率。
構造一個 「好」 的散列函數應遵循以下兩條原則：
- (1)函數計算要簡單，每一關鍵字只能有一個散列地址與之對應；
- (2) 函數的值域需在表長的範圍內， 計算出的散列地址的分佈應均勻，儘可能減少衝突。
下面介紹構造散列函數的幾種常用方法。
2.1、數字分析法
如果事先知道關鍵字集合， 且每個關鍵字的位數比散列表的地址碼位數多，每個關鍵字由n位數組成，如K1…Kn , 則可以從關鍵字中提取數字分佈比較均勻的若干位作為散列地址。
例如，有80個記錄，其關鍵字為8位十進制數。假設散列表的表長為100, 則可取兩位十進制數組成散列地址，選取的原則是分析這80個關鍵字，使得到的散列地址盡最避免產生衝突。
假設這80個關鍵字中的一部分如下所列：
對關鍵字全體的分析中可以發現：第1、2位都是”8 、1″, 第3位只可能取3或4, 第4位可能取2、 5或 7,因此這 4 位都不可取。由千中間的 4 位可看成是近乎隨機的，因此可取其中任意兩位，或取其中兩位與另外兩位的疊加求和後捨去進位作為散列地址。
數字分析法的適用情況：事先必須明確知道所有的關鍵字每一位上各種數字的分佈情況。
在實際應用中，例如，同一出版社出版的所有圖書，其ISBN號的前幾位都是相同的，因此，若數據表只包含同一出版社的圖書，構造散列函數時可以利用這種數字分析排除ISBN號的前幾位數字。
2.2、平方取中法
通常在選定散列函數時不一定能知道關鍵字的全部情況，取其中哪幾位也不一定合適，而一個數平方後的中間幾位數和數的每一位都相關，如果取關鍵字平方後的中間幾位或其組合作為散列地址，則使隨機分佈的關鍵字得到的散列地址也是隨機的，具體所取的位數由表長決定。平方取中法是一種較常用的構造散列函數的方法。
平方取中法的適用情況：不能事先了解關鍵字的所有情況，或難千直接從關鍵字中找到取值較分散的幾位。
2.3、摺疊法
將關鍵字分割成位數相同的幾部分（最後一部分的位數可以不同），然後取這幾部分的疊加和（捨去進位） 作為散列地址，這種方法稱為摺疊法。根據數位疊加的方式，可以把摺疊法分為移位疊加和邊界疊加兩種。移位疊加是將分割後每一部分的最低位對齊，然後相加；邊界疊加是將兩相鄰的部分沿邊界來回摺疊，然後對齊相加。
例如，當散列表長為 1000 時，關鍵字key = 45387765213, 從左到右按 3 位數一段分割，可以得到 4 個部分：453 、 877 、 652 、 13。分別採用移位疊加和邊界疊加，求得散列地址為 995 和914, 如下圖 所示。
摺疊法的適用情況：適合於散列地址的位數較少，而關鍵字的位數較多，且難千直接從關鍵字中找到取值較分散的幾位。
2.4、除留餘數法
假設散列表表長為m, 選擇一個不大千m的數p, 用p去除關鍵字，除後所得餘數為散列地址，即
這個方法的關鍵是選取適當的p, 一般情況下，可以選p為小於表長的最大質數。例如，表長m= 100 , 可取p= 97 。
除留餘數法計算簡單，適用範圍非常廣，是最常用的構造散列函數的方法。它不僅可以對關鍵字直接取模，也可在摺疊、平方取中等運算之後取模，這樣能夠保證散列地址一定落在散列表的地址空間中。
2.5、隨機數法
選取一個隨機函數，取關鍵字的隨機函數的值為散列地址。
3、處理衝突的方法
選擇一個 「好」 的散列函數可以在一定程度上減少衝突，但在實際應用中，很難完全避免發生衝突，所以選擇一個有效的處理衝突的方法是散列法的另一個關鍵問題。創建散列表和查找散列表都會遇到衝突，兩種情況下處理衝突的方法應該一致。
處理衝突的方法與散列表本身的組織形式有關。按組織形式的不同，通常分兩大類：開放地址法和鏈地址法。
3.1、開放地址法
開放地址法的基本思想是：把記錄都存儲在散列表數組中，當某一記錄關鍵字 key的初始散列地址H0=H(key)發生衝突時，以H0為基礎 ，採取合適方法計算得到另一個地址H1, 如果H1仍然發生衝突，以H1為基礎再求下一個地址H2，若H2仍然衝突，再求得H3。依次類推，直至Hk不發生衝突為止，則Hk為該記錄在表中的散列地址。
這種方法在尋找 「下一個 「 空的散列地址時，原來的數組空間對所有的元素都是開放的，所以稱為開放地址法。通常把尋找 「下一個 「 空位的過程稱為探測，上述方法可用如下公式表示：
3.1.1、線性探測法
這種探測方法可以將散列表假想成一個循環表，發生衝突時，從衝突地址的下一單元順序尋找空單元，如果到最後 一個位置也沒找到空單元，則回到表頭開始繼續查找，直到找到一個空位，就把此元素放入此空位中。如果找不到空位，則說明散列表已滿，需要進行溢出處理。
3.1.2、二次探測法
3.1.3、偽隨機探測法
例如，散列表的長度為 11, 散列函數 H(key) = key%11, 假設表中已填有關鍵字分別為 17 、60 、 29 的記錄，如圖 11 (a) 所示。現有第四個記錄，其關鍵字為 38, 由散列函數得到散列地址為 5, 產生衝突。
-
若用線性探測法處理時，得到下一個地址 6, 仍衝突；再求下一個地址 7, 仍衝突；直到散列地址為 8 的位置為 「空」 時為止，處理衝突的過程結束，38 填入散列表中序號為 8 的位置，如圖11 (b) 所示。
-
若用二次探測法，散列地址 5 衝突後，得到下一個地址 6, 仍衝突；再求得下一個地址 4 , 無衝突， 38 填入序號為 4 的位置，如圖 11 (C), 所示。
-
若用偽隨機探測法，假設產生的偽隨機數為 9, 則計算下一個散列地址為(5+9)%11 = 3, 所以38 填入序號為 3 的位置，如圖 11 (d) 所示。
從上述線性探測法處理的過程中可以看到一個現象：當表中 i, i+1, i+2 位置上已填有記錄時，下一個散列地址為i、i+ I 、i+2和i+3 的記錄都將填入i+3 的位置，這種在處理衝突過程中發生的兩個第一個散列地址不同的記錄爭奪同一個後繼散列地址的現象稱作 「二次聚集＂（或稱作 「堆積＂），即在處理同義詞的衝突過程中又添加了非同義詞的衝突。
可以看出，上述三種處理方法各有優缺點。
-
線性探測法的優點是：只要散列表未填滿，總能找到一個不發生衝突的地址。缺點是：會產生 」二次聚集「 現象。
-
而二次探測法和偽隨機探測法的優點是：可以避免 「二次聚集「 現象。缺點也很顯然：不能保證一定找到不發生衝突的地址。
3.2、鏈地址法
鏈地址法的基本思想是：把具有相同散列地址的記錄放在同一個單鏈表中，稱為同義詞鏈表。有 m 個散列地址就有 m 個單鏈表，同時用數組 HT[0…m-1]存放各個鏈表的頭指針，凡是散列地址為 i 的記錄都以結點方式插入到以 HT[i]為頭結點的單鏈表中。
該方法的基本思想就是選擇足夠大的M，使得所有的鏈表都儘可能的短小，以保證查找的效率。對採用鏈地址法的哈希實現的查找分為兩步，首先是根據散列值找到等一應的鏈表，然後沿着鏈表順序找到相應的鍵。
4、散列表的算法
散列表上的運算有查找、插入和刪除。其中主要是查找，這是因為散列表主要用於快速查找，且插入和刪除均要用到査找操作。
接下來建立一個簡單的散列表，其散列函數採用上述的除留餘數法，處理衝突的方法採用開放定址法下的線性探測法。
public class HashTable {
int[] elem;
int count;
private static final int Nullkey = -32768;
public HashTable(int count) {
this.count = count;
elem = new int[count];
for (int i = 0; i < count; i++) {
elem[i] = Nullkey; // 代表位置為空
}
}
/*
* 散列函數
*/
public int hash(int key) {
return key % count; // 除留餘數法
}
/*
* 插入操作
*/
public void insert(int key) {
int addr = hash(key); // 求散列地址
while (elem[addr] != Nullkey) { // 位置非空，有衝突
addr = (addr + 1) % count; // 開放地址法的線性探測
}
elem[addr] = key;
}
/*
* 查找操作
*/
public boolean search(int key) {
int addr = hash(key); // 求散列地址
while (elem[addr] != key) {
addr = (addr + 1) % count; // 開放地址法的線性探測
if (addr == hash(key) || elem[addr] == Nullkey) { // 循環回到原點或者到了空地址
System.out.println("要查找的記錄不存在！");
return false;
}
}
System.out.println("存在記錄:" + key + ",位置為：" + addr);
return true;
}
public static void main(String[] args) {
int[] arr = {12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34};
HashTable aTable = new HashTable(arr.length);
for (int a : arr) {
aTable.insert(a);
}
for (int a : arr) {
aTable.search(a);
}
}
}
- (1) 雖然散列表在關鍵字與記錄的存儲位置之間建立了直接映像，但由千 ＂衝突＂ 的產生，使得散列表的查找過程仍然是一個給定值和關鍵字進行比較的過程。因此，仍需以平均查找長度作為衡量散列表查找效率的量度。
- (2) 查找過程中需和給定值進行比較的關鍵字的個數取決千三個因素：散列函數、處理衝突的方法和散列表的裝填因子。
散列表的裝填因子α定義為:
α標誌散列表的裝滿程度。直觀地看，α越小，發生衝突的可能性就越小；反之，α越大，表中已填入的記錄越多，再填記錄時，發生衝突的可能性就越大，則查找時，給定值需與之進行比較的關鍵字的個數也就越多。
- (3) 散列函數的 「好壞「 首先影響出現衝突的頻繁程度。但一般情況下認為：凡是 ＂均勻的＂散列函數，對同一組隨機的關鍵字，產生衝突的可能性相同，假如所設定的散列函數是 ＂均勻”的，則影響平均查找長度的因素只有兩個—一處理衝突的方法和裝填因子 α。
五、總結
查找是數據處理中經常使用的一種操作。 這裡主要介紹了對查找表的查找 ， 查找表實際上僅僅是一個集合，為了提高查找效率，將查找表組織成不同的數據結構，主要包括3種不同結構的查找表：線性表、 樹表和散列表。
- (1)線性表的查找
主要包括順序查找、折半查找和分塊查找。
- (2)樹表的查找
樹表的結構主要包括二叉排序樹、 平衡二叉樹、 B-樹和B+樹
* 二叉排序樹的查找過程與折半查找過程類似
* 二叉排序樹在形態均勻時性能最好，而形態為單支樹時其查找性能則退化為與順序查找相同，因此，二叉排序樹最好是一棵平衡二叉樹。 平衡二叉樹的平衡調整方法就是確保二叉排序樹在任何情況下的深度均為 O(log2n），平衡調整方法分為4種： LL型、RR型、LR型和RL型。
* B-樹是一種平衡的多叉查找樹，是一種在外存文件系統中常用的動態索引技術。 在 B-樹上進行查找的過程和二叉排序樹類似，是一個順指針查找結點和在結點內的關鍵字中查找交叉進行的過程。 為了確保B-樹的定義，在B-樹中插入一個關鍵字，可能產生結點的 「分裂＂， 而刪除一個關鍵字，可能產生結點的 「合併＂。
* B+樹是一種B-樹的變型樹，更適合做文件系統的索引。 在B+樹上進行隨機查找、 插入和刪除的過程基本上與B-樹類似，但具體實現細節又有所區別。
- (3)散列表的查找
散列表也屬線性結構，但它和線性表的查找有着本質的區別。 它不是以關鍵字比較為基礎進行查找的，而是通過一種散列函數把記錄的關鍵字和它在表中的位置建立起對應關係，並在存儲記錄發生衝突時採用專門的處理衝突的方法。這種方式構造的散列表，不僅平均查找長度和記錄總數無關，而且可以通過調節裝填因子，把平均查找長度控制在所需的範圍內。
散列查找法主要研究兩方面的問題：如何構造散列函數，以及如何處理衝突。
* 構造散列函數的方法很多，除留餘數法是最常用的構造散列函數的方法。它不僅可以對關鍵字直接取模， 也可在摺疊、平方取中等運算之後取模。
* 處理衝突的方法通常分為兩大類：開放地址法和鏈地址法，二者之間的差別類似千順序表和單鏈表的差別。
上一篇：重學數據結構（七、圖）
本博客為學習筆記，參考資料如下！
水平有限，難免錯漏，歡迎指正！
參考：
【1】：鄧俊輝 編著. 《數據結構與算法》
【2】：王世民 等編著 . 《數據結構與算法分析》
【3】： Michael T. Goodrich 等編著.《Data-Structures-and-Algorithms-in-Java-6th-Edition》
【4】：嚴蔚敏、吳偉民 編著 . 《數據結構》
【5】：程傑 編著 . 《大話數據結構》
【6】：圖解：如何理解與實現散列表
【7】：算法圖解之散列表
【8】：數據結構與算法-Day17-哈希(散列)表
【9】：Java數據結構與算法解析(十二)——散列表
【10】：【Java】 大話數據結構(13) 查找算法(4) （散列表（哈希表））
