七大查找算法

1、七大查找算法 查找是在大量的信息中尋找一個特定的信息元素，在計算機應(yīng)用中，查找是常用的基本運算，例如編譯程序中符號表的查找。本文簡單概括性的介紹了常見的七種查找算法，說是七種，其實二分查找、插值查找以及斐波那契查找都可以歸為一類插值查找。插值查找和斐波那契查找是在二分查找的基礎(chǔ)上的優(yōu)化查找算法。樹表查找和哈希查找會在后續(xù)的博文中進行詳細介紹。查找定義：根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素（或記錄）。查找算法分類：1）靜態(tài)查找和動態(tài)查找；注：靜態(tài)或者動態(tài)都是針對查找表而言的。動態(tài)表指查找表中有刪除和插入操作的表。2）無序查找和有序查找。無序查找：被查找數(shù)列有序無序均可

2、；有序查找：被查找數(shù)列必須為有序數(shù)列。平均查找長度（Average Search Length，ASL）：需和指定key進行比較的關(guān)鍵字的個數(shù)的期望值，稱為查找算法在查找成功時的平均查找長度。對于含有n個數(shù)據(jù)元素的查找表，查找成功的平均查找長度為：ASL = Pi*Ci的和。Pi：查找表中第i個數(shù)據(jù)元素的概率。Ci：找到第i個數(shù)據(jù)元素時已經(jīng)比較過的次數(shù)。1. 順序查找說明：順序查找適合于存儲結(jié)構(gòu)為順序存儲或鏈接存儲的線性表?；舅枷耄喉樞虿檎乙卜Q為線形查找，屬于無序查找算法。從數(shù)據(jù)結(jié)構(gòu)線形表的一端開始，順序掃描，依次將掃描到的結(jié)點關(guān)鍵字與給定值k相比較，若相等則表示查找成功；若掃描結(jié)束仍沒有找

3、到關(guān)鍵字等于k的結(jié)點，表示查找失敗。復(fù)雜度分析：查找成功時的平均查找長度為：（假設(shè)每個數(shù)據(jù)元素的概率相等） ASL = 1/n(1+2+3+n) = (n+1)/2 ;當(dāng)查找不成功時，需要n+1次比較，時間復(fù)雜度為O(n);所以，順序查找的時間復(fù)雜度為O(n)。C+實現(xiàn)源碼：/順序查找int SequenceSearch(int a, int value, int n) int i; for(i=0; i<n; i+) if(ai=value) return i; return -1;2. 二分查找說明：元素必須是有序的，如果是無序的則要先進行排序操作?；舅枷耄阂卜Q為是折半查找，屬于有

4、序查找算法。用給定值k先與中間結(jié)點的關(guān)鍵字比較，中間結(jié)點把線形表分成兩個子表，若相等則查找成功；若不相等，再根據(jù)k與該中間結(jié)點關(guān)鍵字的比較結(jié)果確定下一步查找哪個子表，這樣遞歸進行，直到查找到或查找結(jié)束發(fā)現(xiàn)表中沒有這樣的結(jié)點。復(fù)雜度分析：最壞情況下，關(guān)鍵詞比較次數(shù)為log2(n+1)，且期望時間復(fù)雜度為O(log2n)；注：折半查找的前提條件是需要有序表順序存儲，對于靜態(tài)查找表，一次排序后不再變化，折半查找能得到不錯的效率。但對于需要頻繁執(zhí)行插入或刪除操作的數(shù)據(jù)集來說，維護有序的排序會帶來不小的工作量，那就不建議使用。大話數(shù)據(jù)結(jié)構(gòu)C+實現(xiàn)源碼：/二分查找（折半查找），版本1int BinaryS

5、earch1(int a, int value, int n) int low, high, mid; low = 0; high = n-1; while(low<=high) mid = (low+high)/2; if(amid=value) return mid; if(amid>value) high = mid-1; if(amid<value) low = mid+1; return -1;/二分查找，遞歸版本int BinarySearch2(int a, int value, int low, int high) int mid = low+(high-lo

6、w)/2; if(amid=value) return mid; if(amid>value) return BinarySearch2(a, value, low, mid-1); if(amid<value) return BinarySearch2(a, value, mid+1, high);3. 插值查找在介紹插值查找之前，首先考慮一個新問題，為什么上述算法一定要是折半，而不是折四分之一或者折更多呢？打個比方，在英文字典里面查“apple”，你下意識翻開字典是翻前面的書頁還是后面的書頁呢？如果再讓你查“zoo”，你又怎么查？很顯然，這里你絕對不會是從中間開始查起，而是有一

7、定目的的往前或往后翻。同樣的，比如要在取值范圍1 10000 之間 100 個元素從小到大均勻分布的數(shù)組中查找5， 我們自然會考慮從數(shù)組下標(biāo)較小的開始查找。經(jīng)過以上分析，折半查找這種查找方式，不是自適應(yīng)的（也就是說是傻瓜式的）。二分查找中查找點計算如下：mid=(low+high)/2, 即mid=low+1/2*(high-low);通過類比，我們可以將查找的點改進為如下：mid=low+(key-alow)/(ahigh-alow)*(high-low)，也就是將上述的比例參數(shù)1/2改進為自適應(yīng)的，根據(jù)關(guān)鍵字在整個有序表中所處的位置，讓mid值的變化更靠近關(guān)鍵字key，這樣也就間接地減少了

8、比較次數(shù)。基本思想：基于二分查找算法，將查找點的選擇改進為自適應(yīng)選擇，可以提高查找效率。當(dāng)然，差值查找也屬于有序查找。注：對于表長較大，而關(guān)鍵字分布又比較均勻的查找表來說，插值查找算法的平均性能比折半查找要好的多。反之，數(shù)組中如果分布非常不均勻，那么插值查找未必是很合適的選擇。復(fù)雜度分析：查找成功或者失敗的時間復(fù)雜度均為O(log2(log2n)。C+實現(xiàn)源碼：/插值查找int InsertionSearch(int a, int value, int low, int high) int mid = low+(value-alow)/(ahigh-alow)*(high-low); if(a

9、mid=value) return mid; if(amid>value) return InsertionSearch(a, value, low, mid-1); if(amid<value) return InsertionSearch(a, value, mid+1, high);4. 斐波那契查找在介紹斐波那契查找算法之前，我們先介紹一下很它緊密相連并且大家都熟知的一個概念黃金分割。黃金比例又稱黃金分割，是指事物各部分間一定的數(shù)學(xué)比例關(guān)系，即將整體一分為二，較大部分與較小部分之比等于整體與較大部分之比，其比值約為1:0.618或1.618:1。0.618被公認(rèn)為最具有審美

10、意義的比例數(shù)字，這個數(shù)值的作用不僅僅體現(xiàn)在諸如繪畫、雕塑、音樂、建筑等藝術(shù)領(lǐng)域，而且在管理、工程設(shè)計等方面也有著不可忽視的作用。因此被稱為黃金分割。大家記不記得斐波那契數(shù)列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89.（從第三個數(shù)開始，后邊每一個數(shù)都是前兩個數(shù)的和）。然后我們會發(fā)現(xiàn)，隨著斐波那契數(shù)列的遞增，前后兩個數(shù)的比值會越來越接近0.618，利用這個特性，我們就可以將黃金比例運用到查找技術(shù)中?；舅枷耄阂彩嵌植檎业囊环N提升算法，通過運用黃金比例的概念在數(shù)列中選擇查找點進行查找，提高查找效率。同樣地，斐波那契查找也屬于一種有序查找算法。相對于折半查找，一般將待

11、比較的key值與第mid=（low+high）/2位置的元素比較，比較結(jié)果分三種情況：1）相等，mid位置的元素即為所求2）>，low=mid+1;     3）<，high=mid-1。斐波那契查找與折半查找很相似，他是根據(jù)斐波那契序列的特點對有序表進行分割的。他要求開始表中記錄的個數(shù)為某個斐波那契數(shù)小1，及n=F(k)-1; 開始將k值與第F(k-1)位置的記錄進行比較(及mid=low+F(k-1)-1),比較結(jié)果也分為三種1）相等，mid位置的元素即為所求2）>，low=mid+1,k-=2;說明：low=mid+1說明待查找的

12、元素在mid+1,high范圍內(nèi)，k-=2 說明范圍mid+1,high內(nèi)的元素個數(shù)為n-(F(k-1)= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1個，所以可以遞歸的應(yīng)用斐波那契查找。3）<，high=mid-1,k-=1。說明：low=mid+1說明待查找的元素在low,mid-1范圍內(nèi)，k-=1 說明范圍low,mid-1內(nèi)的元素個數(shù)為F(k-1)-1個，所以可以遞歸 的應(yīng)用斐波那契查找。復(fù)雜度分析：最壞情況下，時間復(fù)雜度為O(log2n)，且其期望復(fù)雜度也為O(log2n)。C+實現(xiàn)源碼：/ 斐波那契查找.cpp #include "st

13、dafx.h"#include <memory>#include <iostream>using namespace std;const int max_size=20;/斐波那契數(shù)組的長度/*構(gòu)造一個斐波那契數(shù)組*/ void Fibonacci(int * F) F0=0; F1=1; for(int i=2;i<max_size;+i) Fi=Fi-1+Fi-2;/*定義斐波那契查找法*/ int FibonacciSearch(int *a, int n, int key) /a為要查找的數(shù)組,n為要查找的數(shù)組長度,key為要查找的關(guān)鍵字 int

14、 low=0; int high=n-1; int Fmax_size; Fibonacci(F);/構(gòu)造一個斐波那契數(shù)組F int k=0; while(n>Fk-1)/計算n位于斐波那契數(shù)列的位置 +k; int * temp;/將數(shù)組a擴展到Fk-1的長度 temp=new int Fk-1; memcpy(temp,a,n*sizeof(int); for(int i=n;i<Fk-1;+i) tempi=an-1; while(low<=high) int mid=low+Fk-1-1; if(key<tempmid) high=mid-1; k-=1; el

15、se if(key>tempmid) low=mid+1; k-=2; else if(mid<n) return mid; /若相等則說明mid即為查找到的位置 else return n-1; /若mid>=n則說明是擴展的數(shù)值,返回n-1 delete temp; return -1;int main() int a = 0,16,24,35,47,59,62,73,88,99; int key=100; int index=FibonacciSearch(a,sizeof(a)/sizeof(int),key); cout<<key<<&quo

16、t; is located at:"<<index; return 0;5. 樹表查找5.1 最簡單的樹表查找算法二叉樹查找算法?；舅枷耄憾娌檎覙涫窍葘Υ檎业臄?shù)據(jù)進行生成樹，確保樹的左分支的值小于右分支的值，然后在就行和每個節(jié)點的父節(jié)點比較大小，查找最適合的范圍。 這個算法的查找效率很高，但是如果使用這種查找方法要首先創(chuàng)建樹。 二叉查找樹（BinarySearch Tree，也叫二叉搜索樹，或稱二叉排序樹Binary Sort Tree）或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：1）若任意節(jié)點的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點

17、的值；2）若任意節(jié)點的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；3）任意節(jié)點的左、右子樹也分別為二叉查找樹。二叉查找樹性質(zhì)：對二叉查找樹進行中序遍歷，即可得到有序的數(shù)列。不同形態(tài)的二叉查找樹如下圖所示： 有關(guān)二叉查找樹的查找、插入、刪除等操作的詳細講解，請移步復(fù)雜度分析：它和二分查找一樣，插入和查找的時間復(fù)雜度均為O(logn)，但是在最壞的情況下仍然會有O(n)的時間復(fù)雜度。原因在于插入和刪除元素的時候，樹沒有保持平衡（比如，我們查找上圖（b）中的“93”，我們需要進行n次查找操作）。我們追求的是在最壞的情況下仍然有較好的時間復(fù)雜度，這就是平衡查找樹設(shè)計的初衷。下圖為

18、二叉樹查找和順序查找以及二分查找性能的對比圖： 基于二叉查找樹進行優(yōu)化，進而可以得到其他的樹表查找算法，如平衡樹、紅黑樹等高效算法。5.2 平衡查找樹之2-3查找樹（2-3 Tree）2-3查找樹定義：和二叉樹不一樣，2-3樹運行每個節(jié)點保存1個或者兩個的值。對于普通的2節(jié)點(2-node)，他保存1個key和左右兩個自己點。對應(yīng)3節(jié)點(3-node)，保存兩個Key，2-3查找樹的定義如下：1）要么為空，要么：2）對于2節(jié)點，該節(jié)點保存一個key及對應(yīng)value，以及兩個指向左右節(jié)點的節(jié)點，左節(jié)點也是一個2-3節(jié)點，所有的值都比key要小，右節(jié)點也是一個2-3節(jié)點，所有的值比key

19、要大。3）對于3節(jié)點，該節(jié)點保存兩個key及對應(yīng)value，以及三個指向左中右的節(jié)點。左節(jié)點也是一個2-3節(jié)點，所有的值均比兩個key中的最小的key還要??；中間節(jié)點也是一個2-3節(jié)點，中間節(jié)點的key值在兩個跟節(jié)點key值之間；右節(jié)點也是一個2-3節(jié)點，節(jié)點的所有key值比兩個key中的最大的key還要大。2-3查找樹的性質(zhì)：1）如果中序遍歷2-3查找樹，就可以得到排好序的序列；2）在一個完全平衡的2-3查找樹中，根節(jié)點到每一個為空節(jié)點的距離都相同。（這也是平衡樹中“平衡”一詞的概念，根節(jié)點到葉節(jié)點的最長距離對應(yīng)于查找算法的最壞情況，而平衡樹中根節(jié)點到葉節(jié)點的距離都一樣，最壞情況也具有對數(shù)復(fù)

20、雜度。）性質(zhì)2）如下圖所示： 復(fù)雜度分析：2-3樹的查找效率與樹的高度是息息相關(guān)的。· 在最壞的情況下，也就是所有的節(jié)點都是2-node節(jié)點，查找效率為lgN· 在最好的情況下，所有的節(jié)點都是3-node節(jié)點，查找效率為log3N約等于0.631lgN距離來說，對于1百萬個節(jié)點的2-3樹，樹的高度為12-20之間，對于10億個節(jié)點的2-3樹，樹的高度為18-30之間。對于插入來說，只需要常數(shù)次操作即可完成，因為他只需要修改與該節(jié)點關(guān)聯(lián)的節(jié)點即可，不需要檢查其他節(jié)點，所以效率和查找類似。下面是2-3查找樹的效率： 5.3 平衡查找樹之紅黑樹（Red-Bla

21、ck Tree）2-3查找樹能保證在插入元素之后能保持樹的平衡狀態(tài)，最壞情況下即所有的子節(jié)點都是2-node，樹的高度為lgn，從而保證了最壞情況下的時間復(fù)雜度。但是2-3樹實現(xiàn)起來比較復(fù)雜，于是就有了一種簡單實現(xiàn)2-3樹的數(shù)據(jù)結(jié)構(gòu)，即紅黑樹（Red-Black Tree）?；舅枷耄杭t黑樹的思想就是對2-3查找樹進行編碼，尤其是對2-3查找樹中的3-nodes節(jié)點添加額外的信息。紅黑樹中將節(jié)點之間的鏈接分為兩種不同類型，紅色鏈接，他用來鏈接兩個2-nodes節(jié)點來表示一個3-nodes節(jié)點。黑色鏈接用來鏈接普通的2-3節(jié)點。特別的，使用紅色鏈接的兩個2-nodes來表示一個3-nodes節(jié)點

22、，并且向左傾斜，即一個2-node是另一個2-node的左子節(jié)點。這種做法的好處是查找的時候不用做任何修改，和普通的二叉查找樹相同。紅黑樹的定義：紅黑樹是一種具有紅色和黑色鏈接的平衡查找樹，同時滿足：· 紅色節(jié)點向左傾斜· 一個節(jié)點不可能有兩個紅色鏈接· 整個樹完全黑色平衡，即從根節(jié)點到所以葉子結(jié)點的路徑上，黑色鏈接的個數(shù)都相同。下圖可以看到紅黑樹其實是2-3樹的另外一種表現(xiàn)形式：如果我們將紅色的連線水平繪制，那么他鏈接的兩個2-node節(jié)點就是2-3樹中的一個3-node節(jié)點了。紅黑樹的性質(zhì)：整個樹完全黑色平衡，即從根節(jié)點到所以葉子結(jié)點的路徑上，黑色鏈接的個數(shù)都

23、相同（2-3樹的第2）性質(zhì)，從根節(jié)點到葉子節(jié)點的距離都相等）。復(fù)雜度分析：最壞的情況就是，紅黑樹中除了最左側(cè)路徑全部是由3-node節(jié)點組成，即紅黑相間的路徑長度是全黑路徑長度的2倍。下圖是一個典型的紅黑樹，從中可以看到最長的路徑(紅黑相間的路徑)是最短路徑的2倍：紅黑樹的平均高度大約為logn。下圖是紅黑樹在各種情況下的時間復(fù)雜度，可以看出紅黑樹是2-3查找樹的一種實現(xiàn)，它能保證最壞情況下仍然具有對數(shù)的時間復(fù)雜度。紅黑樹這種數(shù)據(jù)結(jié)構(gòu)應(yīng)用十分廣泛，在多種編程語言中被用作符號表的實現(xiàn)，如：· Java中的java.util.TreeMap,java.util.TreeSet；·

24、; C+ STL中的：map,multimap,multiset；· .NET中的：SortedDictionary,SortedSet 等。5.4 B樹和B+樹（B Tree/B+ Tree）平衡查找樹中的2-3樹以及其實現(xiàn)紅黑樹。2-3樹種，一個節(jié)點最多有2個key，而紅黑樹則使用染色的方式來標(biāo)識這兩個key。維基百科對B樹的定義為“在計算機科學(xué)中，B樹（B-tree）是一種樹狀數(shù)據(jù)結(jié)構(gòu)，它能夠存儲數(shù)據(jù)、對其進行排序并允許以O(shè)(log n)的時間復(fù)雜度運行進行查找、順序讀取、插入和刪除的數(shù)據(jù)結(jié)構(gòu)。B樹，概括來說是一個節(jié)點可以擁有多于2個子節(jié)點的二叉查找樹。與自平衡二叉查

25、找樹不同，B樹為系統(tǒng)最優(yōu)化大塊數(shù)據(jù)的讀和寫操作。B-tree算法減少定位記錄時所經(jīng)歷的中間過程，從而加快存取速度。普遍運用在數(shù)據(jù)庫和文件系統(tǒng)。B樹定義：B樹可以看作是對2-3查找樹的一種擴展，即他允許每個節(jié)點有M-1個子節(jié)點。· 根節(jié)點至少有兩個子節(jié)點· 每個節(jié)點有M-1個key，并且以升序排列· 位于M-1和M key的子節(jié)點的值位于M-1 和M key對應(yīng)的Value之間· 其它節(jié)點至少有M/2個子節(jié)點下圖是一個M=4 階的B樹:可以看到B樹是2-3樹的一種擴展，他允許一個節(jié)點有多于2個的元素。B樹的插入及平衡化操作和2-3樹很相似，這里就不介紹了。

26、下面是往B樹中依次插入6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4B+樹定義：B+樹是對B樹的一種變形樹，它與B樹的差異在于：· 有k個子結(jié)點的結(jié)點必然有k個關(guān)鍵碼；· 非葉結(jié)點僅具有索引作用，跟記錄有關(guān)的信息均存放在葉結(jié)點中。· 樹的所有葉結(jié)點構(gòu)成一個有序鏈表，可以按照關(guān)鍵碼排序的次序遍歷全部記錄。如下圖，是一個B+樹: 下圖是B+樹的插入動畫： B和B+樹的區(qū)別在于，B+樹的非葉子結(jié)點只包含導(dǎo)航信息，不包含實際的值，所有的葉子結(jié)點和相連的節(jié)

27、點使用鏈表相連，便于區(qū)間查找和遍歷。B+ 樹的優(yōu)點在于：· 由于B+樹在內(nèi)部節(jié)點上不好含數(shù)據(jù)信息，因此在內(nèi)存頁中能夠存放更多的key。 數(shù)據(jù)存放的更加緊密，具有更好的空間局部性。因此訪問葉子幾點上關(guān)聯(lián)的數(shù)據(jù)也具有更好的緩存命中率。· B+樹的葉子結(jié)點都是相鏈的，因此對整棵樹的便利只需要一次線性遍歷葉子結(jié)點即可。而且由于數(shù)據(jù)順序排列并且相連，所以便于區(qū)間查找和搜索。而B樹則需要進行每一層的遞歸遍歷。相鄰的元素可能在內(nèi)存中不相鄰，所以緩存命中性沒有B+樹好。但是B樹也有優(yōu)點，其優(yōu)點在于，由于B樹的每一個節(jié)點都包含key和value，因此經(jīng)常訪問的元素可能離根節(jié)點更近，因此訪問也

28、更迅速。下面是B 樹和B+樹的區(qū)別圖：B/B+樹常用于文件系統(tǒng)和數(shù)據(jù)庫系統(tǒng)中，它通過對每個節(jié)點存儲個數(shù)的擴展，使得對連續(xù)的數(shù)據(jù)能夠進行較快的定位和訪問，能夠有效減少查找時間，提高存儲的空間局部性從而減少IO操作。它廣泛用于文件系統(tǒng)及數(shù)據(jù)庫中，如：· Windows：HPFS文件系統(tǒng)；· Mac：HFS，HFS+文件系統(tǒng)；· Linux：ResiserFS，XFS，Ext3FS，JFS文件系統(tǒng)；· 數(shù)據(jù)庫：ORACLE，MYSQL，SQLSERVER等中。有關(guān)B/B+樹在數(shù)據(jù)庫索引中的應(yīng)用，請看張洋的MySQL索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理這篇文章，這篇文章

29、對MySQL中的如何使用B+樹進行索引有比較詳細的介紹，推薦閱讀。樹表查找總結(jié)：二叉查找樹平均查找性能不錯，為O(logn)，但是最壞情況會退化為O(n)。在二叉查找樹的基礎(chǔ)上進行優(yōu)化，我們可以使用平衡查找樹。平衡查找樹中的2-3查找樹，這種數(shù)據(jù)結(jié)構(gòu)在插入之后能夠進行自平衡操作，從而保證了樹的高度在一定的范圍內(nèi)進而能夠保證最壞情況下的時間復(fù)雜度。但是2-3查找樹實現(xiàn)起來比較困難，紅黑樹是2-3樹的一種簡單高效的實現(xiàn)，他巧妙地使用顏色標(biāo)記來替代2-3樹中比較難處理的3-node節(jié)點問題。紅黑樹是一種比較高效的平衡查找樹，應(yīng)用非常廣泛，很多編程語言的內(nèi)部實現(xiàn)都或多或少的采用了紅黑樹。除此之外，2-

30、3查找樹的另一個擴展B/B+平衡樹，在文件系統(tǒng)和數(shù)據(jù)庫系統(tǒng)中有著廣泛的應(yīng)用。6. 分塊查找分塊查找又稱索引順序查找，它是順序查找的一種改進方法。算法思想：將n個數(shù)據(jù)元素"按塊有序"劃分為m塊（m n）。每一塊中的結(jié)點不必有序，但塊與塊之間必須"按塊有序"；即第1塊中任一元素的關(guān)鍵字都必須小于第2塊中任一元素的關(guān)鍵字；而第2塊中任一元素又都必須小于第3塊中的任一元素，算法流程：step1 先選取各塊中的最大關(guān)鍵字構(gòu)成一個索引表；step2 查找分兩個部分：先對索引表進行二分查找或順序查找，以確定待查記錄在哪一塊中；然后，在已確定的塊中用順序法進行查找。7. 哈希查找什么是哈希表（Hash）？我們使用一個下標(biāo)范圍比較大的數(shù)組來存儲元素?？梢栽O(shè)計一個函數(shù)（哈希函數(shù)， 也叫做散列函數(shù)），使得每個元素的關(guān)鍵字都與一個函數(shù)值（即數(shù)組下標(biāo)）相對應(yīng)，于是用這個數(shù)組單元來存儲這個元素；也可以簡單的理解為，按照關(guān)鍵字為每一個元素"分類"，然后將這個元素存儲在相應(yīng)"類"所對應(yīng)的地方。但是，不能夠保證每個元素的關(guān)鍵字與函數(shù)值是一一對應(yīng)的，因此極有可能出現(xiàn)對于不同的元素，卻計算出了相同的函數(shù)值，這樣就產(chǎn)生了"沖突"，換句話說，就是把不同的元素分在了相同的"類"之中。后面我們