算法概念
查找是在大量的信息中尋找一個(gè)特定的信息元素，在計(jì)算機(jī)應(yīng)用中晨缴，查找是常用的基本運(yùn)算译秦，例如編譯程序中符號(hào)表的查找。本文簡(jiǎn)單概括性的介紹了常見(jiàn)的七種查找算法，說(shuō)是七種筑悴，其實(shí)二分查找们拙、插值查找以及斐波那契查找都可以歸為一類——插值查找。插值查找和斐波那契查找是在二分查找的基礎(chǔ)上的優(yōu)化查找算法
查找算法分類：
靜態(tài)查找和動(dòng)態(tài)查找阁吝；
注：靜態(tài)或者動(dòng)態(tài)都是針對(duì)查找表而言的砚婆。動(dòng)態(tài)表指查找表中有刪除和插入操作的表。無(wú)序查找和有序查找突勇。
無(wú)序查找：被查找數(shù)列有序無(wú)序均可装盯；
有序查找：被查找數(shù)列必須為有序數(shù)列。平均查找長(zhǎng)度（Average Search Length甲馋，ASL）：需和指定key進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)的期望值埂奈，稱為查找算法在查找成功時(shí)的平均查找長(zhǎng)度
對(duì)于含有n個(gè)數(shù)據(jù)元素的查找表，查找成功的平均查找長(zhǎng)度為：ASL = Pi*Ci的和定躏。
Pi：查找表中第i個(gè)數(shù)據(jù)元素的概率账磺。
Ci：找到第i個(gè)數(shù)據(jù)元素時(shí)已經(jīng)比較過(guò)的次數(shù)。
排序方法 條件 時(shí)間復(fù)雜度(平均) 時(shí)間復(fù)雜度(最壞) 時(shí)間復(fù)雜度(最好) 順序查找 無(wú)序 分塊查找 分塊順序 二分查找 有序 插值查找 有序 斐波那契查找 有序 二叉樹(shù)查找 有序 哈希表法(散列表) 無(wú)序
七種算法
一共屈、順序查找
線性搜索或順序搜索是一種尋找某一特定值的搜索算法绑谣，指按一定的順序檢查數(shù)組中每一個(gè)元素，直到找到所要尋找的特定值為止拗引。是最簡(jiǎn)單的一種搜索算法借宵。順序查找也稱為線形查找，屬于無(wú)序查找算法矾削。
算法描述
從數(shù)據(jù)結(jié)構(gòu)線形表的一端開(kāi)始壤玫，順序掃描，依次將掃描到的結(jié)點(diǎn)關(guān)鍵字與給定值k相比較哼凯，若相等則表示查找成功欲间；
若掃描結(jié)束仍沒(méi)有找到關(guān)鍵字等于k的結(jié)點(diǎn)，表示查找失敗断部。
代碼實(shí)現(xiàn)
/// 順序查找 /// @param array 查找數(shù)組 /// @param word 要查找關(guān)鍵字 - (NSInteger)sequentialSearch:(NSArray *)array searchWord:(id)word { for (int i = 0; i < array.count; i ++) { if ([array[i] isEqual:word]) { return I; break; } } return -1; } //調(diào)用 NSMutableArray * array = [NSMutableArray arrayWithObjects:@"15",@"6",@"106",@"236",@"2",@"34",@"13",@"58",@"37",@"121",@"33", nil]; NSLog(@"順序查找：%ld", [self sequentialSearch:array searchWord:@"58"]);
算法分析
假設(shè)一個(gè)數(shù)組中有n個(gè)元素猎贴，最好的情況就是要尋找的特定值就是數(shù)組里的第一個(gè)元素，這樣僅需要1次比較就可以蝴光。而最壞的情況是要尋找的特定值不在這個(gè)數(shù)組或者是數(shù)組里的最后一個(gè)元素她渴，這就需要進(jìn)行n次比較。
查找成功時(shí)的平均查找長(zhǎng)度為：（假設(shè)每個(gè)數(shù)據(jù)元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2
時(shí)間復(fù)雜度為O(n)蔑祟，最好的情況是第一個(gè)就查找到了趁耗，為O(1)，最壞是沒(méi)有找到疆虚，為O(n)苛败。
二满葛、分塊查找
分塊查找又稱索引順序查找，它是順序查找的一種改進(jìn)方法罢屈。
將n個(gè)數(shù)據(jù)元素"按塊有序"劃分為m塊（m ≤ n）嘀韧。每一塊中的結(jié)點(diǎn)不必有序，但塊與塊之間必須"按塊有序"儡遮；即第1塊中任一元素的關(guān)鍵字都必須小于第2塊中任一元素的關(guān)鍵字乳蛾；而第2塊中任一元素又都必須小于第3塊中的任一元素，……
算法描述
- 先選取各塊中的最大關(guān)鍵字構(gòu)成一個(gè)索引表鄙币；
- 先對(duì)索引表進(jìn)行二分查找或順序查找肃叶，以確定待查記錄在哪一塊中；
- 然后十嘿，在已確定的塊中用順序法進(jìn)行查找因惭。
代碼實(shí)現(xiàn)
/// 分塊查找 /// @param array 查找數(shù)組 /// @param indexItemList 索引表 /// @param number 要查找數(shù)字 - (NSInteger)blockSearch:(NSArray *)array indexItemList:(NSArray<BlockItem*> *)indexItemList searchNumber:(id)number { BlockItem *indexItem = nil; //遍歷索引表 for(int i = 0;i < indexItemList.count; i++) { //找到索引項(xiàng) if(indexItemList[i].max >= number) { indexItem = indexItemList[I]; break; } } //索引表中不存在該索引項(xiàng) if(indexItem == nil) { return -1; } //根據(jù)索引項(xiàng)，在主表中查找 for(int i = indexItem.start; i < indexItem.start + indexItem.length; i++) { if(array[i] == number){ return I; break; } } return -1; } //索引 @interface BlockItem : NSObject @property (assign, nonatomic) int start; @property (assign, nonatomic) int length; @property (assign, nonatomic) NSNumber *max; - (instancetype)initWithStart:(int)start length:(int)length max:(NSNumber *)max; @end @implementation BlockItem - (instancetype)initWithStart:(int)start length:(int)length max:(NSNumber *)max { if (self = [super init]) { self.start = start; self.length = length; self.max = max; } return self; } @end //調(diào)用 NSArray *blockArray = @[@3, @4, @6, @2, @5, @7, @14, @12, @16, @13, @19, @17, @25, @21, @36, @23, @22, @29]; BlockItem *model1 = [[BlockItem alloc] initWithStart:0 length:6 max:@7]; BlockItem *model2 = [[BlockItem alloc] initWithStart:6 length:6 max:@19]; BlockItem *model3 = [[BlockItem alloc] initWithStart:12 length:6 max:@36]; NSArray *indicesArray = @[model1, model2, model3]; NSLog(@"分塊查找：%ld", [self blockSearch:blockArray indexItemList:indicesArray searchNumber: @17]);
算法分析
分塊查找由于只要求索引表是有序的绩衷，對(duì)塊內(nèi)節(jié)點(diǎn)沒(méi)有排序要求蹦魔，因此特別適合于節(jié)點(diǎn)動(dòng)態(tài)變化的情況。
索引查找的比較次數(shù)等于算法中查找索引表的比較次數(shù)和查找相應(yīng)子表的比較次數(shù)之和咳燕，假定索引表的長(zhǎng)度為m勿决，子表長(zhǎng)度為s，
則索引查找的平均查找長(zhǎng)度為：
ASL= (1+m)/2 + (1+s)/2 = 1 + (m+s)/2
假定每個(gè)子表具有相同的長(zhǎng)度招盲，即s=n/m, 則 ASL = 1 + (m + n/m)/2 ,當(dāng)m = n/m ,(即m =低缩，此時(shí)s也等于
可見(jiàn)曹货，索引查找的速度快于順序查找咆繁，但低于二分查找。
在索引存儲(chǔ)中顶籽，不僅便于查找單個(gè)元素玩般，而且更方便查找一個(gè)子表中的全部元素，若在主表中的每個(gè)子表后都預(yù)留有空閑位置礼饱，則索引存儲(chǔ)也便于進(jìn)行插入和刪除運(yùn)算坏为。
三、二分查找
二分查找算法也叫折半法查找法镊绪，要求待查找的列表必須是按關(guān)鍵字大小有序排列的順序表匀伏。
二分查找基于分治思想，在實(shí)現(xiàn)上可以使用遞歸或迭代镰吆，首先用給定值k先與中間結(jié)點(diǎn)的關(guān)鍵字比較，中間結(jié)點(diǎn)把線形表分成兩個(gè)子表跑慕，若相等則查找成功万皿；若不相等摧找，再根據(jù)k與該中間結(jié)點(diǎn)關(guān)鍵字的比較結(jié)果確定下一步查找哪個(gè)子表，這樣遞歸進(jìn)行牢硅，直到查找到或查找結(jié)束發(fā)現(xiàn)表中沒(méi)有這樣的結(jié)點(diǎn)蹬耘。
算法描述
- 將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等則表示查找成功减余；否則利用中間位置記錄將表分成前综苔、后兩個(gè)子表。
- 如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字位岔，則進(jìn)一步查找前一個(gè)子表如筛，否則查找后一個(gè)子表。
- 重復(fù)以上過(guò)程抒抬，一直到找到滿足條件的記錄為止時(shí)表明查找成功杨刨。
- 如果最終子表不存在，則表明查找不成功擦剑。
代碼實(shí)現(xiàn)
/// 二分法查找 /// @param array 查找數(shù)組 /// @param number 查找的數(shù)字 - (NSInteger)binarySearch:(NSArray *)array searchNumber:(id)number { NSUInteger mid; NSUInteger min = 0; NSUInteger max = array.count - 1; while (min <= max) { mid = (min + max)/2; if ([number intValue] == [array[mid] intValue]) { NSLog(@"We found the number! It is at index %lu", mid); return mid; break; } else if ([number intValue] < [array[mid] intValue]) { max = mid - 1; } else if ([number intValue] > [array[mid] intValue]) { min = mid + 1; } } return -1; } //調(diào)用 NSArray *binaryArray = @[@1,@20,@30,@45,@50,@55,@60,@66,@70]; NSLog(@"二分法查找：%ld", [self sequentialSearch:binaryArray searchWord:@30]);
算法分析
二分查找方法具有比較次數(shù)少妖胀、查找速度快及平均性能好的優(yōu)點(diǎn)。缺點(diǎn)是要求待查表為有序表惠勒，且插入赚抡、刪除困難。因此纠屋，折半查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表涂臣。
最壞情況下，關(guān)鍵詞比較次數(shù)為巾遭，且期望時(shí)間復(fù)雜度為
肉康；
四、插值查找
插值查找是對(duì)二分查找的一種改進(jìn)灼舍，適用于均勻分布的有序表吼和。思想基本上和二分查找一樣，有修改的地方就是mid的獲取骑素。
在二分查找中炫乓，mid=(start+end)/2, 即mid=start+(end-start)/2;也就是說(shuō)我們的mid每次都是折中的取，但是對(duì)于一些均勻分布的有序表献丑，這樣做感覺(jué)有些費(fèi)時(shí)末捣，比如找字典的時(shí)候，找a這個(gè)字母创橄，我們肯定不會(huì)從中間開(kāi)始箩做，而是偏向于字典前面一些開(kāi)始。
插值查找就是基于這樣的思想對(duì)mid取值進(jìn)行改進(jìn)妥畏。通過(guò)類比邦邦，我們可以將查找的點(diǎn)改進(jìn)為如下：
mid = start + (searchValue-array[start]) / (array[end]-array[start]) * (end-start)安吁，
也就是將上述的比例參數(shù)1/2改進(jìn)為自適應(yīng)的，根據(jù)關(guān)鍵字在整個(gè)有序表中所處的位置燃辖，讓mid值的變化更靠近關(guān)鍵字searchValue鬼店，這樣也就間接地減少了比較次數(shù)。
算法描述
- 將表mid位置記錄的關(guān)鍵字與查找關(guān)鍵字比較黔龟，如果兩者相等則表示查找成功妇智；否則利用中間位置記錄將表分成前、后兩個(gè)子表氏身。
- 如果mid位置記錄的關(guān)鍵字大于查找關(guān)鍵字巍棱，則進(jìn)一步查找前一個(gè)子表，否則查找后一個(gè)子表观谦。
- 重復(fù)以上過(guò)程拉盾，一直到找到滿足條件的記錄為止時(shí)表明查找成功。
- 如果最終子表不存在豁状，則表明查找不成功捉偏。
代碼實(shí)現(xiàn)
/// 插值查找 /// @param array 查找數(shù)組 /// @param number 要查找數(shù)字 /// @param startIndex 查找起始位置 /// @param endIndex 查找結(jié)束位置 - (NSInteger)insertValueSearch:(NSArray *)array searchNumber:(id)number startIndex:(int)startIndex endIndex:(int)endIndex { if (endIndex >= startIndex) { int mid = startIndex + ([number intValue] - [array[startIndex] intValue]) / ([array[endIndex] intValue] - [array[startIndex] intValue]) * (endIndex - startIndex); if (array[mid] == number) { return mid; } else if (array[mid] > number) { return [self insertValueSearch:array searchNumber:number startIndex:startIndex endIndex:mid-1]; } else if (array[mid] < number) { return [self insertValueSearch:array searchNumber:number startIndex:mid+1 endIndex:endIndex]; } } return -1; } //調(diào)用 NSArray *insetValueArray = @[@1,@20,@30,@45,@50,@55,@60,@66,@70]; NSLog(@"插值查找：%ld", [self insertValueSearch:insetValueArray searchNumber:@70 startIndex:0 endIndex:(insetValueArray.count-1)]);
算法分析
查找成功或者失敗的時(shí)間復(fù)雜度均為
。
對(duì)于表長(zhǎng)較大泻红，而關(guān)鍵字分布又比較均勻的查找表來(lái)說(shuō)夭禽，插值查找算法的平均性能比折半查找要好的多。反之谊路，數(shù)組中如果分布非常不均勻(如[@1,@2,@3,@201,@202,@203,@1000,@1001,@1003])讹躯，那么插值查找未必是很合適的選擇。
五缠劝、斐波那契查找
上面我們講了插值查找潮梯，它是基于折半查找改進(jìn)，然后除了插值方式的切割外惨恭，還有基于斐波那契黃金分割點(diǎn)切割方式的改進(jìn)秉馏。
所以斐波那契查找也是改變了二分查找中原有的中值 mid 的求解方式，其 mid 不再代表中值脱羡，而是代表了黃金分割點(diǎn)：
mid = left + F_{block - 1} - 1
算法描述
- 將表mid位置記錄的關(guān)鍵字與查找關(guān)鍵字比較萝究，如果兩者相等則表示查找成功；否則利用中間位置記錄將表分成前锉罐、后兩個(gè)子表帆竹。
- 如果mid位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一個(gè)子表脓规，否則查找后一個(gè)子表栽连。
- 重復(fù)以上過(guò)程，一直到找到滿足條件的記錄為止時(shí)表明查找成功侨舆。
- 如果最終子表不存在秒紧，則表明查找不成功舷暮。
代碼實(shí)現(xiàn)
#pragma mark 斐波那契查找 /// 斐波那契查找 /// @param array 查找數(shù)組 /// @param searchNumber 查找的數(shù)字 - (NSInteger)fibonacciSearch:(NSArray *)array searchValue:(id)searchNumber { NSMutableArray *mArray = [NSMutableArray arrayWithArray:array]; NSArray *fibArray = [self fibonacciArray:30]; int startIndex = 0; int endIndex = mArray.count - 1; int k = 0; while (endIndex > ([fibArray[k] intValue] - 1)) { k ++; } for (int i = mArray.count; i <= [fibArray[k] intValue]; i ++) { mArray[i] = mArray[endIndex]; } while (startIndex <= endIndex) { int mid = startIndex + [fibArray[k - 1] intValue] - 1; // 根據(jù)斐波那契數(shù)列進(jìn)行黃金分割 if ([mArray[mid] intValue] == [searchNumber intValue]) { if (mid <= array.count - 1) { return mid; } else { // 說(shuō)明查找得到的數(shù)據(jù)元素是補(bǔ)全值 return array.count - 1; } } else if ([mArray[mid] intValue] > [searchNumber intValue]) { endIndex = mid - 1; k = k - 1; } else if ([mArray[mid] intValue] < [searchNumber intValue]) { startIndex = mid + 1; k = k - 2; } } return -1; } /// 獲得一個(gè)斐波那契數(shù)組 /// @param size 數(shù)組大小 - (NSArray *)fibonacciArray:(NSInteger)size { NSMutableArray *array = [NSMutableArray arrayWithCapacity:size]; array[0] = @1; array[1] = @1; for (int i=2; i < size; i++) { array[i] = @([array[i-1] longLongValue] + [array[i-2] longLongValue]); } return array; } //調(diào)用 NSArray *fibonacciArray = @[@1,@3,@5,@7,@8,@10,@13,@15,@17,@19,@21]; NSLog(@"斐波那契查找：%ld", [self fibonacciSearch:fibonacciArray searchValue:@19]);
算法分析
在最壞情況下，斐波那契查找的時(shí)間復(fù)雜度還是
噩茄，且其期望復(fù)雜度也為
六衅谷、二叉樹(shù)查找
二叉查找樹(shù)（Binary Search Tree，BST）是一種特殊的二叉樹(shù)似将，一棵二叉搜索樹(shù)（BST）是一棵二叉樹(shù)获黔，其中，每個(gè)節(jié)點(diǎn)的值都要大于其左子樹(shù)中任意節(jié)點(diǎn)的值而小于右子樹(shù)中任意節(jié)點(diǎn)的值在验。
算法描述
- 如果二叉查找樹(shù)為空玷氏，則返回空操作，否則腋舌，執(zhí)行一下操作盏触；
- 先取根節(jié)點(diǎn)，如果節(jié)點(diǎn) X 等于根節(jié)點(diǎn)块饺，則返回赞辩；
- 如果節(jié)點(diǎn)小于根節(jié)點(diǎn)，則遞歸查找左子樹(shù)授艰；如果節(jié)點(diǎn)大于根節(jié)點(diǎn)辨嗽，則遞歸查找右子樹(shù)。
代碼實(shí)現(xiàn)
@interface Tree : NSObject @property (strong, nonatomic) NSNumber *value;//值 @property (assign, nonatomic) int index;//下標(biāo) @property (strong, nonatomic) Tree *left;//左樹(shù) @property (strong, nonatomic) Tree *right;//右樹(shù) - (instancetype)initWithValue:(NSNumber *)value index:(int)index left:(Tree *)left right:(Tree *)right; @end @implementation Tree - (instancetype)initWithValue:(NSNumber *)value index:(int)index left:(Tree *)left >right:(Tree *)right { if (self = [super init]) { self.value = value; self.index = index; self.left = left; self.right = right; } return self; } @end #pragma mark 二叉樹(shù)查找 /// 二分法查找 /// @param binaryTree 查找的二叉樹(shù) /// @param number 查找的數(shù)字 - (NSInteger)binaryTreeSearch:(Tree *)binaryTree searchNumber:(id)number { Tree *tree = binaryTree; NSInteger index = -1; while (tree != nil) { if (number < tree.value) { tree = tree.left; } else if (number > tree.value) { tree = tree.right; } else if (number == tree.value) { index = tree.index; } } return index; }
算法分析
最優(yōu)情況下想诅，二叉搜索樹(shù)為完全二叉樹(shù)召庞，其時(shí)間復(fù)雜度為：O(
)
最差情況下，二叉搜索樹(shù)為單支樹(shù), 来破，其時(shí)間復(fù)雜度為：O(n)
一般的篮灼，二叉排序樹(shù)的查找性能在O(
七炮沐、哈希表法(散列表)
哈希查找是是一種以 鍵-值(key-indexed) 存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)争群，我們只要輸入待查找的值即key，即可查找到其對(duì)應(yīng)的值大年。
哈希表查找又叫散列表查找换薄，通過(guò)查找關(guān)鍵字不需要比較就可以獲得需要記錄的存儲(chǔ)位置，它是通過(guò)在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系hashAddress翔试，使得每個(gè) key 對(duì)應(yīng)一個(gè)存儲(chǔ)位置 hashAddress(key)轻要。若查找集合中存在這個(gè)記錄，則必定在 hashAddress(key) 的位置上垦缅。
算法描述
- 用給定的哈希函數(shù)構(gòu)造哈希表冲泥。
- 根據(jù)選擇的沖突處理方法解決地址沖突，常見(jiàn)的解決沖突的方法：拉鏈法和線性探測(cè)法
- 在哈希表的基礎(chǔ)上執(zhí)行哈希查找
代碼實(shí)現(xiàn)
#pragma mark 哈希查找 /// 哈希查找（未考慮沖突） /// @param array 查找數(shù)組 /// @param number 要查找元素 - (NSInteger)hashSearch:(NSArray *)array searchNumber:(id)number { NSDictionary *hashTable = [self makeHashTable:array]; if ([hashTable valueForKey:[NSString stringWithFormat:@"%@", number]]) { NSInteger index = [[hashTable valueForKey:[NSString stringWithFormat:@"%@", number]] integerValue]; return index; } return -1; } - (NSDictionary *)makeHashTable:(NSArray *)array { NSMutableDictionary *hash = [NSMutableDictionary dictionary]; for (int i = 0; i < array.count; i++) { if (![hash valueForKey:[NSString stringWithFormat:@"%d", i]]) { [hash setValue:[NSString stringWithFormat:@"%d", i] forKey:[NSString stringWithFormat:@"%@", array[i]]]; } } return hash; } NSArray *hashArray = @[@1,@3,@5,@7,@8,@10,@13,@15,@17,@19,@21]; NSLog(@"哈希查找：%ld", [self hashSearch:hashArray searchNumber:@13]);
算法分析
單純論查找復(fù)雜度：對(duì)于無(wú)沖突的Hash表而言壁涎，查找復(fù)雜度為O(1)凡恍。
哈希表可以以極快的速度來(lái)查找、添加或刪除元素（只需要數(shù)次的比較操作怔球。）它比紅黑樹(shù)咳焚、二叉搜索樹(shù)都要快得多。但是哈希表沒(méi)有排序功能庞溜，類似的革半，如尋找最大值、最小值流码、中值這些行為都不能在哈希表中實(shí)現(xiàn)又官。
哈希表的查找過(guò)程基本上和造表過(guò)程相同。一些關(guān)鍵碼可通過(guò)哈希函數(shù)轉(zhuǎn)換的地址直接找到漫试，另一些關(guān)鍵碼在哈希函數(shù)得到的地址上產(chǎn)生了沖突六敬，需要按處理沖突的方法進(jìn)行查找。在介紹的三種處理沖突的方法中驾荣，產(chǎn)生沖突后的查找仍然是給定值與關(guān)鍵碼進(jìn)行比較的過(guò)程外构。所以，對(duì)哈希表查找效率的量度播掷，依然用平均查找長(zhǎng)度來(lái)衡量审编。
查找過(guò)程中，關(guān)鍵碼的比較次數(shù)取決于產(chǎn)生沖突的多少歧匈。如果產(chǎn)生的沖突少垒酬，查找效率就高，如果產(chǎn)生的沖突多，查找效率就低勘究。因此矮湘，影響產(chǎn)生沖突多少的因素，也就是影響查找效率的因素口糕。影響產(chǎn)生沖突多少有以下三個(gè)因素：
∶逖簟① 哈希函數(shù)是否均勻；
【懊琛② 處理沖突的方法券时；
③ 哈希表的裝填因子伏伯。
分析這三個(gè)因素，盡管哈希函數(shù)的“好壞”直接影響沖突產(chǎn)生的頻度捌袜，但一般情況下说搅，我們總認(rèn)為所選的哈希函數(shù)是“均勻的”。因此虏等，可不考慮哈希函數(shù)對(duì)平均查找長(zhǎng)度的影響弄唧。
哈希表的裝填因子定義為 α =
是哈希表裝滿程度的標(biāo)志因子。由于表長(zhǎng)是定值霍衫，α與“填入表中的元素個(gè)數(shù)”成正比候引，所以，α越大敦跌，填入表中的元素較多澄干，產(chǎn)生沖突的可能性就越大；α越小柠傍，填入表中的元素較少麸俘，產(chǎn)生沖突的可能性就越小。
實(shí)際上惧笛，哈希表的平均查找長(zhǎng)度是裝填因子α的函數(shù)从媚，只是不同處理沖突的方法有不同的函數(shù)。下表為幾種不同處理沖突方法的平均查找長(zhǎng)度:
處理沖突的方法 2+ 查找成功時(shí) 查找不成功時(shí) 線性探測(cè)法 Hnl = (1 +
)
Unl = )
二次探測(cè)法與再哈希法 Hnl = - %7D)
Unl = 鏈地址法 Hnl = 1 + 
Unl = α + 
哈希方法存取速度快患整、節(jié)省空間拜效，靜態(tài)查找、動(dòng)態(tài)查找均適用各谚，但由于存取是隨機(jī)的紧憾，因此，不便于順序查找昌渤。
